两种做法：线段树和树状数组
TLE了几次= = 主要是cout
#include#include #include using namespace std;const int maxn = 30000+10;const int maxm = 65535*3+1;int n,num[maxn],C[maxm];inline int lowbit(int x){ return x&(-x);}int sum(int x){ int ret = 0; while(x > 0){ ret += C[x]; x -= lowbit(x); } return ret;}void add(int x,int d){ while(x <= maxm) { C[x] += d; x += lowbit(x); }}int find(int x){ int L = 1,R = maxm; while(L<=R){ int mid = (L+R)>>1; if(sum(mid)<=x){ L = mid+1; }else{ R = mid-1; } } return L;}int main(){ scanf("%d",&n); memset(C,0,sizeof(C)); for(int i = 1; i <= n; i++){ scanf("%d",&num[i]); add(num[i],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){ add(num[a],-1); num[a]-=b; if(num[a]>0) add(num[a],1); else n--; } } else{ scanf("%d%d",&a,&b); if(num[a]>0){ add(num[a],-1); num[a]+=b; add(num[a],1); } } } printf("%d\n",n); return 0;}
#include#include #include 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;}