势能分析平衡树,splay或treap都可以
放个指针版的就跑
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<=b;++i) ; template <class T> inline bool check_Max(T &x, const T&y) { return x<y?x=y,false:true;} template <class T> inline bool check_Min(T &x, const T&y) { return x>y?x=y,false:true;} inline int gi() { ; char o; bool f=true; for(;!isdigit(o=getchar());) if(o=='-') f=false; )+(x<<)+(o&); ; } struct node {int v,ky,sz,lz; node *ls,*rs;}*rt,*nul,pool[maxn],*pis=pool; inline ; rt=nul;} node *newnode(; k->sz=; return k;} inline void add(node *&x,int vl) { x->v+=vl; x->lz+=vl; return ;} inline void pd(node *&x) { ; } inline ; } inline void mrg(node *&c,node *x,node *y) { if(x==nul||y==nul) {c=x==nul?y:x; return;} pd(x); pd(y); if(x->ky < y->ky) c=x,mrg(c->rs,x->rs,y); else c=y,mrg(c->ls,x,y->ls); up(c); } inline void spl(node *c,node *&x,node *&y,int rk) { if(c==nul) { x=y=nul; return;} pd(c); if(c->v <= rk) x=c,spl(c->rs,x->rs,y,rk); else y=c,spl(c->ls,x,y->ls,rk); up(c); } inline void insert(int vl) { node *x,*y; spl(rt,x,y,vl); mrg(x,x,newnode(vl)); mrg(rt,x,y); } int find(node *&x,int rk) { ==rk) return x->v; pd(x); if(rk<=x->ls->sz) return find(x->ls,rk); ); } inline void rec(node *&now,node *&x,int vl) { if(x==nul) return; pd(x); rec(now,x->ls,vl); rec(now,x->rs,vl); x->ls=x->rs=nul; x->sz=; x->v-=vl; node *x1,*y1; spl(now,x1,y1,x->v); mrg(x1,x1,x); mrg(now,x1,y1); } inline void cg(int k) { node *x,*y,*z; spl(rt,x,y,k); spl(y,y,z,k<<); add(z,-k); rec(x,y,k); mrg(rt,x,z); } int n,m; int main() { #ifndef ONLINE_JUDGE freopen("3.in","r",stdin); freopen("a.out","w",stdout); #endif n=gi();m=gi(); init(); rep(i,,n) insert(gi()); rep(i,,m) { int opt=gi(),K=gi(); ) printf("%d\n",find(rt,K)); else cg(K); } ; }