3196:Tyvj 1730二強制平衡樹線分樹セットバランスツリー

13586 ワード

前回の問題を見た時は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; }