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

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



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

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


复杂度$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);

int main() {
	freopen("", "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


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. 说:
2022年10月27日 21:45

Education is a significant aspect for everyone but an expensive option for many in the West Bengal state. The state offers quality education and perfect education institutions. However, the majority of students don’t have the financial ability to complete their education. This increase dropout rates and poverty in many families. The West Bengal state has introduced many scholarship schemes to ensure every student get the right to free education. The weak financial students can enjoy scholarship benefits and pursue their education.

登录 *

loading captcha image...
or Ctrl+Enter