浅拍了五千组数据，实在不知道锅在哪里
- 板块P3380 【模板】二逼平衡树（树套树）
- 楼主Soul_Love
- 当前回复1
- 已保存回复1
- 发布时间2024/1/25 19:54
- 上次更新2024/1/25 21:48:18
查看原帖
被骇客银狼阻止的越权访问保存失败
浅拍了五千组数据，实在不知道锅在哪里
#include<bits/stdc++.h>
#define int long long
#define inf 2147483647
using namespace std;
int n1,m,t1,t2,L1[650],R1[650],L2[650],R2[650],pos1[100010],pos2[100010],a[100010],n2,b[200010],ql1,ql2;
int cnt1[650][650],cnt2[650][200010],ton1[200100],ton2[200100];
/*unordered_*/map<int,int> jyb;
/*unordered_*/map<int,bool> zjp;
inline int read()
{
int k=0,f=0;char c=getchar();
for(;!isdigit(c);c=getchar()) f|=c=='-';
for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
return f?-k:k;
}
struct que
{
int l,r,k,pos,op;
}cq[100100];
inline void add(int x)
{
// printf("!%lld\n",x);
if(zjp[x]==0)
{
zjp[x]=1;
b[++n2]=x;
}
}
inline void lsh()
{
sort(b+1,b+n2+1);
// for(int i=1;i<=n2;i++) printf("%lld\n",b[i]);
// puts("");
for(int i=1;i<=n2;i++) jyb[b[i]]=i;
// for(int i=1;i<=n1;i++) printf("!%lld\n",a[i]);
for(int i=1;i<=n1;i++) a[i]=jyb[a[i]];
// for(int i=1;i<=n1;i++) printf("!%lld\n",a[i]);
}
inline void build1()
{
ql1=sqrt(n1);
t1=n1/ql1;
for(int i=1;i<=t1;i++)
{
L1[i]=R1[i-1]+1;
R1[i]=i*ql1;
}
if(R1[t1]!=n1)
{
t1++;
L1[t1]=R1[t1-1]+1;
R1[t1]=n1;
}
for(int i=1;i<=t1;i++)
{
for(int j=L1[i];j<=R1[i];j++)
{
pos1[j]=i;
}
for(int j=1;j<=R1[i];j++) cnt2[i][a[j]]++;
}
}
inline void build2()
{
ql2=sqrt(n2);
t2=n2/ql2;
for(int i=1;i<=t2;i++)
{
L2[i]=R2[i-1]+1;
R2[i]=i*ql2;
}
if(R2[t2]!=n2)
{
t2++;
L2[t2]=R2[t2-1]+1;
R2[t2]=n2;
}
for(int i=1;i<=t2;i++)
{
for(int j=L2[i];j<=R2[i];j++)
{
pos2[j]=i;
}
}
for(int i=1;i<=t1;i++)
{
for(int j=1;j<=R1[i];j++)
{
cnt1[i][pos2[a[j]]]++;
}
}
}
inline void update(int k,int x)
{
for(int i=pos1[k];i<=t1;i++)
{
cnt2[i][a[k]]--;
cnt1[i][pos2[a[k]]]--;
}
a[k]=x;
for(int i=pos1[k];i<=t1;i++)
{
cnt2[i][a[k]]++;
cnt1[i][pos2[a[k]]]++;
}
}
inline int get_pre(int l,int r,int k)
{
int q1=pos1[l],p1=pos1[r],ans=-inf;
k--;
if(q1==p1)
{
for(int i=l;i<=r;i++)
{
// printf("!%lld %lld %lld\n",a[i],ans,k);
if(a[i]<=k) ans=max(ans,a[i]);
}
return ans>0?b[ans]:ans;
}
for(int i=l;i<=R1[q1];i++) if(a[i]<=k) ans=max(ans,a[i]);
for(int i=L1[p1];i<=r;i++) if(a[i]<=k) ans=max(ans,a[i]);
// printf("!%lld\n",ans);
for(int i=k;i>=L2[pos2[k]];i--)
{
if(cnt2[p1-1][i]-cnt2[q1][i])
{
ans=max(ans,i);
break;
}
}
for(int i=pos2[k]-1;i>0;i--)
{
int flag=0;
// printf("!");
if(cnt1[p1-1]-cnt1[q1])
{
for(int j=R2[i];j>=L2[i];j--)
{
if(cnt2[p1-1][j]-cnt2[q1][j])
{
ans=max(ans,j);
flag=1;
break;
}
}
}
if(flag) break;
}
return ans>0?b[ans]:ans;
}
inline int get_nxt(int l,int r,int k)
{
int q1=pos1[l],p1=pos1[r],ans=inf;
k++;
if(q1==p1)
{
for(int i=l;i<=r;i++)
{
// printf("!%lld %lld %lld\n",a[i],ans,k);
if(a[i]>=k) ans=min(ans,a[i]);
}
return ans!=inf?b[ans]:ans;
}
for(int i=l;i<=R1[q1];i++) if(a[i]>=k) ans=min(ans,a[i]);
for(int i=L1[p1];i<=r;i++) if(a[i]>=k) ans=min(ans,a[i]);
// printf("!%lld\n",ans);
for(int i=k;i<=R2[pos2[k]];i++)
{
if(cnt2[p1-1][i]-cnt2[q1][i])
{
ans=min(ans,i);
break;
}
}
for(int i=pos2[k]+1;i<=t2;i++)
{
int flag=0;
// printf("!");
if(cnt1[p1-1]-cnt1[q1])
{
for(int j=L2[i];j<=R2[i];j++)
{
if(cnt2[p1-1][j]-cnt2[q1][j])
{
ans=min(ans,j);
flag=1;
break;
}
}
}
if(flag) break;
}
return ans!=inf?b[ans]:ans;
}
inline int get_rank(int l,int r,int k)
{
int q1=pos1[l],p1=pos1[r],ans=1;
k--;
if(q1==p1)
{
for(int i=l;i<=r;i++) if(a[i]<=k) ans++;
return ans;
}
for(int i=l;i<=R1[q1];i++) if(a[i]<=k) ans++;
for(int i=L1[p1];i<=r;i++) if(a[i]<=k) ans++;
for(int i=L2[pos2[k]];i<=k;i++) ans+=cnt2[p1-1][i]-cnt2[q1][i];
for(int i=1;i<pos2[k];i++) ans+=cnt1[p1-1][i]-cnt1[q1][i];
return ans;
}
inline int get_kth(int l,int r,int k)
{
int q1=pos1[l],p1=pos1[r];
if(q1==p1)
{
for(int i=l;i<=r;i++)
{
ton1[pos2[a[i]]]++;
ton2[a[i]]++;
}
for(int i=1;i<=t2;i++)
{
if(k-ton1[i]<=0)
{
for(int j=L2[i];j<=R2[i];j++)
{
k-=ton2[j];
if(k<=0)
{
for(int w=l;w<=r;w++)
{
ton1[pos2[a[w]]]--;
ton2[a[w]]--;
}
return b[j];
}
}
}
k-=ton1[i];
}
}
for(int i=l;i<=R1[q1];i++)
{
ton1[pos2[a[i]]]++;
ton2[a[i]]++;
}
for(int i=L1[p1];i<=r;i++)
{
ton1[pos2[a[i]]]++;
ton2[a[i]]++;
}
for(int i=1;i<=t2;i++)
{
if(k-cnt1[p1-1][i]+cnt1[q1][i]-ton1[i]<=0)
{
for(int j=L2[i];i<=R2[i];j++)
{
k-=cnt2[p1-1][j]-cnt2[q1][j]+ton2[j];
if(k<=0)
{
for(int w=l;w<=R1[q1];w++)
{
ton1[pos2[a[w]]]--;
ton2[a[w]]--;
}
for(int w=L1[p1];w<=r;w++)
{
ton1[pos2[a[w]]]--;
ton2[a[w]]--;
}
return b[j];
}
}
}
k-=cnt1[p1-1][i]-cnt1[q1][i]+ton1[i];
}
return 1;
}
inline void check_a()
{
for(int i=1;i<=n1;i++) printf("%lld ",a[i]);
puts("");
}
inline void check_cnt1()
{
for(int i=1;i<=t1;i++)
{
for(int j=1;j<=t2;j++)
{
printf("%lld ",cnt1[i][j]);
}
puts("");
}
}
inline void check_cnt2()
{
for(int i=1;i<=t1;i++)
{
for(int j=1;j<=n2;j++)
{
printf("%lld ",cnt2[i][j]);
}
puts("");
}
}
inline void check_b()
{
for(int i=1;i<=n2;i++) printf("%lld ",b[i]);
puts("");
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n1=read(),m=read();
for(int i=1;i<=n1;i++)
{
a[i]=read();
add(a[i]);
}
for(int i=1;i<=m;i++)
{
cq[i].op=read();
if(cq[i].op==3) cq[i].pos=read(),cq[i].k=read();
else cq[i].l=read(),cq[i].r=read(),cq[i].k=read();
add(cq[i].k);
add(cq[i].k+1);
add(cq[i].k-1);
}
lsh();
build1();
build2();
// check_b();
for(int i=1;i<=m;i++)
{
// check_a();
// check_cnt1();
// check_cnt2();
if(cq[i].op==1) printf("%lld\n",get_rank(cq[i].l,cq[i].r,jyb[cq[i].k]));
else if(cq[i].op==2) printf("%lld\n",get_kth(cq[i].l,cq[i].r,cq[i].k));
else if(cq[i].op==3) update(cq[i].pos,jyb[cq[i].k]);
else if(cq[i].op==4) printf("%lld\n",get_pre(cq[i].l,cq[i].r,jyb[cq[i].k]));
else printf("%lld\n",get_nxt(cq[i].l,cq[i].r,jyb[cq[i].k]));
}
return 0;
}
/*
10 5
4 10 5 4 2 7 10 5 2 2
1 1 7 7
1 3 5 6
3 5 1
3 7 4
5 9 10 6
*/
/*
0 1 2 3 4 5 6 7 8 10
1 2 3 4 5 6 7 8 9 10
5 10 6 5 3 8 10 6 3 3
*/
加载中...