信息战（四）——战场演练（线段树，树状数组）
两种做法：线段树和树状数组
TLE了几次= = 主要是cout
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 30000+10;const int maxm = 65535*3+1;struct node{int lson,rson,sum;int mid(){return lson+(rson-lson)/2;}}tree[maxm*4];int n,num[maxn];void pushup(int pos){tree[pos].sum = tree[pos*2+1].sum+tree[pos*2].sum;}void build(int l,int r,int pos){tree[pos].lson = l;tree[pos].rson = r;tree[pos].sum = 0;if(l == r)return;int mid = tree[pos].mid();build(l,mid,pos*2);build(mid+1,r,pos*2+1);}void update(int x,int pos,int k){if(tree[pos].lson==tree[pos].rson && tree[pos].lson==x){tree[pos].sum += k;}else{int mid = tree[pos].mid();if(x<=mid) update(x,pos*2,k);else update(x,pos*2+1,k);pushup(pos);}}int query(int L,int R,int pos){if(tree[pos].lson >= L && tree[pos].rson<=R) return tree[pos].sum;int mid = tree[pos].mid();if(R <= mid) return query(L,R,pos*2);else if(L > mid) return query(L,R,pos*2+1);else return query(L,mid,pos*2)+query(mid+1,R,pos*2+1);}int find(int x){int L = 1,R = maxm;while(L<=R){int mid = (L+R)/2;if(query(1,mid,1)<=x){L = mid+1;}else{R = mid-1;}} return L;}int main(){scanf("%d",&n);int maxk = 0;build(1,maxm,1);for(int i = 1; i <= n; i++){scanf("%d",&num[i]);update(num[i],1,1);}int m;scanf("%d",&m);while(m--){char task[40];int a,b;scanf("%s",task);if(task[0]=='Q'){scanf("%d",&a);if(a>n)printf("-1\n");else printf("%d\n",find(n-a));}else if(task[0]=='A'){scanf("%d%d",&a,&b);if(num[a]>0){update(num[a],1,-1);num[a]-=b;if(num[a]>0) update(num[a],1,1);else n--;}}else{scanf("%d%d",&a,&b);if(num[a]>0){update(num[a],1,-1);num[a]+=b;update(num[a],1,1);}} }printf("%d\n",n);return 0;}