COCI 2015/2016 Round 3 Nekameleoni 【线段树+尺取】
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; }
2016年9月23日 12:49
球做domino