容易想到建一棵平衡树，修改时打上标记即可。但是修改会导致平衡树结构被破坏。注意到实际上只有[k+1,2k)这一部分数在平衡树中的位置会被改变，所以对这一部分暴力修改，因为每次都会使其至少减小一半，复杂度非常正确。
开始写的玩意一个点要跑10s吓到我了，卡了半天常（最后也只是在darkbzoj上过了）造了半天bug，调的欲仙欲死，退役了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<cassert> using namespace std; #define ll long long #define N 100010 #define inf 2000000001 #define lson tree[k].ch[0] #define rson tree[k].ch[1] char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,a[N],root,cnt; struct data{int x,ch[2],fa,s,lazy; }tree[N<<5]; inline void up(int k){tree[k].s=tree[lson].s+tree[rson].s+1;} inline void update(int k,int x){if (k) {if (tree[k].x<inf) tree[k].x-=x;tree[k].lazy+=x;}} inline void down(int k){if (tree[k].lazy) update(lson,tree[k].lazy),update(rson,tree[k].lazy),tree[k].lazy=0;} inline void push(int k){if (tree[k].fa) push(tree[k].fa);down(k);} inline int whichson(int k){return tree[tree[k].fa].ch[1]==k;} inline void move(int k) { int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k); tree[gf].ch[whichson(fa)]=k,tree[k].fa=gf; tree[fa].ch[p]=tree[k].ch[!p],tree[tree[k].ch[!p]].fa=fa; tree[k].ch[!p]=fa,tree[fa].fa=k; up(fa),up(k); } void splay(int k,int rt) { push(k); while (tree[k].fa!=rt) { int fa=tree[k].fa; if (tree[fa].fa!=rt) if (whichson(k)^whichson(fa)) move(k); else move(fa); move(k); } if (!rt) root=k; } void build(int &k,int l,int r) { if (l>r) return; int mid=l+r>>1; k=++cnt;tree[k].x=a[mid],tree[k].s=r-l+1; build(lson,l,mid-1);build(rson,mid+1,r); tree[lson].fa=tree[rson].fa=k; } int find(int k,int x) { if (tree[lson].s+1==x) return k; down(k); if (tree[lson].s+1>x) return find(lson,x); else return find(rson,x-tree[lson].s-1); } int qsuf(int k,int x) { if (!k) return 0; down(k); if (tree[k].x<x) return qsuf(rson,x); else { int t=qsuf(lson,x); return t&&tree[t].x<=tree[k].x?t:k; } } int qpre(int k,int x) { if (!k) return 0; down(k); if (tree[k].x>x) return qpre(lson,x); else { int t=qpre(rson,x); return t&&tree[t].x>=tree[k].x?t:k; } } void ins(int x) { int k=root,fa=0; while (k) down(k),tree[k].s++,fa=k,k=tree[k].x<=x?rson:lson; k=++cnt;tree[k].x=x,tree[k].s=1,tree[k].fa=fa,tree[fa].ch[tree[fa].x<=x]=k; splay(k,0); } void dfs(int k,int x) { if (!k) return; down(k); ins(tree[k].x-x); dfs(lson,x),dfs(rson,x); } void modify(int x) { int p=qpre(root,x),q=qsuf(root,2*x); splay(p,0);splay(q,p); int k=tree[q].ch[0];tree[q].ch[0]=0;up(q);up(p);update(q,x); dfs(k,x); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4923.in","r",stdin); freopen("bzoj4923.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); a[0]=0,a[n+1]=inf;sort(a,a+n+1); build(root,0,n+1); for (int i=1;i<=m;i++) { int op=read(),x=read(); if (op==1) printf("%d ",tree[find(root,x+1)].x); else modify(x); } return 0; }