3196:Tyvj 1730二強制平衡樹線分樹セットバランスツリー
前回の問題を見た時は2.4時間でした.本当に感動しました.WCから帰ってきてからずっと退廃しているようです.休みの最後の日に、いくつかの問題を書いて心を閉ざすことにしました.朝からデータ構造に驚きました.線分の木のセットのバランスが取れています.きっと私の姿勢が悪いです.遅いです.
#include
#include
#include
#define N 50005
#define M 3000005
#define inf 1000000007
using namespace std;
int n,m,cnt,tmp;
int a[N],l[N<<2],r[N<<2],root[N<<2];
int ls[M],rs[M],rnd[M],size[M],sum[M],v[M];
inline int read()
{
int a=0,f=1; char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
return a*f;
}
inline void pushup(int k)
{
size[k]=size[ls[k]]+size[rs[k]]+sum[k];
}
inline void lturn(int &k)
{
int t=rs[k]; rs[k]=ls[t]; ls[t]=k; pushup(k); pushup(t); k=t;
}
inline void rturn(int &k)
{
int t=ls[k]; ls[k]=rs[t]; rs[t]=k; pushup(k); pushup(t); k=t;
}
void insert(int &k,int num)
{
if (!k)
{
k=++cnt;
size[k]=sum[k]=1;
v[k]=num;
rnd[k]=rand();
return;
}
size[k]++;
if (num==v[k]) sum[k]++;
else if (numif (rnd[ls[k]]else
{
insert(rs[k],num);
if (rnd[rs[k]]void pre(int k,int x,int y)
{
l[k]=x; r[k]=y;
if (l[k]==r[k]) return;
int mid=l[k]+r[k]>>1;
pre(k<<1,x,mid); pre(k<<1|1,mid+1,y);
}
void build(int k,int id,int num)
{
insert(root[k],num);
if (l[k]==r[k]) return;
int mid=l[k]+r[k]>>1;
if (id<=mid) build(k<<1,id,num);
else build(k<<1|1,id,num);
}
inline void ask_rank(int k,int num)
{
if (!k) return;
if (num==v[k]) {tmp+=size[ls[k]]; return;}
else if (numelse {tmp+=size[ls[k]]+sum[k]; ask_rank(rs[k],num);}
}
inline void get_rank(int k,int x,int y,int num)
{
if (l[k]==x&&r[k]==y)
{
ask_rank(root[k],num);
return;
}
int mid=l[k]+r[k]>>1;
if (y<=mid) get_rank(k<<1,x,y,num);
else if (x>mid) get_rank(k<<1|1,x,y,num);
else get_rank(k<<1,x,mid,num),get_rank(k<<1|1,mid+1,y,num);
}
inline void get_index(int x,int y,int z)
{
int l=0,r=inf,ans;
while (l<=r)
{
int mid=l+r>>1;
tmp=1;
get_rank(1,x,y,mid);
if (tmp<=z) ans=mid,l=mid+1; else r=mid-1;
}
printf("%d
",ans);
}
void del(int &k,int num)
{
if (v[k]==num)
{
if (sum[k]>1) {sum[k]--; size[k]--; return;}
if (ls[k]*rs[k]==0) k=ls[k]+rs[k];
else if (rnd[ls[k]]else lturn(k),del(k,num);
}
else if (numelse del(rs[k],num),size[k]--;
}
inline void change(int k,int x,int num,int y)
{
del(root[k],y);
insert(root[k],num);
if (l[k]==r[k]) return;
int mid=l[k]+r[k]>>1;
if (x<=mid) change(k<<1,x,num,y);
else change(k<<1|1,x,num,y);
}
void before(int k,int num)
{
if (!k) return;
if (v[k]else before(ls[k],num);
}
void after(int k,int num)
{
if (!k) return;
if (v[k]>num) tmp=min(v[k],tmp),after(ls[k],num);
else after(rs[k],num);
}
void ask_after(int k,int x,int y,int num)
{
if (l[k]==x&&r[k]==y)
{
after(root[k],num);
return;
}
int mid=l[k]+r[k]>>1;
if (y<=mid) ask_after(k<<1,x,y,num);
else if (x>mid) ask_after(k<<1|1,x,y,num);
else ask_after(k<<1,x,mid,num),ask_after(k<<1|1,mid+1,y,num);
}
void ask_before(int k,int x,int y,int num)
{
if (l[k]==x&&r[k]==y)
{
before(root[k],num);
return;
}
int mid=l[k]+r[k]>>1;
if (y<=mid) ask_before(k<<1,x,y,num);
else if (x>mid) ask_before(k<<1|1,x,y,num);
else ask_before(k<<1,x,mid,num),ask_before(k<<1|1,mid+1,y,num);
}
int main()
{
n=read(); m=read();
pre(1,1,n);
for (int i=1;i<=n;i++) a[i]=read(),build(1,i,a[i]);;
for (int i=1;i<=m;i++)
{
int opt=read();
int x=read(),y=read(),k;
switch (opt)
{
case 1:
k=read(); tmp=1;
get_rank(1,x,y,k);
printf("%d
",tmp);
break;
case 2:
k=read();
get_index(x,y,k);
break;
case 3:
change(1,x,y,a[x]);
a[x]=y;
break;
case 4:
k=read(); tmp=0;
ask_before(1,x,y,k);
printf("%d
",tmp);
break;
case 5:
k=read(); tmp=inf;
ask_after(1,x,y,k);
printf("%d
",tmp);
break;
}
}
return 0;
}