COCI 2015/2016 Round 3 Nekameleoni 【线段树+尺取】

tonyfang posted @ 2016年9月22日 20:57 in coci with tags c++ OI , 1443 阅读

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;
}
zhouyi 说:
2016年9月23日 12:49

球做domino

Shala darpan school 说:
2022年8月04日 12:57

Government of Rajasthan has come forward with an integrated website for every teacher in their state. The website Shala Darpan does consist of information about teachers, students, schools, and its related services. If you’re a teacher from Rajasthan state, then you would need to create your access in the Shala Darpan website and make use of it to experience the various services. Shala darpan school login This site is useful to become a teacher and does get enough information about the future aspects of being a teacher. The portal managed by the School Education Department and Rajasthan Council of Education Department. There are numerous services for use using official Shaladarpan, to get work done in an easier manner.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter