为什么改一下计数方式就可以了
查看原帖
为什么改一下计数方式就可以了
576448
aulive楼主2023/7/11 09:15

为什么改一下计数方式就可以了

WA

AC

#include<bits/stdc++.h>
using namespace std;
int x,n,root,tot,minn,add,kkksc03,kkk;
struct node{
	int lef,rig,num,val,key,size;
}tree[300001];
char opt;
void zag(int &now){
	int x=tree[now].rig;
	tree[now].rig=tree[x].lef;
	tree[x].lef=now;
	tree[x].size=tree[now].size;
	tree[now].size=tree[tree[now].lef].size+tree[tree[now].rig].size+tree[now].num;
	now=x;
}
void zig(int &now){
	int x=tree[now].lef;
	tree[now].lef=tree[x].rig;
	tree[x].rig=now;
	tree[x].size=tree[now].size;
	tree[now].size=tree[now].num+tree[tree[now].lef].size+tree[tree[now].rig].size;
	now=x;
}
void insert(int &now,int x){
	if(!now){
		now=++tot;
		tree[now].size=1;
		tree[now].key=rand();
		tree[now].val=x;
		tree[now].num=1;
		return;
	}
	tree[now].size++;
	if(tree[now].val==x){
		tree[now].num++;
	}else{
		if(tree[now].val>x){
			insert(tree[now].lef,x);
			if(tree[now].key>tree[tree[now].lef].key){
				zig(now);
			}
		}else{
			insert(tree[now].rig,x);
			if(tree[now].key>tree[tree[now].rig].key){
				zag(now);
			}
		}
	}
}
void _delete(int &now){
	if(!now)
	return;
	if(tree[now].val+add<minn){
		kkksc03=kkksc03+tree[now].num+tree[tree[now].lef].size;
		now=tree[now].rig;
		_delete(now);
	}else{
		_delete(tree[now].lef);
	}
}
//void _delete(int &now){
//	if(!now)
//	return;
//	if(tree[now].val+add<minn){
//		kkksc03+=tree[now].num;
//		_delete(tree[now].lef);
//		now=tree[now].rig;
//		_delete(now);
//	}else{
//		_delete(tree[now].lef);
//	}
//}AC代码,其他地方一样
int find_num(int x){
	int now=root;
	while(now){
		if(tree[tree[now].rig].size<x&&tree[now].num+tree[tree[now].rig].size>=x){
			return tree[now].val;
		}
		if(tree[tree[now].rig].size>=x){
			now=tree[now].rig;
		}else{
			x=x-tree[tree[now].rig].size-tree[now].num;
			now=tree[now].lef;
		}
	}
}
int main(){
	cin>>n>>minn;
	while(n--){
		scanf("%s%d",&opt,&x);
		if(opt=='I'){
			if(x>=minn){
				kkk++;
				insert(root,x-add);
			}
		}else{
			if(opt=='S'){
				add-=x;
				_delete(root);
			}else{
				if(opt=='A'){
					add+=x;
				}else{
					if(kkk-kkksc03<x){
						printf("-1\n");
					}else
					printf("%d\n",find_num(x)+add);
				}
			}
		}
	}
	printf("%d",kkksc03);
	return 0;
}  
2023/7/11 09:15
加载中...