Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css

Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css_WEB-ITnose

php中文网

发布： 2016-06-24 11:53:13

原创

1391人浏览过

/*题目*/

立即学习“前端免费学习笔记（深入）”；

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

题意：给了n,m,然后一个包含m个数的数组nnum，数组默认从小到大排序，然后是 n个操作，输入一个数x，若x为0，把0加到这个字符串的末尾，若x为1，把1加到这个字符串的末尾，若x为-1，那么把字符串里的下标与 nnum数组里的元素相等的给删除，字符串一开始是空的，问你最后字符串里有什么，若为空就输出 POOR STACK

这题目看这操作一般都很容易联想到线段树，树状数组，一开始我建了个树状数组，但是超时了，毕竟操作很多，而且在删除操作里，若nnum数组很大，等同于10^12的复杂度，只能优化，一般来说是用二分了，直接以这个串的某个位置是否为空来建立树状数组，每一次加在最后就不用说了，直接加就可以，关键在于删除，首先删除，要第一步二分查找出要删除的最后一位，比如字符串长度为7，而nnum数组里有个8，其实8这个位置不需要删除的，但是这个还是超时，于是想到在树状数组里删除的时候也需要二分，可是写了一直错，后来借鉴了杰哥的发现，原来WA在这里，比如当前字符串为01010，需要删除 1，3，4位置的字符，要轮着来，当你删除1号位置的时候，字符串变成了1010，你在树状数组里也是要删除1节点的状态，所以原来的3号位置在当前变成了2号位置，当你删了3号以后变成了110 ，原来的4号位置变成了2号位置，所以每删除一次，下标会发生变化，但是没事，发现前面操作了几次而你原来的下标就比当前减少了几，所以 nnum[i] - i 其实就是当前需要删除的元素在树状数组里的位置

立即学习“前端免费学习笔记（深入）”；

int n,m;int c[1000000 + 55];int nnum[1000000 + 55];int aa[1000000 + 55];int sum[1000000 + 55];int len;void init() {	memset(c,0,sizeof(c));	memset(aa,-1,sizeof(aa));}bool input() {	while(cin>>n>>m) {		for(int i=0;i<m;i++)cin>>nnum[i];		return false;	}	return true;}int lowbit(int x) {	return x&(-x);}void add(int i,int val) {	while(i <= n) {		c[i] += val;		i += lowbit(i);	}}int get_sum(int i) {	int sum = 0;	while(i > 0) {		sum += c[i];		i -= lowbit(i);	}	return sum;}void binary_find(int pos,int id) {	int l = 1;	int r = n;	while(l <= r) {		int mid = (l + r)>>1;		int ret = get_sum(mid);		if(aa[mid] == -1) {			if(ret >= nnum[pos] - id) r = mid - 1;			else l = mid + 1;		}		else if(ret == nnum[pos] - id) {			add(mid,-1);			aa[mid] = -1;			len--;			break;		}		else if(ret > nnum[pos] - id) r = mid - 1;		else if(ret < nnum[pos] - id) l = mid + 1;	}}void cal() {	int q = n;	len = 0;	int cnt = 1;	while(q--) {		int type;		cin>>type;		if(type == -1) {			if(len == 0)continue;			if(nnum[0] > len)continue;			int now = lower_bound(nnum,nnum + m,len) - nnum;			for(int i=0;i<=now;i++)				binary_find(i,i);		}		else {			aa[cnt] = type;			add(cnt,1);			cnt++;			len++;		}	}	if(len <= 0){puts("Poor stack!");return ;}	for(int i=1;i<=n;i++)		if(aa[i] != -1)			printf("%d",aa[i]);	puts("");}void output() {}int main() {	while(true) {		init();		if(input())return 0;		cal();		output();	}	return 0;}

登录后复制

立即学习“前端免费学习笔记（深入）”；