```cpp
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define ull unsigned long long
#define ll long long
#define inf 50009
#define INF 2000003
#define int_max 2147483647
#define int_min -2147483647
#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}
using namespace std;
int arr[inf];
int n;
struct Spaly{
int son[2];
int f,siz,fqc;
int val;
}t[INF];
int sp_cnt;
int rt[INF];
inline void SP_pushup(int x){
t[x].siz=t[x].fqc+t[t[x].son[0]].siz+t[t[x].son[1]].siz;
return;
}
inline void SP_rotate(int u,int p){
register int v=t[u].f;
t[v].son[!p]=t[u].son[p];
t[t[u].son[p]].f=v;
t[u].f=t[v].f;
if (t[u].f){
t[t[u].f].son[t[t[u].f].son[1]==v]=u;
}
t[u].son[p]=v;
t[v].f=u;
SP_pushup(v);
SP_pushup(u);
return;
}
inline void SP_splay(int rid,int u,int to){
while(t[u].f!=to){
if (t[t[u].f].f==to){
SP_rotate(u,t[t[u].f].son[0]==u);
}
else{
register int f=t[u].f,grandf=t[f].f;
register int p=(t[grandf].son[0]==f);
if (t[f].son[p]==u){
SP_rotate(u,!p);
SP_rotate(u,p);
}
else{
SP_rotate(f,p);
SP_rotate(u,p);
}
}
}
if (to==0){
rt[rid]=u;
}
return;
}
inline void SP_newtree(int v,int x){
t[x].val=v;
t[x].siz=t[x].fqc=1;
t[x].son[1]=t[x].son[0]=0;
t[x].f=0;
return;
}
inline void SP_insert(int rid,int v,int x){
register int u=rt[rid];
if (!u){
SP_newtree(v,x);
rt[rid]=x;
return;
}
while (u){
if (t[u].val==v){
t[u].siz++,t[u].fqc++;
SP_splay(rid,u,0);
return;
}
else if (t[u].val<v){
if (!t[u].son[1]){
SP_newtree(v,x);
t[u].son[1]=x;
t[x].f=u;
break;
}
else{
u=t[u].son[1];
}
}
else{
if (!t[u].son[0]){
SP_newtree(v,x);
t[u].son[0]=x;
t[x].f=u;
break;
}
else{
u=t[u].son[0];
}
}
}
SP_splay(rid,x,0);
return;
}
inline int SP_rank(int rid,int k){
register int u=rt[rid],ans=0;
while (u){
if (t[u].val==k){
ans+=t[t[u].son[0]].siz;
break;
}
else if (k<t[u].val){
u=t[u].son[0];
}
else{
ans+=t[u].fqc+t[t[u].son[0]].siz;
u=t[u].son[1];
}
}
return ans;
}
inline int SP_find(int root,int x){
register int u=root;
while (u){
if (t[u].val==x){
return u;
}
else if (x<t[u].val){
u=t[u].son[0];
}
else{
u=t[u].son[1];
}
}
return -1;
}
inline int SP_findmax(int u){
while (t[u].son[1]){
u=t[u].son[1];
}
return u;
}
inline void SP_change(int rid,int x,int y){
register int u=SP_find(rt[rid],x);
SP_splay(rid,u,0);
if (t[u].fqc>1){
t[u].fqc--;
}
else if (t[u].siz==1){
rt[rid]=0;
}
else{
if (!t[u].son[0]){
rt[rid]=t[u].son[1];
t[t[u].son[1]].f=0;
}
else if (!t[u].son[1]){
rt[rid]=t[u].son[0];
t[t[u].son[0]].f=0;
}
else{
SP_splay(rid,SP_findmax(t[u].son[0]),u);
register int newr=t[u].son[0];
t[newr].son[1]=t[u].son[1];
t[t[u].son[1]].f=newr;
t[newr].f=0;
rt[rid]=newr;
SP_pushup(newr);
}
}
if (t[u].fqc){
SP_insert(rid,y,++sp_cnt);
}
else{
SP_insert(rid,y,u);
}
return;
}
inline int SP_getnext(int rid,int x){
register int u=rt[rid],ans=int_max;
while (u){
if (x<t[u].val){
ans=min(ans,t[u].val);
u=t[u].son[0];
}
else{
u=t[u].son[1];
}
}
return ans;
}
inline int SP_getlast(int rid,int x){
register int u=rt[rid],ans=int_min;
while (u){
if (x<=t[u].val){
u=t[u].son[0];
}
else {
ans=max(ans,t[u].val);
u=t[u].son[1];
}
}
return ans;
}
inline void ST_bulid(int u,int l,int r){
for (int i=l;i<=r;i++){
SP_inser…
```
by ezoixx118 @ 2017-11-26 19:31:48
代码下半段：
```cpp
inline void ST_bulid(int u,int l,int r){
for (int i=l;i<=r;i++){
SP_insert(u,arr[i],++sp_cnt);
}
register int mid=(l+r)>>1;
if (l!=r){
ST_bulid(u<<1,l,mid);
ST_bulid(u<<1|1,mid+1,r);
}
return;
}
inline int ST_rank(int u,int l,int r,int x,int y,int k){
if (x<=l && r<=y){
return SP_rank(u,k);
}
register int ans=0,mid=(l+r)>>1;
if (x<=mid){
ans+=ST_rank(u<<1,l,mid,x,y,k);
}
if (y>mid){
ans+=ST_rank(u<<1|1,mid+1,r,x,y,k);
}
return ans;
}
inline int Binary_Search(int x,int y,int k){
int l=0,r=(int)1e8+1;
while (l<r){
register int mid=(l+r)>>1;
if (ST_rank(1,1,n,x,y,mid)<k){
l=mid+1;
}
else{
r=mid;
}
}
return l-1;
}
inline void ST_change(int u,int l,int r,int x,int v){
SP_change(u,arr[x],v);
if (l==r){
arr[x]=v;
return;
}
register int mid=(l+r)>>1;
if (x<=mid){
ST_change(u<<1,l,mid,x,v);
}
else{
ST_change(u<<1|1,mid+1,r,x,v);
}
return;
}
inline int ST_last(int u,int l,int r,int x,int y,int k){
if (x<=l && r<=y){
return SP_getlast(u,k);
}
register int ans=int_min,mid=(l+r)>>1;
if (x<=mid){
ans=max(ans,ST_last(u<<1,l,mid,x,y,k));
}
if (y>mid){
ans=max(ans,ST_last(u<<1|1,mid+1,r,x,y,k));
}
return ans;
}
inline int ST_next(int u,int l,int r,int x,int y,int k){
if (x<=l && r<=y){
return SP_getnext(u,k);
}
register int ans=int_max,mid=(l+r)>>1;
if (x<=mid){
ans=min(ans,ST_next(u<<1,l,mid,x,y,k));
}
if (y>mid){
ans=min(ans,ST_next(u<<1|1,mid+1,r,x,y,k));
}
return ans;
}
inline void wr(int x){
if(x<0){
putchar('-'),x=-x;
}
if(x>9){
wr(x/10);
}
putchar(x%10+'0');
return;
}
int main(){
int m;
rd(n);rd(m);
for (register int i=1;i<=n;i++){
rd(arr[i]);
}
ST_bulid(1,1,n);
int p,x,y,k;
for (register int i=1;i<=m;i++){
rd(p);
if (p==1){
rd(x);rd(y);rd(k);
wr(ST_rank(1,1,n,x,y,k)+1);
putchar('\n');
}
else if (p==2){
rd(x);rd(y);rd(k);
wr(Binary_Search(x,y,k));
putchar('\n');
}
else if (p==3){
rd(x);rd(k);
ST_change(1,1,n,x,k);
}
else if (p==4){
rd(x);rd(y);rd(k);
wr(ST_last(1,1,n,x,y,k));
putchar('\n');
}
else{
rd(x);rd(y);rd(k);
wr(ST_next(1,1,n,x,y,k));
putchar('\n');
}
}
return 0;
}
```
by ezoixx118 @ 2017-11-26 19:33:36
您听说过大牛分站吗
by wjy666 @ 2017-11-26 20:59:07
@[wjy666](/space/show?uid=20821) 然后呢
by ezoixx118 @ 2017-11-27 18:53:14
@[ezoixx118](/space/show?uid=30541) 大牛分站开O2优化
by wjy666 @ 2017-11-27 19:12:09
@[wjy666](/space/show?uid=20821) 啊!谢谢，卡过去了。。
by ezoixx118 @ 2017-11-28 18:54:35