nekameleoni

题目大意：长度为$n$的线段，初始有染颜色，颜色种类$k$，$m$次操作，两种情况：①改变单条线段颜色；②查询包含所有$k$种颜色的最少长度。

$n,m \leq 10^5, k \leq 50$

【题解】看$k$的范围大概想了想状压，发现套上线段树直接做是$O((m+n)logn \times k^2)$，是会超时的。

后来想了下好像可以利用单调性搞一个尺取？？excited！

复杂度$O((m+n)logn \times k)$

空间差点炸了。时间比标程优秀。

# include <stdio.h>
# include <vector>
# include <algorithm>
typedef long long ll;
# define pli pair<ll, int>
# define MP make_pair
# define V first
# define NUM second
# define lc x<<1
# define rc x<<1|1
using namespace std;

int n, k, m;
int seq[100010];

int w[300100], llen[300100], rlen[300100];
pli left[300010][51], right[300010][51];
const int INF = 2147483000;

inline bool in(ll a, ll b) {
	return (a&b) == a;
}

inline void merge(int x) {
	w[x] = INF;
	int plen = 0;
	for (int i=1; i<=llen[lc]; ++i)
		left[x][++plen] = left[lc][i];
	for (int i=1; i<=llen[rc]; ++i) {
		if(plen == 0 || !in(left[rc][i].V, left[x][plen].V)) {
			left[x][++plen] = left[rc][i];
			if(plen > 1) left[x][plen].V = left[x][plen].V | left[x][plen-1].V;
		}
	}
	llen[x] = plen;
	
	int slen = 0;
	for (int i=1; i<=rlen[rc]; ++i) 
		right[x][++slen] = right[rc][i];
	for (int i=1; i<=rlen[lc]; ++i) {
		if(slen == 0 || !in(right[lc][i].V, right[x][slen].V)) {
			right[x][++slen] = right[lc][i];
			if(slen > 1) right[x][slen].V = right[x][slen].V | right[x][slen-1].V;
		}
	}
	rlen[x] = slen;
	
	// merge
	
	int rpos = 1;
	for (int lpos = llen[rc]; lpos >= 1; --lpos) {
		while(rpos <= rlen[lc] && (right[lc][rpos].V | left[rc][lpos].V) != (1LL<<k)-1) ++rpos;
		if(rpos <= rlen[lc]) {
			if((right[lc][rpos].V | left[rc][lpos].V) == (1LL<<k)-1) {
				w[x] = min(w[x], left[rc][lpos].NUM - right[lc][rpos].NUM+1);
			}
		}
	}
	w[x] = min(w[x], min(w[lc], w[rc]));
}

inline void change(int x, int l, int r, int pos, int del) {
	if(l == r) {
		llen[x] = rlen[x] = 1;
		left[x][1] = right[x][1] = MP(1LL<<del, l);
		w[x] = INF;
		return ;
	}
	int mid = l+r>>1;
	if(pos <= mid) change(lc, l, mid, pos, del);
	else change(rc, mid+1, r, pos, del);
	merge(x);
}


int main() {
	freopen("nekameleoni.in", "r", stdin);
	freopen("nekameleoni.out", "w", stdout);
	
	scanf("%d%d%d", &n, &k, &m);
	
	for (int i=1; i<=n; ++i) {
		scanf("%d", &seq[i]);
		change(1, 1, n, i, seq[i]-1);
	}

	int opt, ta, tb;
	while(m--) {
		scanf("%d", &opt);
		if(opt == 2) {
			printf("%d\n", w[1] == INF ? -1 : w[1]);
		} else {
			scanf("%d%d", &ta, &tb);
			change(1, 1, n, ta, tb-1);
		}
	}

	return 0;
}