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

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

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.

Svmcm.wbhed.gov.in 说:
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. Svmcm.wbhed.gov.in 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.

manabadi2020.in 说:
2023年4月19日 16:19

Every time Andhra Pradesh SSC 10th class examinations AP SSC Time Table 2024 are scheduled students try get all in one and guides to prepare for the exams manabadi2020.in for Maths, Physical Science, Bio Science, Social Studies, Urdu, English, Hindi, Telugu and Sanskrit Model Papers. Most of the times the exam papers are prepared based on these Sample papers only to check with them one can visit their official website.

WB 7th Class Syllab 说:
2023年7月13日 15:54

West Bengal Board of Secondary Education is the West Bengal State Government Administered Autonomous Examining Authority for the 7th,Class Standard Examination of West Bengal, WBBSE is an agency of Government of West Bengal Entrusted with the Responsibilities of Prescribing Courses of instructions and Books and Syllabus, Conducting Examinations for High School Level Students in West Bengal.Board High School Parents can WB 7th Class Syllabus 2024 use the Syllabus to Understand the Concepts and Prepare their Children for the Exam, Accordingly, The West Bengal Class Syllabus 2024 All Subject Chapter Wise Students Prepare for the Upcoming 7th Class Exam


登录 *


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