bzoj 3065: 带插入区间K小值

LINK：bzoj 3065 带插入区间K小值

最终还是想把这道题给A掉。很久以前都思考过的题目了 结果都是败北。

这道题可以块状链表来写 但是我曾经学的块状链表忘了 也好像很难写的样子。。

考虑树套树 由于带插入必然使用平衡树这个数据结构来做，考虑区间第k大 首选主席树。

我们平衡树保证插入 所以必然需要在外面 内部套主席树来做。

由于内部是主席树不适合旋转操作 所以平衡树采用替罪羊树来解决。通常的alpha的值取0.75

但是重构时期望重构节点为nlogn(我不清楚为啥。。 每次重构都要递归logn层 而重新进行主席树的插入为logn

虽然复杂度达到了 nlog^3 但是这只是理论复杂度非常难达到上界。

考虑重构的时候我们选择靠上的节点重构 因为先对下面的节点重构再对上面的节点重构 那么下面重构就没有必要了 减小常数。

注意空间回收 这里可以使用STL的queue存放有哪些位置可以用！

第一次写平衡树套主席树 把算法理念也写一下：

平衡树维护位置集合 考虑是替罪羊树我们假设其初步平衡->类似于二叉树的形态。

平衡树上每个节点之下挂一颗主席树 对于一次区间查询第k大 我们使用平衡树来定位区间 由于类似于二叉树的形态 我们只需要找到logn个节点就可以把区间表示出来。

这些节点的主席树上挂了其儿子的所有信息。当然自己本身也得单独开一颗主席树保证能查找到所在的区间。

这就是我们外套平衡树查区间第k大的思想。

//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define ld long double
#define pb push_back
#define put(x) printf("%d\n",x)
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define rep(p,n,i) for(int i=p;i<=n;++i)
#define pii pair<ll,ll> 
#define mk make_pair
#define EPS 1e-7
#define mod 998244353
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define P 13331ll
#define ui unsigned int
#define S second
#define F first
#define maxx 70000
#define l(p) t[p].l
#define r(p) t[p].r
#define sum(p) t[p].sum
#define ls(p) s[p].l
#define rs(p) s[p].r
#define s(p) s[p].s
#define wr(p) s[p].wr
#define tr(p) s[p].tr
#define v(p) s[p].v 
using namespace std;
const int MAXN=70010,maxn=20000010;
struct wy{int v,l,r,s,wr,tr;}s[MAXN];//平衡树
struct jl{int l,r,sum;}t[maxn];//主席树
queue<int>q;char ch[5];
int root,n,Q,last,top;
int pos[MAXN];
inline void update(int &p,int l,int r,int x,int v)
{
    if(!p){p=q.front();q.pop();}
    sum(p)+=v;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)update(l(p),l,mid,x,v);
    else update(r(p),mid+1,r,x,v);
}
inline int build(int l,int r)
{
    if(l>r)return 0;
    int mid=(l+r)>>1;
    for(int i=l;i<=r;++i)update(tr(pos[mid]),0,maxx,v(pos[i]),1);
    s(pos[mid])=r-l+1;
    ls(pos[mid])=build(l,mid-1);
    rs(pos[mid])=build(mid+1,r);
    return pos[mid];
}
inline void split(int p,int l,int r)
{
    if(l<=1&&r>=s(p)){pos[++top]=tr(p);return;}
    if(l<=s(ls(p))+1&&r>=s(ls(p))+1)pos[++top]=wr(p);
    if(l<=s(ls(p)))split(ls(p),l,r);
    if(r>s(ls(p))+1)split(rs(p),l-s(ls(p))-1,r-s(ls(p))-1);
}
inline void ask(int k)
{
    int L=0,R=maxx;
    while(1)
    {
        if(L==R){last=L;return;}
        int mid=(L+R)>>1,sum=0;
        rep(1,top,i)sum+=sum(l(pos[i]));
        if(sum>=k){rep(1,top,i)pos[i]=l(pos[i]);R=mid;}
        else {rep(1,top,i)pos[i]=r(pos[i]);k-=sum,L=mid+1;}
    }
}
inline int find(int p,int x)
{
    while(1)
    {
        if(s(ls(p))+1==x)return v(p);
        if(s(ls(p))>=x)p=ls(p);
        else x=x-s(ls(p))-1,p=rs(p);
    }
}
inline void del(int &x)//删除主席树
{
    if(!x)return;
    q.push(x);del(l(x));del(r(x));
    sum(x)=0;x=0;
}
inline void dfs(int &x)
{
    if(!x)return;
    dfs(ls(x));pos[++top]=x;dfs(rs(x));
    s(x)=0;del(tr(x));x=0;
}
inline void modify(int p,int x,int v1,int v2)
{
    update(tr(p),0,maxx,v1,-1);
    update(tr(p),0,maxx,v2,1);
    if(x<=s(ls(p))){modify(ls(p),x,v1,v2);return;}
    if(x==s(ls(p))+1)
    {
        del(wr(p));update(wr(p),0,maxx,v2,1);
        v(p)=v2;return;
    }
    modify(rs(p),x-s(ls(p))-1,v1,v2);
}

inline void insert(int &p,int x,int v,int flag)
{
    if(!p)
    {
        p=++n;s(p)=1;v(p)=v;
        update(wr(p),0,maxx,v,1);
        update(tr(p),0,maxx,v,1);
        return;
    }
    int mark=0;
    update(tr(p),0,maxx,v,1);++s(p);
    if(x<=s(ls(p)))
    {
        mark=(s(ls(p))+1)*4>(s(p)+1)*3;
        insert(ls(p),x,v,mark|flag);
    }
    else 
    {
        mark=(s(rs(p))+1)*4>(s(p)+1)*3;
        insert(rs(p),x-s(ls(p))-1,v,mark|flag);
    }
    if(mark&&!flag)top=0,dfs(p),p=build(1,top);
}
int main()
{
    freopen("1.in","r",stdin);
    rep(1,maxn-10,i)q.push(i);
    gt(n);rep(1,n,i)gt(v(i)),update(wr(i),0,maxx,v(i),1),pos[i]=i;
    root=build(1,n);gt(Q);
    rep(1,Q,i)
    {
        scanf("%s",ch+1);
        int x,y,k;
        gt(x);gt(y);
        x=x^last;y=y^last;
        if(ch[1]=='Q')
        {
            top=0;split(root,x,y);//把x到y区间内的主席树收集起来
            gt(k);ask(k^last);put(last);
        }
        if(ch[1]=='M')modify(root,x,find(root,x),y);
        if(ch[1]=='I')insert(root,x-1,y,0);
    }
    return 0;
}

难写+难调 非常鬼畜啊啊啊。。。

值得一提的是 里面的思想对锻炼替罪羊树 及平衡树寻找区间有极大的帮助 尽管稍微参考了一下别人的blog...

不过大体上都是自己写的/doge.

bzoj 3065: 带插入区间K小值

原文：https://www.cnblogs.com/chdy/p/12488939.html