这种题没人会帮忙看吧。。。
by watermonster @ 2020-11-14 17:21:39
顶多给个代码
```cpp
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define il inline
#define re register
const int N=5e4+10;
const int inf=1e8;
namespace FastIO
{
char buf[1<<21],buf2[1<<21],*p1=buf,*p2=buf;
int p,p3=-1;
il int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
il void flush(){fwrite(buf2,1,p3+1,stdout),p3=-1;}
#define isdigit(ch) (ch>=48&&ch<=57)
template <typename T>
il void read(T &x)
{
re bool f=0;x=0;
re char ch=getc();
while(!isdigit(ch)) f|=(ch=='-'),ch=getc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getc();
x=f?-x:x;
}
template <typename T>
il void print(T x)
{
if(p3>(1<<20)) flush();
if(x<0) buf2[++p3]=45,x=-x;
re int a[50]={};
do{a[++p]=x%10+48;}while(x/=10);
do{buf2[++p3]=a[p];}while(--p);
buf2[++p3]='\n';
}
}
using namespace FastIO;
int n,m,s[N];
int rt[N<<2],pool;
int bin[N],top;
struct treap
{
int lso,rso,pri,val,siz,cnt;
#define lso(p) t[p].lso
#define rso(p) t[p].rso
#define pri(p) t[p].pri
#define val(p) t[p].val
#define siz(p) t[p].siz
#define cnt(p) t[p].cnt
}t[N<<7];
il int newnode(){return top?bin[top--]:++pool;}
il void update(re int p){siz(p)=siz(lso(p))+siz(rso(p))+cnt(p);}
il void zig(int &p)
{
re int k=lso(p);
lso(p)=rso(k);rso(k)=p;
update(p),update(k);
p=k;return;
}
il void zag(int &p)
{
re int k=rso(p);
rso(p)=lso(k);lso(k)=p;
update(p),update(k);
p=k;return;
}
il void ins(int &p,re int x)
{
if(!p)
{
p=newnode();
lso(p)=rso(p)=0;
siz(p)=cnt(p)=1;
pri(p)=rand();
val(p)=x;return;
}
++siz(p);
if(val(p)==x){++cnt(p);return;}
if(val(p)<x)
{
ins(rso(p),x);
if(pri(p)<pri(rso(p))) zag(p);
}
else
{
ins(lso(p),x);
if(pri(p)<pri(lso(p))) zig(p);
}
return;
}
il void del(int &p,re int x)
{
if(val(p)==x)
{
if(cnt(p)>1) --siz(p),--cnt(p);
else if(!lso(p)||!rso(p)) bin[++top]=p,p=lso(p)|rso(p);
else if(pri(lso(p))<pri(rso(p))) zag(p),del(p,x);
else zig(p),del(p,x);
return;
}
--siz(p);
if(val(p)<x) del(rso(p),x);
else del(lso(p),x);
return;
}
il int qrnk(re int x,re int k)
{
re int p=rt[x],res=0;
while(p)
{
if(val(p)==k) return res+siz(lso(p));
if(val(p)<k) res+=siz(lso(p))+cnt(p),p=rso(p);
else p=lso(p);
}
return res;
}
il int qpre(re int x,re int k)
{
re int p=rt[x],res=-inf;
while(p)
{
if(val(p)<k) res=val(p),p=rso(p);
else p=lso(p);
}
return res;
}
il int qsuc(re int x,re int k)
{
re int p=rt[x],res=inf;
while(p)
{
if(val(p)>k) res=val(p),p=lso(p);
else p=rso(p);
}
return res;
}
struct segtree{int l,r;}st[N<<2];
il void build(re int p,re int l,re int r)
{
st[p]=(segtree){l,r};
if(l==r)return;
re int mid=(l+r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
return;
}
il void erase(re int p,re int x)
{
if(st[p].l>x||st[p].r<x) return;
del(rt[p],s[x]);
if(st[p].l==st[p].r) return;
erase(p<<1,x);erase(p<<1|1,x);
return;
}
il void change(re int p,re int x,re int val)
{
if(st[p].l>x||st[p].r<x) return;
ins(rt[p],val);
if(st[p].l==st[p].r){s[x]=val;return;}
change(p<<1,x,val);change(p<<1|1,x,val);
return;
}
il void queryrnk(re int p,re int l,re int r,re int k,int &tmp)
{
if(st[p].l>r||st[p].r<l) return;
if(st[p].l>=l&&st[p].r<=r){tmp+=qrnk(p,k);return;}
queryrnk(p<<1,l,r,k,tmp);queryrnk(p<<1|1,l,r,k,tmp);
return;
}
il void querypre(re int p,re int l,re int r,re int k,int &tmp)
{
if(st[p].l>r||st[p].r<l) return;
if(st[p].l>=l&&st[p].r<=r){tmp=max(tmp,qpre(p,k));return;}
querypre(p<<1,l,r,k,tmp);querypre(p<<1|1,l,r,k,tmp);
return;
}
il void querysuc(re int p,re int l,re int r,re int k,int &tmp)
{
if(st[p].l>r||st[p].r<l) return;
if(st[p].l>=l&&st[p].r<=r){tmp=min(tmp,qsuc(p,k));return;}
querysuc(p<<1,l,r,k,tmp);querysuc(p<<1|1,l,r,k,tmp);
return;
}
il void querykth(re int p,re int l,re int r,re int k,int &tmp)
{
re int L=0,R=inf,Mid,res=0;
while(L<=R)
{
Mid=(L+R)>>1;
res=0;queryrnk(1,l,r,Mid,res);
if(res<k) L=Mid+1,tmp=Mid;
else R=Mid-1;
}
return;
}
int main()
{
srand(time(NULL));
read(n),read(m);build(1,1,n);
for(re int i=1;i<=n;++i) read(s[i]);
for(re int i=1;i<=n;++i) change(1,i,s[i]);
re int l,r,k,opt,ans;
while(m--)
{
ans=0;read(opt);
if(opt==1)
{
read(l),read(r),read(k);
queryrnk(1,l,r,k,ans);
print(ans+1);
}
if(opt==2)
{
read(l),read(r),read(k);
querykth(1,l,r,k,ans);
print(ans);
}
if(opt==3)
{
read(l),read(k);
erase(1,l);change(1,l,k);
}
if(opt==4)
{
ans=-inf;
read(l),read(r),read(k);
querypre(1,l,r,k,ans);
print(ans);
}
if(opt==5)
{
ans=inf;
read(l),read(r),read(k);
querysuc(1,l,r,k,ans);
print(ans);
}
}
flush();return 0;
}
```
by watermonster @ 2020-11-14 17:23:39
~~代码题解区就有~~
谢谢，我已经找到错误了
by Gary88 @ 2020-11-14 18:33:01