题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4923
解法题解里说的挺清楚的，好吧，我就是找个地方存一哈代码...
辣鸡卡常题，跑了16s竟然判过了....实在是优化不动了
代码：
#include<bits/stdc++.h> using namespace std; const int MAXN=100010; const int INF=2e9+5; int a[MAXN]; int n,q; namespace Splay_Tree { #define Key_value ch[ch[root][1]][0] int pre[MAXN],ch[MAXN][2],key[MAXN],size[MAXN],sub[MAXN],tmp[MAXN]; int root,tot1,cnt; inline void NewNode(int &r,int father,int k) { r=++tot1; pre[r]=father; ch[r][0]=ch[r][1]=0; key[r]=k; size[r]=1; sub[r]=0; } inline void push_up(int r) { int lson=ch[r][0],rson=ch[r][1]; size[r]=size[lson]+size[rson]+1; } inline void up_sub(int r,int k) { if(!r) return ; if(key[r]!=-1&&key[r]!=INF) key[r]-=k; sub[r]+=k; } inline void push_down(int r) { if(sub[r]) { up_sub(ch[r][0],sub[r]); up_sub(ch[r][1],sub[r]); sub[r]=0; } } inline void Build(int &x,int l,int r,int father) { if(l>r) return; int mid=(l+r)/2; NewNode(x,father,a[mid]); Build(ch[x][0],l,mid-1,x); Build(ch[x][1],mid+1,r,x); push_up(x); } inline void Init() { root=tot1=0; ch[root][0]=ch[root][1]=size[root]=pre[root]=0; key[root]=0; sub[root]=0; NewNode(root,0,-1); NewNode(ch[root][1],root,INF); Build(Key_value,1,n,ch[root][1]); push_up(ch[root][1]); push_up(root); } //旋转,0为左旋，1为右旋 inline void Rotate(int x,int kind) { int y=pre[x]; push_down(y); push_down(x); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; push_up(y); } //Splay调整，将r结点调整到goal下面 inline void Splay(int r,int goal) { push_down(r); while(pre[r]!=goal) { if(pre[pre[r]]==goal) { push_down(pre[r]); push_down(r); Rotate(r,ch[pre[r]][0]==r); } else { push_down(pre[pre[r]]); push_down(pre[r]); push_down(r); int y=pre[r]; int kind=ch[pre[y]][0]==y; if(ch[y][kind]==r) { Rotate(r,!kind); Rotate(r,kind); } else { Rotate(y,kind); Rotate(r,kind); } } } push_up(r); if(goal==0) root=r; } //获得第K个位置数 inline int Get_kth(int r,int k) { push_down(r); int t=size[ch[r][0]]+1; if(t==k) return r; if(t>k) return Get_kth(ch[r][0],k); else return Get_kth(ch[r][1],k-t); } inline int Get_mx(int r) { push_down(r); if(ch[r][1]) return Get_mx(ch[r][1]); return r; } inline int Get_mi(int r) { push_down(r); if(ch[r][0]) return Get_mx(ch[r][0]); return r; } inline int Get_ri(int r,int k) { int ret=-1; while(1) { push_down(r); if(key[r]>k) { ret=r; if(ch[r][0]) r=ch[r][0]; else return ret; } else { if(ch[r][1]) r=ch[r][1]; else return ret; } } } inline int Get_lf(int r,int k) { int ret=-1; while(1) { push_down(r); if(key[r]<=k) { ret=r; if(ch[r][1]) r=ch[r][1]; else return ret; } else { if(ch[r][0]) r=ch[r][0]; else return ret; } } } inline void InOrder(int r) { if(!r) return; push_down(r); InOrder(ch[r][0]); tmp[cnt++]=r; InOrder(ch[r][1]); } inline int Get_next(int r) { push_down(r); if(ch[r][1]==0) return -1; r=ch[r][1]; push_down(r); while(ch[r][0]) { r=ch[r][0]; push_down(r); } return r; } void Insert(int r,int now) { push_down(r); if(key[tmp[now]]<key[r]) { if(ch[r][0]) { Insert(ch[r][0],now); } else { pre[tmp[now]]=r; ch[r][0]=tmp[now]; ch[tmp[now]][0]=ch[tmp[now]][1]=0; size[tmp[now]]=1; sub[tmp[now]]=0; } push_up(r); } if(key[tmp[now]]>=key[r]) { if(ch[r][1]) { Insert(ch[r][1],now); } else { pre[tmp[now]]=r; ch[r][1]=tmp[now]; ch[tmp[now]][0]=ch[tmp[now]][1]=0; size[tmp[now]]=1; sub[tmp[now]]=0; } push_up(r); } } void change(int k) { int l=Get_lf(root,k); Splay(l,0); int r=Get_ri(root,k+k); Splay(r,root); if(key[ch[root][1]]!=INF) { key[ch[root][1]]-=k; } sub[ch[root][1]]+=k; push_down(ch[root][1]); if(Key_value==0) return ; int sv=Key_value; cnt=0; pre[sv]=0; Key_value=0; InOrder(sv); int now=0; while(now<cnt) Insert(root,now++); } } using namespace Splay_Tree; inline char nc() { static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void rea(int &x) { char c=nc(); x=0; for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc()); } int op,k; int main() { //freopen("in.in","r",stdin); //freopen("out.out","w",stdout); rea(n);rea(q); for(int i=1;i<=n;i++) { rea(a[i]); } sort(a+1,a+1+n); Init(); Splay(1,0); while(q--) { rea(op); rea(k); if(op==1) { printf("%d\n",key[Get_kth(root,k+1)]); } else { change(k); } } return 0; }
