Loading...

洛谷P2617 Dynamic Rankings

check评论:0 条 remove_red_eye浏览量:496 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-17

qwq这道题数据加强了,然而我不会$O(n\ log^2n)$的树状数组套主席树,就只能写$O(n\ log^3n)$的线段树套$splay$很明显$TLE$了

但是我会树套树啦qwq

我们线段树的每个结点都是一个$splay$,代表当前区间的$splay$,然后就很简单啦qwq

树套树难调试的要死啊QAQ

#include <bits/stdc++.h>
using namespace std;
#define maxn 8000010
int key[maxn],f[maxn],ch[maxn][2],siz[maxn],cnt[maxn],rt[maxn],tot,a[maxn>>5];
int n,m,maxnn=-0x3f3f3f3f;
map<int,int> mp;
void clear(int x)
{
    key[x]=f[x]=ch[x][0]=ch[x][1]=siz[x]=cnt[x]=0;
}
void update(int x)
{
    if(x)
    {
        siz[x]=cnt[x];
        if(ch[x][0])
        {
            siz[x]+=siz[ch[x][0]];
        }
        if(ch[x][1])
        {
            siz[x]+=siz[ch[x][1]];
        }
    }
}
int get(int x)
{
    return ch[f[x]][1]==x;
}
void rotate(int x)
{
    int old=f[x],oldf=f[old],which=get(x);
    ch[old][which]=ch[x][which^1];
    f[ch[old][which]]=old;
    ch[x][which^1]=old;
    f[old]=x;
    f[x]=oldf;
    if(oldf)
    {
        ch[oldf][old==ch[oldf][1]]=x;
    }
    update(old);
    update(x);
}
void splay(int i,int x)
{
    for(int fa;fa=f[x];rotate(x))
    {
        if(f[fa])
        {
            rotate(get(fa)==get(x)?fa:x);
        }
    }
    rt[i]=x;
}
void ins(int i,int x)
{
    if(!rt[i])
    {
        rt[i]=++tot;
        clear(tot);
        key[tot]=x;
        cnt[tot]=siz[tot]=1;
        update(tot);
        return ;
    }
    int now=rt[i],fa=0;
    while(1)
    {
        if(key[now]==x)
        {
            cnt[now]++;
            update(now);
            update(fa);
            splay(i,now);
            return ;
        }
        fa=now;
        now=ch[now][key[now]<x];
        if(!now)
        {
            tot++;
            clear(tot);
            key[tot]=x;
            cnt[tot]=siz[tot]=1;
            f[tot]=fa;
            ch[fa][key[fa]<x]=tot;
            update(fa);
            splay(i,tot);
            return ;
        }
    }
}
int pre(int i)
{
    int now=ch[rt[i]][0];
    while(ch[now][1])
    {
        now=ch[now][1];
    }
    return now;
}
int suc(int i)
{
    int now=ch[rt[i]][1];
    while(ch[now][0])
    {
        now=ch[now][0];
    }
    return now;
}
int find(int i,int x)
{
    int now=rt[i],ans=0;
    while(now)
    {
        if(x<key[now])
        {
            now=ch[now][0];
            continue;
        }
        ans+=(ch[now][0]?siz[ch[now][0]]:0);
        if(x==key[now])
        {
            splay(i,now);
            return ans;
        }
        ans+=cnt[now];
        now=ch[now][1];
    }
    return ans;
}
void del(int i,int x)
{
    find(i,x);
    if(cnt[rt[i]]>1)
    {
        cnt[rt[i]]--;
        update(rt[i]);
        return ;
    }
    if(!ch[rt[i]][0]&&!ch[rt[i]][1])
    {
        clear(rt[i]);
        rt[i]=0;
        return ;
    }
    if(!ch[rt[i]][0])
    {
        int old=rt[i];
        rt[i]=ch[old][1];
        f[ch[old][1]]=0;
        clear(old);
        return ;
    }
    if(!ch[rt[i]][1])
    {
        int old=rt[i];
        rt[i]=ch[old][0];
        f[ch[old][0]]=0;
        clear(old);
        return ;
    }
    int qwq=pre(i),old=rt[i];
    splay(i,qwq);
    ch[qwq][1]=ch[old][1];
    f[ch[qwq][1]]=qwq;
    clear(old);
    update(rt[i]);
}
void segins(int o,int lf,int rg,int w,int x)
{
    ins(o,x);
    if(lf==rg)
    {
        return ;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        segins(o<<1,lf,mid,w,x);
    }
    else
    {
        segins(o<<1|1,mid+1,rg,w,x);
    }
}
void segdel(int o,int lf,int rg,int w,int x)
{
    del(o,x);
    if(lf==rg)
    {
        return ;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        segdel(o<<1,lf,mid,w,x);
    }
    else
    {
        segdel(o<<1|1,mid+1,rg,w,x);
    }
}
int segq(int o,int lf,int rg,int l,int r,int x)
{
    if(l<=lf&&rg<=r)
    {
        return find(o,x);
    }    
    int ans=0;
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        ans+=segq(o<<1,lf,mid,l,r,x);
    }
    if(mid<r)
    {
        ans+=segq(o<<1|1,mid+1,rg,l,r,x);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        maxnn=max(maxnn,a[i]);
        segins(1,1,n,i,a[i]);
    }
    char opt[10];
    int l,r,x;
    for(int i=1;i<=m;i++)
    {
        scanf("%s%d%d",opt,&l,&r);
        if(opt[0]=='Q')
        {
            scanf("%d",&x);
            int lf=0,rg=maxnn+1;
            while(lf<rg)
            {
                int mid=(lf+rg)>>1;
                int k=segq(1,1,n,l,r,mid);
                if(k>=x)
                {
                    rg=mid;
                }
                else
                {
                    lf=mid+1;
                }
            }
            printf("%d\n",lf-1);
        }
        else
        {
            segdel(1,1,n,l,a[l]);
            segins(1,1,n,l,r);
            maxnn=max(maxnn,r);
            a[l]=r;
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名