洛谷 P3835 【模板】可持久化平衡树

这个题也是可以用可持久化线段树来解决的。

值域线段树（也有的叫权值线段树）可以用来维护一个可重集，并实现一些一般情况下平衡树才能实现的事情。

如果用值来当做区间左右端点，每个叶子节点上存某个值出现的次数，非叶子节点上存一定范围内的值出现的总次数，就可以建成值域线段树。可以在上面直接查询第k大值、小于某值的数的个数等等，具体请百度或参见代码。

如何将线段树可持久化呢？线段树在单点更新的时候会经过log n个节点，每一次更新时显然也只有这么多节点会发生变化。

记录每一个版本的线段树的根节点，每一次操作前将根节点赋为与这次操作基于的版本的根节点相同。在更新操作时，备份每一个经过的节点（包括各个属性：左、右子树以及区间和），然后再进行修改。具体也可以参考可持久化线段树的题解。

如果直接用可持久化的值域线段树，显然空间是不够的（4*2e9个节点啊...）。现在有两种选择：

1.发现这道题没有加、减操作，所有操作涉及的值都是确定的。因此可以进行离散化，然后再做，想必可以A掉吧（我没试过）

2.可以写动态开点线段树。题目要求的集合一开始是空的，因此如果一开始建一棵完整的线段树的话，每一个节点记录的区间和都是0。而总共只有5e5次操作，每一次操作涉及更改节点最多有log2(2e9)=31个，两者乘起来远远小于4*2e9。

可以考虑一开始不真正建树。规定：如果某节点的某个子节点是一个特殊的标记的话，表明以这个子节点为根的子树还没有实际建出来。显然，一个子树没有实际建出来的时候，其表示的区间的和为0。（以下代码中我用的标记是0）

在进行修改操作的时候，可能需要建出来要走入的那个子节点。在进行查询操作的时候，可以把未建出的子节点的区间和当做0。

附：写完后我发现前驱和后继竟然是最难写的...

附：注意各种对不存在的节点的查询/要忽略的操作

附：注意代码中有一些操作用到的变量被设置成了全局变量，还define了一个mid，表示区间中点，可能比较奇怪...

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define inf 2147483647
using namespace std;
int lc[20000000],rc[20000000],root[20000000],dat[20000000],ll=-1e9,rr=1e9;
//lc[i]、rc[i]分别表示节点i的左子节点、右子节点编号，如果lc[x]=0则表示x的左子树尚未建出来，rc[x]同理
//dat[i]表示节点i表示的值域区间中各数的出现次数之和
int n,L,x,mem=1;//因为0号被"未实际建出的节点"的特殊标记占用了，1号被版本0的根节点占用了

void addx(int l,int r,int& num)//更新操作，将线段树维护的集合中数L的出现次数加上x（x为1或-1）
{
    int t=num;num=++mem;lc[num]=lc[t];rc[num]=rc[t];dat[num]=dat[t];//备份当前节点，如果当前节点原来为空则也可以完成
    if(l==r)
    {
        if(!(dat[num]==0&&x<0)) dat[num]+=x;//如果L出现次数为0且操作为删除操作，则忽略操作
        return;
    }
    if(L<=mid)  addx(l,mid,lc[num]);
    else    addx(mid+1,r,rc[num]);
    dat[num]=0;
    if(lc[num]) dat[num]+=dat[lc[num]];
    if(rc[num]) dat[num]+=dat[rc[num]];//维护当前节点信息
}
int query(int l,int r,int num)//查询集合中小于x的数的个数
{
    if(l==r)    return 0;//如果已经到叶子节点了，那么当前节点等于x，显然不小于x
    if(!num)    return 0;//如果当前节点为空，那么该节点表示的子树中数都没有，自然返回0
    if(x<=mid)  return query(l,mid,lc[num]);//根据x决定向左/右子树走
    else    return (lc[num]?dat[lc[num]]:0)+query(mid+1,r,rc[num]);
}
int query_kth(int l,int r,int k,int num)//查询第k小数
{
    assert(num!=0);//assert(x)表示如果x为false则停止程序，是用来调试的。如果查询操作是正常进行的，那么不可能走到未建出的点中
    if(l==r)    {return l;}
    //if(!num)  return 0;//没有用
    int ls=lc[num]?dat[lc[num]]:0;
    if(ls>=k)   return query_kth(l,mid,k,lc[num]);//根据左子树中数出现总次数决定向左/右子树走
    else        return query_kth(mid+1,r,k-ls,rc[num]);
}
int query_time(int l,int r,int num)//查询数x出现的次数
{
    while(l!=r)
    {
        if(!num)    return 0;//当前节点未建出，表明其子节点均未出现
        if(L<=mid)  r=mid,num=lc[num];
        else    l=mid+1,num=rc[num];
    }
    return dat[num];
}
int query_pre(int l,int r,int num)//查询数x的前驱
{
    int t=query(l,r,num);//t是集合中比x小的数的个数
    if(t==0)    return -inf;//如果集合中比x小的数有0个，则x是集合中最小的数，不存在前驱
    return query_kth(l,r,t,num);//否则查询集合中第t小即可
}
int query_nxt(int l,int r,int num)
{
    int t1=query(l,r,num),t2=query_time(l,r,num);//t1是集合中比x小的数的个数,t2是集合中x出现的次数，加起来是集合中小于等于x的数的个数
    x=inf;int t3=query(l,r,num);
    if(t1+t2==t3)   return inf;//如果集合中小于等于x的数与集合中小于等于inf的数相等，则x是集合中最大的数，不存在后继
    return query_kth(l,r,t1+t2+1,num);//否则查询集合中第t1+t2+1小即可
}
int main()
{
    int i,v,idx;
    scanf("%d",&n);
    root[0]=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&v,&idx,&x);root[i]=root[v];
        if(idx==1)
        {
            L=x;x=1;
            addx(ll,rr,root[i]);
        }
        else if(idx==2)
        {
            L=x;x=-1;
            addx(ll,rr,root[i]);
        }
        else if(idx==3)
        {
            printf("%d\n",query(ll,rr,root[i])+1);
        }
        else if(idx==4)
        {
            printf("%d\n",query_kth(ll,rr,x,root[i]));
        }
        else if(idx==5)
        {
            L=x;
            printf("%d\n",query_pre(ll,rr,root[i]));
        }
        else if(idx==6)
        {
            L=x;
            printf("%d\n",query_nxt(ll,rr,root[i]));
        }
    }
    return 0;
}