【bzoj3065】带插入区间K小值

2015.06.11 11:40 Thu | 10次阅读 | 旧日oi | 固定链接 | 源码

题目大意:见题目名称……
原序列长度 <= 35000
插入个数 <= 35000,修改个数 <= 70000,查询个数 <= 70000  ,0 <= 每时每刻的权值 <= 70000
题解
先膜vfk!
如果不带插入不带修改,主席树解决,如果带上修改,套个树状数组就行了。
如果带上插入,就要用到替罪羊树套主席树了。
替罪羊树的使用方式类似treap,但是不旋转,如果太不平衡了就暴力重建一下。
具体实现:
修改:这个好说,把从替罪羊树中根到这个节点的路径上的线段树更新一下就好log^2n;
插入的话也是把根到新的点的路径上的点都更新,然后如果不平衡了,需要重建的点的所有子节点的线段树和节点本身,然后暴力重构。
查询就是把所有要用到的线段树拎出来然后二分查找就行。
总时间复杂度nlog^2n.

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10000005
#define M 70000
#define alpha 0.8
using namespace std;
int tot,root,cnt,del_num,flag,tmp,sz,tot2;
int d[N],ls[N],rs[N],val[N],siz[N],rt[N],d2[N];
int c[M+5],A[M+5],B[M+5],cnt1,cnt2;
struct node{
    int sum,l,r;
}a[N];
void reuse(int &x)
{
    if(!x) return;
    d[++tot]=x;
    reuse(a[x].l);reuse(a[x].r);
    a[x].sum=0;x=0;
}
void insert(int &x,int l,int r,int pos,int k)
{
    if(!x) x=tot?d[tot--]:++sz;
    a[x].sum+=k;
    if(!a[x].sum)
    {
        reuse(x);
        return;
    }
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) insert(a[x].l,l,mid,pos,k);
    else insert(a[x].r,mid+1,r,pos,k);
}
void build(int &x,int l,int r)
{
    if(l>r) return;
    x=tot2?d2[tot2--]:++cnt;
    int mid=(l+r)>>1;siz[x]=r-l+1;val[x]=c[mid];
    build(ls[x],l,mid-1);build(rs[x],mid+1,r);
    for(int i=l;i<=r;i++) insert(rt[x],0,M,c[i],1);
}
void Travel(int x)
{
    if(!x) return;
    reuse(rt[x]);
    Travel(ls[x]);
    c[++del_num]=val[x];
    Travel(rs[x]);
    d2[++tot2]=x;ls[x]=rs[x]=0;
}
void rebuild(int &x)
{
    del_num=0;Travel(x);
    build(x,1,del_num);
}
void insert(int &x,int p,int v)
{
    if(!x)
    {
        x=++cnt;val[x]=v;siz[x]=1;
        insert(rt[x],0,M,v,1);
        return;
    }
    siz[x]++;insert(rt[x],0,M,v,1);
    if(siz[ls[x]]+1>=p) insert(ls[x],p,v);
    else insert(rs[x],p-siz[ls[x]]-1,v);
    if(max(siz[ls[x]],siz[rs[x]])>siz[x]*alpha) tmp=x;
    else if(tmp&&(ls[x]==tmp||rs[x]==tmp)) flag=x;
}
void insert(int x,int y)
{
    flag=tmp=0;
    insert(root,x,y);
    if(tmp==root) rebuild(root);
    else if(flag) rebuild(ls[flag]==tmp?ls[flag]:rs[flag]);
}
int change(int &x,int p,int v)
{
    if(siz[ls[x]]+1==p)
    {
        int tmp=val[x];val[x]=v;
        insert(rt[x],0,M,tmp,-1);
        insert(rt[x],0,M,val[x],1);
        return tmp;
    }
    int k;
    if(siz[ls[x]]+1>=p) k=change(ls[x],p,v);
    else k=change(rs[x],p-siz[ls[x]]-1,v);
    insert(rt[x],0,M,v,1);insert(rt[x],0,M,k,-1);
    return k;
}
void query(int x,int l,int r)
{
    int L=siz[ls[x]],R=siz[x];
    if(l==1&&r==R){A[++cnt1]=rt[x];return;}
    if(l<=L+1&&r>=L+1)B[++cnt2]=val[x];
    if(r<=L)query(ls[x],l,r);
    else if(l>L+1)query(rs[x],l-L-1,r-L-1);
    else
    {
        if(l<=L)query(ls[x],l,L);
        if(R>L+1)query(rs[x],1,r-L-1);
    }
}
int get_ans(int x,int y,int k)
{
    cnt1=cnt2=0;
    query(root,x,y);k--;
    int l=0,r=M,mid,sum;
    while(l<r)
    {
        mid=(l+r)>>1;sum=0;
        for(int i=1;i<=cnt1;i++) sum+=a[a[A[i]].l].sum;
        for(int i=1;i<=cnt2;i++) if(B[i]>=l&&B[i]<=mid) sum++;
        if(k<sum)
        {
            for(int i=1;i<=cnt1;i++) A[i]=a[A[i]].l;
            r=mid;
        }
        else
        {
            for(int i=1;i<=cnt1;i++) A[i]=a[A[i]].r;
            l=mid+1;k-=sum;
        }
    }
    return l;
}
int main()
{
    //freopen("tt.in","r",stdin);
    int n,q,x,y,k,ans=0;char s[2];
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    build(root,1,n);
    cin>>q;
    while(q--)
    {
        scanf("%s%d%d",s,&x,&y);x^=ans;y^=ans;
        if(s[0]=='Q')
        {
            scanf("%d",&k);k^=ans;
            printf("%d\n",ans=get_ans(x,y,k));
        }
        else if(s[0]=='M') 
        change(root,x,y);
        else insert(x,y);
    }
    return 0;
}```