Codeforces Round #220 (Div. 2) D tree array && binary_html/css_WEB-ITnose

/*Title*/

Tips: given n, m, and then an array nnum containing m numbers, the array defaults from small to large Sorting, then n operations, input a number x, if x is 0, add 0 to the end of the string, if x is 1, add 1 to the end of the string, if x is -1, then Delete the subscripts in the string that are equal to the elements in the nnum array. The string is empty at the beginning. What is in the last string? If it is empty, output POOR STACK

. Looking at this operation, it is usually easy to think of line segment trees and tree arrays. I built a tree array at the beginning, but it timed out. After all, there are many operations, and in the deletion operation, if the nnum array is very large, it is equivalent to 10^ The complexity of 12 can only be optimized. Generally speaking, it is divided into two. A tree array is directly established based on whether a certain position of the string is empty. Needless to say, it is added at the end each time. Just add it directly. The key is To delete, first delete, the first step is to use binary search to find the last digit to be deleted. For example, the length of the string is 7, and there is 8 in the nnum array. In fact, the position 8 does not need to be deleted, but this still times out, so I thought that when deleting in a tree array, it also needs to be divided into two parts, but I kept writing it wrong. Later, I learned from Jie Ge's discovery and found that WA is here. For example, the current string is 01010, and the characters at positions 1, 3, and 4 need to be deleted. It takes turns. When you delete position 1, the string becomes 1010. You also need to delete the status of node 1 in the tree array, so the original position 3 becomes position 2. When you delete No. 3, it becomes 110, and the original No. 4 position becomes No. 2, so every time you delete it, the subscript will change, but it’s okay. I found that after several operations before, your original subscript It is a few less than the current one, so nnum[i] - i is actually the position of the element that needs to be deleted in the tree array

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;}