MnZn求助，分块做法，一二类询问跨块时有问题，求调qwq
- 板块P3380 【模板】二逼平衡树（树套树）
- 楼主NATURAL6
- 当前回复0
- 已保存回复0
- 发布时间2022/10/7 22:01
- 上次更新2023/10/27 08:14:30
查看原帖
被骇客银狼阻止的越权访问保存失败
MnZn求助，分块做法，一二类询问跨块时有问题，求调qwq
#include<bits/stdc++.h>
using namespace std;
const int cl=320;
inline int qread()
{
register int a=0;register char ch=getchar();
while(ch>'9'||ch<'0'){ch=getchar();}
while(ch>='0'&&ch<='9'){(a*=10)+=(ch^48);ch=getchar();}
return a;
}
int n,m,a[50010],b[100010],s[100010],sum[320],sss;
int c[100010],st[320],ed[320],cs[250][100010],csum[250][320];
struct cz
{
int op,l,r,k;
}q[50010];
inline void Q1(register int l,register int r,register int k)
{
int ans=0;
if(c[l]==c[r])
{
for(register int i=l;i<=r;++i)ans+=(a[i]<k);
cout<<ans+1<<endl;
return ;
}
else
{
for(register int i=l;i<=ed[c[l]];++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
for(register int i=1;i<c[k];++i)ans+=sum[i]+csum[c[r]-1][i]-csum[c[l]][i];
for(register int i=st[c[k]];i<k;++i)ans+=s[i]+cs[c[r]-1][i]-cs[c[l]][i];
cout<<ans+1<<endl;
for(register int i=l;i<=ed[c[l]];++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
return ;
}
return ;
}
inline void Q2(register int l,register int r,register int k)
{
int cnt=0,pos=1;
if(c[l]==c[r])
{
for(register int i=l;i<=r;++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
while(cnt+sum[pos]<k&&pos<=c[100000])cnt+=sum[pos],++pos;
pos=st[pos];
while(cnt+s[pos]<k&&pos<=100000)cnt+=s[pos],++pos;
cout<<b[pos]-1<<endl;
for(register int i=l;i<=r;++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
return ;
}
else
{
for(register int i=l;i<=ed[c[l]];++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
while(cnt+sum[pos]+csum[c[r]-1][pos]-csum[c[l]][pos]<k&&pos<=c[100000])cnt+=sum[pos]+csum[c[r]-1][pos]-csum[c[l]][pos],++pos;
pos=st[pos];
while(cnt+s[pos]+cs[c[r]-1][pos]-cs[c[l]][pos]<k&&pos<=100000)cnt+=s[pos]+cs[c[r]-1][pos]-cs[c[l]][pos],++pos;
cout<<b[pos]-1<<endl;
for(register int i=l;i<=ed[c[l]];++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
return ;
}
return ;
}
inline void U(register int pos,register int k)
{
int p=c[pos];
while(p<=c[n])
{
--cs[p][a[pos]];
--csum[p][c[a[pos]]];
++cs[p][k];
++csum[p][c[k]];
++p;
}
a[pos]=k;
return ;
}
inline void Q3(register int l,register int r,register int k)
{
int pos=k-1,op=0;
if(c[l]==c[r])
{
for(register int i=l;i<=r;++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
while(pos>=st[c[k]])
{
if(s[pos])
{
op=1;
cout<<b[pos]-1<<endl;
break;
}
pos--;
}
if(!op)
{
pos=c[k]-1;
while(!sum[pos]&&pos)pos--;
if(!pos)cout<<-2147483647<<endl;
else
{
pos=ed[pos];
while(!s[pos]&&pos)pos--;
cout<<b[pos]-1<<endl;
}
}
for(register int i=l;i<=r;++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
}
else
{
for(register int i=l;i<=ed[c[l]];++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
while(pos>=st[c[k]])
{
if(s[pos]+cs[c[r]-1][pos]-cs[c[l]][pos])
{
op=1;
cout<<b[pos]-1<<endl;
break;
}
pos--;
}
if(!op)
{
pos=c[k]-1;
while(!(sum[pos]+csum[c[r]-1][pos]-csum[c[l]][pos])&&pos)pos--;
if(!pos)cout<<-2147483647<<endl;
else
{
pos=ed[pos];
while(!(s[pos]+cs[c[r]-1][pos]-cs[c[l]][pos])&&pos)pos--;
cout<<b[pos]-1<<endl;
}
}
for(register int i=l;i<=ed[c[l]];++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
}
return ;
}
inline void Q4(register int l,register int r,register int k)
{
int pos=k+1,op=0;
if(c[l]==c[r])
{
for(register int i=l;i<=r;++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
while(pos<=ed[c[k]])
{
if(s[pos])
{
op=1;
cout<<b[pos]-1<<endl;
break;
}
pos++;
}
if(!op)
{
pos=c[k]+1;
while(!sum[pos]&&pos<=c[100000])pos++;
if(pos>c[100000])cout<<2147483647<<endl;
else
{
pos=st[pos];
while(!s[pos]&&pos<=100000)pos++;
cout<<b[pos]-1<<endl;
}
}
for(register int i=l;i<=r;++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
}
else
{
for(register int i=l;i<=ed[c[l]];++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
++s[a[i]];
++sum[c[a[i]]];
}
while(pos<=ed[c[k]])
{
if(s[pos]+cs[c[r]-1][pos]-cs[c[l]][pos])
{
op=1;
cout<<b[pos]-1<<endl;
break;
}
pos++;
}
if(!op)
{
pos=c[k]+1;
while(!(sum[pos]+csum[c[r]-1][pos]-csum[c[l]][pos])&&pos<=c[100000])pos++;
if(pos>c[100000])cout<<2147483647<<endl;
else
{
pos=st[pos];
while(!(s[pos]+cs[c[r]-1][pos]-cs[c[l]][pos])&&pos<=100000)pos++;
cout<<b[pos]-1<<endl;
}
}
for(register int i=l;i<=ed[c[l]];++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
for(register int i=st[c[r]];i<=r;++i)
{
--s[a[i]];
--sum[c[a[i]]];
}
}
return ;
}
int main()
{
// freopen("P3380_1.in","r",stdin);
// freopen("1.out","w",stdout);
n=qread();
m=qread();
b[0]=n;
for(register int i=1;i<=n;++i)b[i]=a[i]=qread()+1;
for(register int i=1;i<=100001;++i)
{
c[i]=(i-1)/cl+1;
ed[c[i]]=i;
}
for(register int i=100001;i;--i)st[c[i]]=i;
for(register int i=1;i<=m;++i)
{
q[i].op=qread();
if(q[i].op==1)
{
q[i].l=qread();
q[i].r=qread();
q[i].k=qread()+1;
b[++b[0]]=q[i].k;
}
if(q[i].op==2)
{
q[i].l=qread();
q[i].r=qread();
q[i].k=qread();
}
if(q[i].op==3)
{
q[i].l=qread();
q[i].k=qread()+1;
b[++b[0]]=q[i].k;
}
if(q[i].op==4)
{
q[i].l=qread();
q[i].r=qread();
q[i].k=qread()+1;
b[++b[0]]=q[i].k;
}
if(q[i].op==5)
{
q[i].l=qread();
q[i].r=qread();
q[i].k=qread()+1;
b[++b[0]]=q[i].k;
}
}
sort(b+1,b+1+b[0]);
b[0]=unique(b+1,b+1+b[0])-b-1;
for(register int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+b[0],a[i])-b;
for(register int i=1;i<=c[n];++i)
{
for(register int j=st[i];j<=ed[i];++j)
{
++s[a[j]];
++sum[c[a[j]]];
}
memcpy(cs[i],s,sizeof(s));
memcpy(csum[i],sum,sizeof(sum));
}
memset(s,0,sizeof(s));
memset(sum,0,sizeof(sum));
for(register int i=1;i<=m;++i)
{
if(q[i].op==1)
{
q[i].k=lower_bound(b+1,b+1+b[0],q[i].k)-b;
Q1(q[i].l,q[i].r,q[i].k);
}
if(q[i].op==2)Q2(q[i].l,q[i].r,q[i].k);
if(q[i].op==3)
{
q[i].k=lower_bound(b+1,b+1+b[0],q[i].k)-b;
U(q[i].l,q[i].k);
a[q[i].l]=q[i].k;
}
if(q[i].op==4)
{
q[i].k=lower_bound(b+1,b+1+b[0],q[i].k)-b;
Q3(q[i].l,q[i].r,q[i].k);
}
if(q[i].op==5)
{
q[i].k=lower_bound(b+1,b+1+b[0],q[i].k)-b;
Q4(q[i].l,q[i].r,q[i].k);
}
}
return 0;
}
加载中...