长春网站优化/最有创意的广告语30条

终于填坑！！！！！！
鬼知道以前怎么错的！！
反正现在A了
虽然tyvj还是80 但我相信 那是splay的问题 换做treap就可以（虽然不会....

以后写代码 不要怕 长名变量 取有意义的名字

要以易于维护为第一要求 其次再是美观！！

这次有很多地方可以省略 但为了可维护 就不要怕麻烦 反正比WA掉强！！！

http://pan.baidu.com/s/1nuta3xf 用金币在Tyvj扣的数据 2组大 2组小 我还对着小数据手动排序【捂脸 其实自己通读一遍代码就差不多！

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;int init[50000+1];
int seg_num[50000*4];
int num[2000000],ch[2000000][2],fa[2000000],size[2000000],root[50000*4],cnt=0;
int n,m,opt;
int ans;
void vist(int now)
{if(now==0) return ;cout<<num[now]<<' '<<size[now]<<' '<<num[ch[now][0]]<<' '<<num[ch[now][1]]<<endl;vist(ch[now][0]);vist(ch[now][1]);
}
void Up(int x)
{size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void Rotate(int x,int &rt)
{int y=fa[x],z=fa[y];if(y==rt) {rt=x;z=0;///}else{ch[z][ ch[z][1]==y ]=x;}int c=ch[y][1]==x;fa[x]=z;fa[y]=x;fa[ch[x][c^1]]=y;ch[y][c]=ch[x][c^1];ch[x][c^1]=y;Up(y);Up(x);
}
void Splay(int x,int &rt)
{while(x!=rt){if(fa[x]!=rt) Rotate(fa[x],rt);Rotate(x,rt);}
}
void Ins(int &now,int k,int last,int &rt)
{if(now==0){now=++cnt;fa[now]=last;size[now]=1;num[now]=k;Splay(now,rt);return ;} if(k>=num[now]) Ins(ch[now][1],k,now,rt);else Ins(ch[now][0],k,now,rt);
}
void Build(int now,int L,int R)
{for(int i=L;i<=R;i++) Ins(root[now],init[i],root[now],root[now]);if(L==R) return;Build(now*2,L,(L+R)/2);Build(now*2+1,(L+R)/2+1,R);
}
void Sp_Rank(int now,int k)
{if(now==0) return ;if(num[now]>=k) {Sp_Rank(ch[now][0],k);}else{ans+=size[ch[now][0]]+1;Sp_Rank(ch[now][1],k);}
}
void Seg_Rank(int now,int L,int R,int s,int t,int k)
{if(s<=L&&R<=t){Sp_Rank(root[now],k);return ;}int mid=(L+R)/2;if(s<=mid) Seg_Rank(now*2,L,mid,s,t,k);if(mid+1<=t) Seg_Rank(now*2+1,mid+1,R,s,t,k);
}
int Kth(int s,int t,int k)
{int L=0,R=100000000;int ou;while(L<R){int mid=(L+R)/2;ans=1;Seg_Rank(1,1,n,s,t,mid);if(ans<=k) ou=mid,L=mid+1;else R=mid;}return ou;
}
int Find(int now,int x)
{if(num[now]==x) return now;if(x<num[now]) return Find(ch[now][0],x);else return Find(ch[now][1],x);
}
void Sp_Change(int &rt,int v,int k)
{int loc=Find(rt,v);Splay(loc,rt);if(ch[rt][0]*ch[rt][1]==0) rt=ch[rt][0]+ch[rt][1];else{int tmp=ch[rt][0];while(ch[tmp][1]!=0) tmp=ch[tmp][1];Splay(tmp,ch[rt][0]); ch[ch[rt][0]][1]=ch[rt][1];size[ch[rt][0]]+=size[ch[rt][1]];fa[ch[rt][1]]=ch[rt][0];rt=ch[rt][0];}Ins(rt,k,rt,rt); 
}
void Seg_Change(int now,int L,int R,int pos,int k)
{Sp_Change(root[now],init[pos],k);if(L==R) return ;int mid=(L+R)/2;if(pos<=mid) Seg_Change(now*2,L,mid,pos,k);else Seg_Change(now*2+1,mid+1,R,pos,k); 
}
void Sp_Before(int now,int k)
{if(now==0) return ;if(num[now]>=k) Sp_Before(ch[now][0],k);else ans=max(ans,num[now]),Sp_Before(ch[now][1],k);
}
void Seg_Before(int now,int L,int R,int s,int t,int k)
{if(s<=L&&R<=t) {Sp_Before(root[now],k);return ;}int mid=(L+R)/2;if(s<=mid) Seg_Before(now*2,L,mid,s,t,k);if(mid+1<=t) Seg_Before(now*2+1,mid+1,R,s,t,k);
}
void Sp_After(int now,int k)
{if(now==0) return ;if(num[now]<=k) Sp_After(ch[now][1],k);else ans=min(ans,num[now]),Sp_After(ch[now][0],k);
}
void Seg_After(int now,int L,int R,int s,int t,int k)
{if(s<=L&&R<=t) {Sp_After(root[now],k);return ;}int mid=(L+R)/2;if(s<=mid) Seg_After(now*2,L,mid,s,t,k);if(mid+1<=t) Seg_After(now*2+1,mid+1,R,s,t,k);
}
int main()
{
//  freopen("a.in","r",stdin);scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&init[i]); Build(1,1,n);int L,R,pos,k;while(m--){scanf("%d",&opt);switch (opt){case 1:{scanf("%d %d %d",&L,&R,&k);ans=0;Seg_Rank(1,1,n,L,R,k);printf("%d\n",ans+1);break;}case 2:{scanf("%d %d %d",&L,&R,&k);printf("%d\n",Kth(L,R,k));break;}case 3:{scanf("%d %d",&pos,&k);Seg_Change(1,1,n,pos,k);init[pos]=k;break;} case 4:{scanf("%d %d %d",&L,&R,&k);ans=-1;Seg_Before(1,1,n,L,R,k);printf("%d\n",ans);break;}case 5:{scanf("%d %d %d",&L,&R,&k);ans=100000000+1;Seg_After(1,1,n,L,R,k);printf("%d\n",ans);break;}}}return 0;
}