可持久化

· · 个人记录

【可持久化数据结构 (Persistent data structure)】 总是可以保留每一个历史版本，若所有版本都既可以访问又可以修改，称为完全可持久化。可以理解为文本编辑器中的【ctrl+z】撤销操作。

参考：https://oi-wiki.org/ds/persistent/

【可持久化下标线段树】

【P3919 【模板】可持久化数组（可持久化线段树/平衡树）】

https://www.luogu.com.cn/problem/P3919

你需要维护一个长度为 N 的数组，支持如下几种操作

  1. 在某个历史版本上修改某一个位置上的值
  2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

用下标线段树维护一个数组，对于每个版本建一棵线段树->空间 O(QN) 。为了进行优化，可持久化的思想基于以下事实：

也就是每个新版本只需要新建 logN 个点，其他点和老版本【共用】。如上图所示，a[1] 位置发生修改，新建1'/2'/4'/8' 四个新点。这样，从原先的根结点 1 看下去，仍可以看到老版本数组对应的线段树，而从新的根结点 1' 看下去，看到的是新版本数组对应的线段树，我们就保存下来了所有历史版本。

#include<iostream>
#include<cstdio>
#define maxn 1000005
using namespace std;
struct Segment
{
    int ls,rs,val;
};
Segment Tree[maxn<<5];
int n,m;
int a[maxn],cnt;
int newnode(int node)
{
    ++cnt;
    Tree[cnt]=Tree[node];
    return cnt;
} 
int root[maxn];
int build(int id,int l,int r)
{
    id=++cnt;
    if(l==r)
    {
        Tree[id].val=a[l];
        return id;
    }
    int mid=(l+r)>>1;
    Tree[id].ls=build(Tree[id].ls,l,mid);
    Tree[id].rs=build(Tree[id].rs,mid+1,r);
    return id;
}
int update(int id,int l,int r,int p,int v)
{
    int newid=newnode(id);
    if(l==r) 
    {
        Tree[newid].val=v;
        return newid;
    }
    int mid=(l+r)>>1;
    if(p<=mid) Tree[newid].ls=update(Tree[id].ls,l,mid,p,v);
    else Tree[newid].rs=update(Tree[id].rs,mid+1,r,p,v);
    return newid;
}
int query(int id,int l,int r,int p)
{
    if(l==r) return Tree[id].val;
    int mid=(l+r)>>1;
    if(p<=mid) return query(Tree[id].ls,l,mid,p);
    else return query(Tree[id].rs,mid+1,r,p);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    root[0]=build(0,1,n);
    int his,k,p,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&his,&k,&p);
        if(k==1)
        {
            scanf("%d",&v);
            root[i]=update(root[his],1,n,p,v);
        }
        else 
        {
            printf("%d\n",query(root[his],1,n,p));
            root[i]=root[his];
        }
    }
    return 0;
}

【T19803 【模板】区间修改主席树】

https://www.luogu.com.cn/problem/T19803

可持久化下标线段树，要求支持区间修改。注意 pushdown 的时候需要复制结点，否则只会 pushdown 到旧线段树的 ls/rs 上，而不会影响新树。

空间/时间都是1个log，常数很大。

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int maxn=2e5+5;
int ls[maxn*100],rs[maxn*100];
ll sum[maxn*100],tag[maxn*100];
int n,m,a[maxn],cnt,rt[maxn];
void pushup(int id)
{
    sum[id]=(sum[ls[id]]+sum[rs[id]])%mod;
}
void build(int &id,int l,int r)
{
    id=++cnt;
    if(l==r)
    {
        sum[id]=a[l]%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(ls[id],l,mid);
    build(rs[id],mid+1,r);
    pushup(id);
}
int newdot(int id)
{
    cnt++;
    ls[cnt]=ls[id],rs[cnt]=rs[id];
    sum[cnt]=sum[id],tag[cnt]=tag[id];
    return cnt;
}
void pushdown(int id,int l,int r)
{
    ls[id]=newdot(ls[id]);
    rs[id]=newdot(rs[id]);
    tag[ls[id]]=(tag[ls[id]]+tag[id])%mod;
    tag[rs[id]]=(tag[rs[id]]+tag[id])%mod;
    int mid=(l+r)>>1;
    sum[ls[id]]=(sum[ls[id]]+tag[id]*(mid-l+1))%mod;
    sum[rs[id]]=(sum[rs[id]]+tag[id]*(r-mid))%mod;
    tag[id]=0;
}
void update(int &id,int id0,int l,int r,int x,int y,ll add)
{
    id=newdot(id0);
    if(l>=x && r<=y)
    {
        tag[id]=(tag[id]+add)%mod;
        sum[id]=(sum[id]+(r-l+1)*add)%mod;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(id,l,r);
    pushdown(id0,l,r);
    if(x<=mid) update(ls[id],ls[id0],l,mid,x,y,add);
    if(y>mid) update(rs[id],rs[id0],mid+1,r,x,y,add);
    pushup(id);
}
ll query(int id,int l,int r,int x,int y)
{
    if(l>=x && r<=y) return sum[id];
    ll ret=0;
    int mid=(l+r)>>1;
    pushdown(id,l,r);
    if(x<=mid) ret+=query(ls[id],l,mid,x,y);
    if(y>mid) ret+=query(rs[id],mid+1,r,x,y);
    ret%=mod;
    return ret;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(rt[0],1,n);
    int k,t,l,r;
    ll x;
    for(int i=1;i<=m;i++)
    {
        cin>>k>>t>>l>>r;
        if(k==1)
        {
            cin>>x;
            update(rt[i],rt[t],1,n,l,r,x);
        }
        if(k==2)
        {
            cout<<query(rt[t],1,n,l,r)<<'\n';
            rt[i]=rt[t];
        }
    }
    return 0;
}

【可持久化值域线段树/主席树】

【P3834 【模板】可持久化线段树 2（主席树）】

https://www.luogu.com.cn/problem/P3834

查询序列区间第 k 小，静态在线。

给定 n 个整数构成的序列，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。

类似值域线段树上二分求 kth() 的方法，对于 [l,r] 区间内部的kth，若有[1,l-1] 和 [1,r] 2个前缀所对应的2棵值域线段树rt0/rt1，可以通过：

为了构建所有前缀 [1,i] 对应的动态开点值域线段树，用可持久化的方式依次将 a[1...n] 加入值域线段树，每次加入都生成一个新版本。空间O(nlogn)，同时拥有 n 棵值域线段树。注意这里主席树支持在线询问，但不支持修改（只能解决静态问题）。时间复杂度 O(qlogn)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 200005
using namespace std;
struct Segment
{
    int ls,rs,val;
};
Segment Tree[maxn<<5];
int n,m;
int a[maxn],b[maxn],root[maxn],cnt;
int newnode(int node)
{
    Tree[++cnt]=Tree[node];
    return cnt;
}
void pushup(int id)
{
    Tree[id].val=Tree[Tree[id].ls].val+Tree[Tree[id].rs].val;
}
void build(int &id,int l,int r)
{
    id=++cnt;
    if(l==r)
    {
        Tree[id].val=0;
        return;
    }
    int mid=(l+r)>>1;
    build(Tree[id].ls,l,mid);
    build(Tree[id].rs,mid+1,r);
    pushup(id);
}
int update(int id,int l,int r,int p)
{
    int newid=newnode(id);
    if(l==r)
    {
        Tree[newid].val++;
        return newid;
    }
    int mid=(l+r)>>1;
    if(p<=mid) Tree[newid].ls=update(Tree[id].ls,l,mid,p);
    else Tree[newid].rs=update(Tree[id].rs,mid+1,r,p);
    pushup(newid);
    return newid;
}
int query(int lid,int rid,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int x=Tree[Tree[rid].ls].val-Tree[Tree[lid].ls].val;
    if(k<=x) 
        return query(Tree[lid].ls,Tree[rid].ls,l,mid,k);
    else
        return query(Tree[lid].rs,Tree[rid].rs,mid+1,r,k-x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int num=unique(b+1,b+1+n)-b-1;
    build(root[0],1,num);
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(b+1,b+1+num,a[i])-b;
        root[i]=update(root[i-1],1,num,p);
    }
    int st,end,k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&st,&end,&k);
        printf("%d\n",b[query(root[st-1],root[end],1,num,k)]);
    }
    return 0;
}

【P2633 Count on a tree】

https://www.luogu.com.cn/problem/P2633

树上路径第 k 小，静态强制在线。

对所有 1\to i 路径建主席树，对于 u\to v 路径，找到rt[u],rt[v],rt[lca],rt[fa[lca]] 四棵值域线段树，在上面二分即可。时间/空间复杂度1个log。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100005
using namespace std;
int n,m;
struct Eric_cai
{
    int to,next;
};
Eric_cai EC[maxn<<1];
int head[maxn],cnt;
void add(int u,int v)
{
    EC[++cnt].to=v;
    EC[cnt].next=head[u];
    head[u]=cnt;
}
struct Segment
{
    int ls,rs,val;
};
int a[maxn],p[maxn],b[maxn],num;
Segment Tree[maxn<<5];
int root[maxn],sum;
int build(int id,int l,int r)
{
    id=++sum;
    if(l==r) return id;
    int mid=(l+r)/2;
    Tree[id].ls=build(id,l,mid);
    Tree[id].rs=build(id,mid+1,r);
    return id;
}
void pushup(int id)
{
    Tree[id].val=Tree[Tree[id].ls].val+Tree[Tree[id].rs].val;
}
int update(int id,int l,int r,int x)
{
    int newid=++sum;
    Tree[newid]=Tree[id];
    if(l==r) 
    {
        Tree[newid].val++;
        return newid;
    }
    int mid=(l+r)/2;
    if(x<=mid) Tree[newid].ls=update(Tree[id].ls,l,mid,x);
    else Tree[newid].rs=update(Tree[id].rs,mid+1,r,x);
    pushup(newid);
    return newid;
}
int fa[maxn],dep[maxn],dfn[maxn],times;
int son[maxn],sz[maxn];
void dfs(int now,int f)
{
    root[now]=update(root[f],1,num,p[now]);
    dep[now]=dep[f]+1;
    fa[now]=f;
    sz[now]=1;
    for(int i=head[now];i!=0;i=EC[i].next)
    {
        if(EC[i].to==f) continue;
        dfs(EC[i].to,now);
        sz[now]+=sz[EC[i].to];
        if(sz[EC[i].to]>sz[son[now]]) son[now]=EC[i].to;
    }
    return;
}
int top[maxn];
void pre(int now,int f)
{
    dfn[now]=++times;
    top[now]=f;
    if(son[now]==0) return;
    pre(son[now],f);
    for(int i=head[now];i!=0;i=EC[i].next)
    {
        if(EC[i].to==fa[now] || EC[i].to==son[now]) continue;
        pre(EC[i].to,EC[i].to);
    }
}
int get_lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) return u;
    else return v;
}
int query(int uid,int vid,int lcaid,int falcaid,int l,int r,int k)
{
    if(l==r) return b[l];
    int mid=(l+r)/2;
    int lsval=Tree[Tree[uid].ls].val+Tree[Tree[vid].ls].val-Tree[Tree[lcaid].ls].val-Tree[Tree[falcaid].ls].val;
    int nowval=Tree[uid].val+Tree[vid].val-Tree[lcaid].val-Tree[falcaid].val;
    if(lsval>=k) return query(Tree[uid].ls,Tree[vid].ls,Tree[lcaid].ls,Tree[falcaid].ls,l,mid,k);
    else return query(Tree[uid].rs,Tree[vid].rs,Tree[lcaid].rs,Tree[falcaid].rs,mid+1,r,k-lsval);
}
int main()
{
    int u,v,st,end,k,last=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    root[0]=build(1,1,n);
    sort(b+1,b+1+n);
    num=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++)
        p[i]=lower_bound(b+1,b+1+num,a[i])-b;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    pre(1,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&st,&end,&k);
        if(i!=1) st=st^last;
        int lca=get_lca(st,end);
        last=query(root[st],root[end],root[lca],root[fa[lca]],1,num,k);
        printf("%d\n",last);
    }
    return 0;
}

【P3567 [POI2014]KUR-Couriers】

https://www.luogu.com.cn/problem/P3567

题意：给一个数列，每次询问一个区间内有没有一个数出现次数超过一半。

对所有前缀建值域主席树。对于区间 [l,r] ，len = r-l+1，比较2棵值域线段树中左子/右子的 sz 之差和 len/2 的关系，易知左子/右子只有其中之一能够满足限制，递归下去继续找，复杂度1个log。

#include<iostream>
#include<cstdio>
#define maxn 500005
using namespace std;
struct Segment
{
    int ls,rs,val;
};
Segment Tree[maxn<<5];
int n,m,cnt,num[maxn];
int root[maxn];
int build(int id,int l,int r)
{
    id=++cnt;
    if(l==r) return id;
    int mid=(l+r)>>1;
    Tree[id].ls=build(id<<1,l,mid);
    Tree[id].rs=build((id<<1)|1,mid+1,r);
    return id;
}
int newnode(int x)
{
    Tree[++cnt]=Tree[x];
    return cnt;
}
void pushup(int id)
{
    Tree[id].val=Tree[Tree[id].ls].val+Tree[Tree[id].rs].val;
}
int update(int id,int l,int r,int x)
{
    int newid=newnode(id);
    if(l==r)
    {
        Tree[newid].val++;
        return newid;
    }
    int mid=(l+r)>>1;
    if(mid>=x) Tree[newid].ls=update(Tree[id].ls,l,mid,x);
    else Tree[newid].rs=update(Tree[id].rs,mid+1,r,x);
    pushup(newid);
    return newid;
}
int query(int lid,int rid,int l,int r,int x)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int y=Tree[Tree[rid].ls].val-Tree[Tree[lid].ls].val;
    int z=Tree[Tree[rid].rs].val-Tree[Tree[lid].rs].val;
    if(y>x) return query(Tree[lid].ls,Tree[rid].ls,l,mid,x);
    if(z>x) return query(Tree[lid].rs,Tree[rid].rs,mid+1,r,x);
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    root[0]=build(0,1,maxn);
    for(int i=1;i<=n;i++)
        root[i]=update(root[i-1],1,maxn,num[i]);
    int st,end;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&st,&end);
        printf("%d\n",query(root[st-1],root[end],1,maxn,(end-st+1)/2));
    }
    return 0;
}

拓展：询问 (l,r,t) 代表区间中出现次数大于 len/t 的最大数字，t<=20。

静态二维数点

把序列中的一个数 a[i] 看成二维平面上的一个点 (i,a[i])，则对一个下标区间 [l,r] 中值域区间[vl,vr] 内的计数/求和等操作，相当于静态二维数点，用主席树可以做到复杂度1个log。

注意这里不支持动态修改。

【可持久化01Trie】

可持久化 01Trie 的方式和可持久化值域线段树的方式是相似的，只是以 01字典树 的方式来维护值域。一般用来解决异或相关的能够按位贪心的题目。例如：

解法：考虑对所有前缀异或和 s[i] 建立可持久化01Trie，在rt[l-1]/rt[r]2棵Trie上按位贪心。

【P4735 最大异或和】

https://www.luogu.com.cn/problem/P4735

给定一个非负整数序列 a[1...n]。

有 m 个操作，有以下两种操作类型：

后缀转化为前缀，相当于找一个前缀 s[y] 使得 s[y]\bigoplus x\bigoplus tot 的值最大，y 有范围限制，转化为可持久化01Trie的经典模型。

复杂度 O(30(n+m))。

#include<iostream>
#include<cstdio>
#define maxn 20000005
using namespace std;
int sum[maxn],n,m,a[maxn],cnt;
int son[maxn][2],rt[maxn],sz[maxn];
int newdot(int x)
{
    son[++cnt][0]=son[x][0];
    son[cnt][1]=son[x][1];
    sz[cnt]=sz[x];
    return cnt;
}
void pushup(int id)
{
    //cout<<"ph:"<<id<<endl;
    sz[id]=sz[son[id][0]]+sz[son[id][1]];
}
void add(int now,int &id,int num,int p)
{
    id=newdot(now);
    if(p==-1)
    {
        sz[id]++;
        return;
    }
    if(num&(1<<p)) add(son[now][1],son[id][1],num,p-1);
    else add(son[now][0],son[id][0],num,p-1);
    pushup(id);
}
void dfs(int now)
{
    cout<<now<<" "<<son[now][0]<<" "<<son[now][1]<<" "<<sz[now]<<endl;
    if(son[now][0]) dfs(son[now][0]);
    if(son[now][1]) dfs(son[now][1]);
}
int get_Max(int rid,int lid,int num,int p)
{
    //cout<<rid<<" "<<son[rid][0]<<" "<<son[rid][1]<<endl;
    if(p==-1) return 0;
    if(sz[son[rid][((num&(1<<p))==0)]]-sz[son[lid][((num&(1<<p))==0)]])
    {
        //cout<<p<<" "<<rid<<" "<<lid<<" "<<((num&(1<<p))==0)<<endl;
        return (1<<p)+get_Max(son[rid][((num&(1<<p))==0)],son[lid][((num&(1<<p))==0)],num,p-1);
    }
    else return get_Max(son[rid][((num&(1<<p))!=0)],son[lid][((num&(1<<p))!=0)],num,p-1);
}
int main()
{
    int l,r,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]^a[i];
        add(rt[i-1],rt[i],sum[i],25);
        //cout<<i<<":"<<endl;
        //dfs(rt[i]);
    }
    char opt;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        //for(int j=1;j<=n;j++) cout<<sum[j]<<" ";
        //cout<<endl;
        //dfs(rt[n]);
        cin>>opt;
        if(opt=='A')
        {
            scanf("%d",&x);
            n++;
            sum[n]=sum[n-1]^x;
            add(rt[n-1],rt[n],sum[n],25);
        }
        else
        {
            ans=0;
            scanf("%d%d%d",&l,&r,&x);
            if(l==1)
            {
                ans=sum[n]^x;
                l=2;
            }
            ans=max(ans,get_Max(rt[r-1],rt[l-2],sum[n]^x,25));
            printf("%d\n",ans);
        }
    }
    return 0;
}

【P4551 最长异或路径】

https://www.luogu.com.cn/problem/P4551

给定一棵 n 个点的带权树，寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

异或的性质非常好，path(u,v) = path(rt,u) \bigoplus path(rt,v)

递推求出 rt 到树上所有点 i 路径的异或值 d[i] ，建一棵01Tire然后在上面查询 n 次即可，复杂度 O(30n)

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+5;
struct Eric_cai
{
    int to,next,val;
};
Eric_cai EC[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int w)
{
    EC[++cnt].to=v;
    EC[cnt].val=w;
    EC[cnt].next=head[u];
    head[u]=cnt;
}
int n,son[maxn<<5][2],sumx[maxn],num,ans;
void dfs(int now,int fa,int w)
{
    sumx[now]=sumx[fa]^w;
    for(int i=head[now];i!=0;i=EC[i].next)
        if(EC[i].to!=fa) dfs(EC[i].to,now,EC[i].val);
}
void ins(int now,int dep,int x)
{
    if(dep<0) return;
    int k=((x&(1<<dep))!=0);
    if(son[now][k]==0) son[now][k]=++num;
    ins(son[now][k],dep-1,x);
}
int query(int now,int dep,int x)
{
    if(dep<0) return 0;
    int k=((x&(1<<dep))==0);
    if(son[now][k]!=0) return (1<<dep)+query(son[now][k],dep-1,x);
    else return query(son[now][k^1],dep-1,x);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int u,v,w;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0,0);
    for(int i=1;i<=n;i++) ins(0,30,sumx[i]);
    for(int i=1;i<=n;i++) ans=max(ans,query(0,30,sumx[i]));
    cout<<ans<<'\n';
    return 0;
}

【P4592 [TJOI2018]异或】

https://www.luogu.com.cn/problem/P4592

给一棵树，询问子树中点权异或一个定值的max，或者询问 u\to v 路径上点权异或一个定值的max。

按时间戳建立点权的可持久化01Trie，子树转化为区间，可以回答子树的询问；对于u->v路径，拆成 rt->u，rt->v，rt->lca，rt->fa[lca] 四条路径，在四棵Trie上二分。总复杂度 O(30n)。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
struct Eric_cai
{
    int to,next;
};
Eric_cai EC[maxn<<1];
int head[maxn],cnt;
void add(int u,int v)
{
    EC[++cnt].to=v;
    EC[cnt].next=head[u];
    head[u]=cnt;
}
struct Trie
{
    int son[maxn<<5][2],num,rt[maxn],sz[maxn<<5];
    void init()
    {
        memset(son,0,sizeof(son));
        memset(rt,0,sizeof(rt));
        memset(sz,0,sizeof(sz));
        rt[0]=num=1;
    }
    int newdot(int id)
    {
        num++;
        son[num][0]=son[id][0],son[num][1]=son[id][1];
        sz[num]=sz[id];
        return num;
    }
    void pushup(int id)
    {
        sz[id]=sz[son[id][0]]+sz[son[id][1]];
    }
    void ins(int &now,int id,int dep,int x)
    {
        now=newdot(id);
        if(dep<0)
        {
            sz[now]++;
            return;
        }
        int k=((x&(1<<dep))!=0);
        ins(son[now][k],son[id][k],dep-1,x);
        pushup(now);
    }
    int query1(int id1,int id2,int dep,int x)
    {
        if(dep<0) return 0;
        int k=((x&(1<<dep))==0);
        if(sz[son[id1][k]]-sz[son[id2][k]]>0)
            return (1<<dep)+query1(son[id1][k],son[id2][k],dep-1,x);
        else return query1(son[id1][k^1],son[id2][k^1],dep-1,x);
    }
    int query2(int id1,int id2,int id3,int id4,int dep,int x)
    {
        if(dep<0) return 0;
        int k=((x&(1<<dep))==0);
        if(sz[son[id1][k]]+sz[son[id2][k]]-sz[son[id3][k]]-sz[son[id4][k]]>0)
            return (1<<dep)+query2(son[id1][k],son[id2][k],son[id3][k],son[id4][k],dep-1,x);
        else return query2(son[id1][k^1],son[id2][k^1],son[id3][k^1],son[id4][k^1],dep-1,x);
    }
};
Trie T1,T2;
int n,q,val[maxn],dfn[maxn],times,a[maxn],szt[maxn],fa[maxn][30],depth[maxn];
void dfs(int now,int f)
{
    depth[now]=depth[f]+1;
    fa[now][0]=f;
    for(int i=1;i<=20;i++)
        fa[now][i]=fa[fa[now][i-1]][i-1];
    szt[now]=1;
    T2.ins(T2.rt[now],T2.rt[f],30,val[now]);
    dfn[now]=++times;
    a[dfn[now]]=now;
    for(int i=head[now];i!=0;i=EC[i].next)
    {
        if(EC[i].to!=f)
        {
            dfs(EC[i].to,now);
            szt[now]+=szt[EC[i].to];
        }
    }
}
int get_lca(int u,int v)
{
    if(depth[u]<depth[v]) swap(u,v);
    for(int i=20;i>=0;i--)
        if(depth[fa[u][i]]>=depth[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k,u,v,w,lca;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    T1.init();
    T2.init();
    dfs(1,0);
    for(int i=1;i<=n;i++)
        T1.ins(T1.rt[i],T1.rt[i-1],30,val[a[i]]);
    for(int i=1;i<=q;i++)
    {
        cin>>k>>u>>v;
        if(k==1) cout<<T1.query1(T1.rt[dfn[u]+szt[u]-1],T1.rt[dfn[u]-1],30,v)<<'\n';
        if(k==2)
        {
            cin>>w;
            lca=get_lca(u,v);
            cout<<T2.query2(T2.rt[u],T2.rt[v],T2.rt[lca],T2.rt[fa[lca][0]],30,w)<<'\n';
        }
    }
    return 0;
}

【P5283 [十二省联考 2019] 异或粽子】

https://www.luogu.com.cn/problem/P5283

给一个序列，求前 k 大区间异或和。

每个右端点 r 对应一段左端点 [1,r-1]，使用超级钢琴模型 + 可持久化01trie。也可以 k 乘2之后忽略 l\le r 的限制，在全局01trie上询问 kth() 完成。

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
const int maxn=5e5+5;
int sz[maxn<<6],son[maxn<<6][2],cnt=1;
void pushup(int id)
{
    sz[id]=sz[son[id][0]]+sz[son[id][1]];
}
void ins(int now,int dep,ll x)
{
    if(dep<0)
    {
        sz[now]++;
        return;
    }
    int k=((x&(1ll<<dep))!=0);
    if(son[now][k]==0) son[now][k]=++cnt;
    ins(son[now][k],dep-1,x);
    pushup(now);
}
int n,k;
ll val[maxn],ans,num[maxn],sum[maxn];
ll query(int now,int dep,ll x,int k)
{
    if(dep<0) return 0;
    int y=((x&(1ll<<dep))==0);
    if(sz[son[now][y]]>=k) return (1ll<<dep)+query(son[now][y],dep-1,x,k);
    else return query(son[now][y^1],dep-1,x,k-sz[son[now][y]]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    ins(1,35,0ll);
    num[0]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>val[i];
        sum[i]=sum[i-1]^val[i];
        ins(1,35,sum[i]);
        num[i]=1;
    }
    priority_queue<pair<ll, int> > pq;
    for(int i=0;i<=n;i++)
        pq.push(make_pair(query(1,35,sum[i],num[i]),i));
    int id;
    k*=2;
    while(k--)
    {
        ans+=pq.top().first;
        id=pq.top().second;
        pq.pop();
        num[id]++;
        if(num[id]<=n) pq.push(make_pair(query(1,35,sum[id],num[id]),id));
    }
    ans/=2;
    cout<<ans<<'\n';
    return 0;
}

【P3293 [SCOI2016]美味】

https://www.luogu.com.cn/problem/P3293

题意：序列 a[1...n]，每次询问 (l,r,b,x) 代表求 b\bigoplus (a[i]+x) 的最大值，有限制 l\le i\le r。

主席树 + 按位贪心，设 a[i] + x = res

位于第 i 位时若 b 的这一位=1，则 res 这一位=0的条件是：

同理，res 这一位=1的条件是：

主席树支持查询下标 [l,r] 中的目标值域区间中是否有值，总复杂度2个log。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=2e5+5;
int n,m,sz[maxn*50],ls[maxn*50],rs[maxn*50],rt[maxn],cnt;
void pushup(int id)
{
    sz[id]=sz[ls[id]]+sz[rs[id]];
}
int newdot(int id)
{
    cnt++;
    sz[cnt]=sz[id],ls[cnt]=ls[id],rs[cnt]=rs[id];
    return cnt;
}
int update(int id,int l,int r,int x)
{
    int now=newdot(id);
    if(l==r)
    {
        sz[now]++;
        return now;
    }
    int mid=(l+r)>>1;
    if(x<=mid) ls[now]=update(ls[now],l,mid,x);
    else rs[now]=update(rs[now],mid+1,r,x);
    pushup(now);
    return now;
}
int query(int id1,int id2,int l,int r,int x,int y)
{
    if(x>y) return 0;
    if(l>=x && r<=y) return sz[id1]-sz[id2];
    int ret=0,mid=(l+r)>>1;
    if(x<=mid) ret+=query(ls[id1],ls[id2],l,mid,x,y);
    if(y>mid) ret+=query(rs[id1],rs[id2],mid+1,r,x,y);
    return ret;
}
int get_ans(int x,int y,int l,int r)
{
    //cout<<"get_ans:"<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
    int L,R,ret=0,k,num=0;
    for(int i=20;i>=0;i--)
    {
        k=((x&(1<<i))==0);
        L=min(max(0,num-y+(1<<i)*k),int(1e5));
        R=max(0,min(int(1e5),num-y+(1<<i)*k+(1<<i)-1));
        //cout<<L<<" "<<R<<" "<<ret<<" "<<num<<" "<<query(rt[r],rt[l-1],0,1e5,L,R)<<endl;
        if(query(rt[r],rt[l-1],0,1e5,L,R)>0) ret+=(1<<i),num+=(1<<i)*k;
        else num+=(1<<i)*(k^1);
    }
    return ret;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int x,y,l,r;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        rt[i]=update(rt[i-1],0,1e5,x);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>l>>r;
        cout<<get_ans(x,y,l,r)<<'\n';
    }
    return 0;
}

【*可持久化平衡树】

Fhq-Treap中的 split() 都是自顶向下的过程，将沿途经过的 logn 个结点复制即可实现可持久化，过程和【可持久化线段树】类似。

注意：

  1. 若参与 merge() 的节点在之后不会用到，则 merge() 函数中不用复制结点，例如维护历史版本等；
  2. 否则 merge() 函数中需要复制结点，例如区间复制等；
  3. 若有区间标记，则 pushD() 时需要复制左右儿子结点；

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

https://www.luogu.com.cn/problem/P3835

维护一个多重集，支持平衡树的所有操作。和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。每个版本的编号即为操作的序号（版本0即为初始状态，空树）。

完整代码，注意主函数中每次操作产生一个新版本: rt[t] = rt[v];

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=5e5+5;
int ls[maxn*50],rs[maxn*50],sz[maxn*50];
int num[maxn*50],rd[maxn*50],cnt,rt[maxn];
int n;
int cpydot(int id)
{
    cnt++;
    ls[cnt]=ls[id],rs[cnt]=rs[id],sz[cnt]=sz[id];
    num[cnt]=num[id],rd[cnt]=rd[id];
    return cnt;
}
int newdot(int x)
{
    cnt++;
    sz[cnt]=1,num[cnt]=x,rd[cnt]=rand();
    return cnt;
}
void pushup(int id)
{
    sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
void split(int now,int x,int &A,int &B)
{
    if(now==0)
    {
        A=B=0;
        return;
    }
    if(num[now]<=x)
    {
        A=cpydot(now);
        split(rs[A],x,rs[A],B);
        pushup(A);
    }
    else
    {
        B=cpydot(now);
        split(ls[B],x,A,ls[B]);
        pushup(B);
    }
}//<=x->A,>x->B
int merge(int A,int B)
{
    if(A==0 || B==0) return A+B;
    if(rd[A]>=rd[B])
    {
        A=cpydot(A);
        rs[A]=merge(rs[A],B);
        pushup(A);
        return A;
    }
    else
    {
        B=cpydot(B);
        ls[B]=merge(A,ls[B]);
        pushup(B);
        return B;
    }
}
int get_num(int now,int x)
{
    if(sz[ls[now]]+1==x) return num[now];
    if(sz[ls[now]]>=x) return get_num(ls[now],x);
    else return get_num(rs[now],x-sz[ls[now]]-1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t,k,x,A,B,C,D;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t>>k>>x;
        if(k==1)
        {
            split(rt[t],x,A,B);
            rt[i]=merge(merge(A,newdot(x)),B);
        }
        if(k==2)
        {
            split(rt[t],x,A,C);
            split(A,x-1,A,B);
            B=merge(ls[B],rs[B]);
            rt[i]=merge(merge(A,B),C);
        }
        if(k==3)
        {
            split(rt[t],x-1,A,B);
            cout<<sz[A]+1<<'\n';
            rt[i]=rt[t];
        }
        if(k==4)
        {
            cout<<get_num(rt[t],x)<<'\n';
            rt[i]=rt[t];
        }
        if(k==5)
        {
            split(rt[t],x-1,A,B);
            if(A==0) cout<<1ll-(1ll<<31)<<'\n';
            else cout<<get_num(A,sz[A])<<'\n';
            rt[i]=rt[t];
        }
        if(k==6)
        {
            split(rt[t],x,A,B);
            if(B==0) cout<<(1ll<<31)-1ll<<'\n';
            else cout<<get_num(B,1)<<'\n';
            rt[i]=rt[t];
        }
    }
    return 0;
}

【*可持久化并查集】

可持久化并查集 = 按秩合并并查集 + 可持久化数组

首先并查集不能采用路径压缩，这是因为一次 findR()操作中，fa数组的很多位置（u 的所有祖先）会发生修改，由于每次修改都需要在可持久化数组上复制产生log个新结点，空间复杂度过大。我们不希望每个版本的 fa 数组的差别太大，最好只有常数个位置改变。

启发式合并/按秩合并

当 merge(u,v) 时，找到 ru,rv 后，让 sz 小的接在 sz 大的下面：

if(sz[ru] > sz[rv]) swap(ru,rv);
fa[ru] = rv;
sz[rv] += sz[ru]

或者让高度（到叶子的最长距离）height 小的接在 height 大的下面：

if(height[ru] > height[rv]) swap(ru,rv);
fa[ru] = rv;
if(height[ru] == height[rv]) ++height[rv];

按 sz 合并一般称为启发式合并，按height合并一般称为按秩合并，二者的复杂度都是 logn（每向上走1条边，身处的子树sz至少扩大1倍），且每次 merge 操作时，fa 数组只有2个位置会发生修改( fa[ru] 和sz[rv] )，直接用可持久化下标线段树维护 fa 数组就可以实现可持久化。使用1个栈可以实现撤销最末操作/回滚。

【P3402 可持久化并查集】

https://www.luogu.com.cn/problem/P3402

给定 n 个集合，第 i 个集合内初始状态下只有一个数 i。

有 m 次操作。操作分为 3 种：

  1. 合并 a,b 所在集合；
  2. 回到第 k 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；
  3. 询问 a,b 是否属于同一集合，输出0/1

由于并查集本身带1个log，而每次去 fa 数组里 findR(x) 又是1个log，所以可持久化并查集的时间是2个log，空间1个log。

Node* findR(Node *rt, int x){//log^2
    Node* p = query(rt, x);
    if(p->fa == x) return p;
    else return findR(rt, p->fa);
}

我写的启发式合并。

#include<iostream>
#include<cstdio>
#define maxn 200005
using namespace std;
int n,m,ls[maxn<<5],rs[maxn<<5],fa[maxn<<5],cntdot;
int rt[maxn],cnt,dep[maxn<<5];
inline int newdot(int x)
{
    fa[++cntdot]=fa[x];
    ls[cntdot]=ls[x];
    rs[cntdot]=rs[x];
    dep[cntdot]=dep[x];
    return cntdot;
}
void update_f(int id1,int &id2,int l,int r,int x,int y)
{
    id2=newdot(id1);
    if(l==r)
    {
        fa[id2]=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update_f(ls[id1],ls[id2],l,mid,x,y);
    else update_f(rs[id1],rs[id2],mid+1,r,x,y);
}
int query(int id,int l,int r,int x)
{
    if(l==r) return fa[id];
    int mid=(l+r)>>1;
    if(x<=mid) return query(ls[id],l,mid,x);
    else return query(rs[id],mid+1,r,x);
}
int query_dep(int id,int l,int r,int x)
{
    if(l==r) return dep[id];
    int mid=(l+r)>>1;
    if(x<=mid) return query_dep(ls[id],l,mid,x);
    else return query_dep(rs[id],mid+1,r,x);
}
void update_dep(int id1,int &id2,int l,int r,int x,int y)
{
    id2=newdot(id1);
    if(l==r)
    {
        dep[id2]=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update_dep(ls[id1],ls[id2],l,mid,x,y);
    else update_dep(rs[id1],rs[id2],mid+1,r,x,y);
}
int get_fa(int x)
{
    int F=query(rt[cnt],1,n,x);
    if(F==x) return x;
    return get_fa(F);
}
inline void Merge(int a,int b)
{
    int Fa=get_fa(a),Fb=get_fa(b),depFa,depFb;
    depFa=query_dep(rt[cnt],1,n,Fa);
    depFb=query_dep(rt[cnt],1,n,Fb);
    if(depFa>depFb)
    {
        swap(Fa,Fb);
        swap(depFa,depFb);
    }
    if(depFa+1>depFb) update_dep(rt[cnt],rt[cnt+1],1,n,Fb,depFa+1);
    update_f(rt[cnt],rt[cnt+1],1,n,Fa,Fb);
    cnt++;
}
void build(int &id,int l,int r)
{
    if(id==0) id=++cntdot;
    if(l==r)
    {
        fa[id]=l;
        dep[id]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls[id],l,mid);
    build(rs[id],mid+1,r);
}
int main()
{
    int opt,a,b;
    scanf("%d%d",&n,&m);
    build(rt[0],1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&opt,&a);
        if(opt==1)
        {
            scanf("%d",&b);
            Merge(a,b);
        }
        if(opt==2) rt[++cnt]=rt[a];
        if(opt==3)
        {
            scanf("%d",&b);
            printf("%d\n",(get_fa(a)==get_fa(b)));
            rt[cnt+1]=rt[cnt];
            cnt++;
        }
    }
    return 0;
}

【P4768 [NOI2018] 归程】

https://www.luogu.com.cn/problem/P4768

题意：每个点带点权，支持合并2个集合以及询问某个历史中某个点所在集合的最小点权，强制在线。

如果可以离线的话按时间顺序做一遍并查集即可。强制在线的话需要把并查集可持久化，这样就支持在线对于某个历史版本的询问，复杂度2个log，现场&loj可过。

1个log正解是kruskal重构树。

在涨水过程中建一棵树，初始每个集合是 n 个叶子，每次加一条边时：

​ 1. 新建一个点，点权设为边的海拔；

  1. 新点的左右儿子设为原先2个集合的根节点；
  2. 新点设为合并之后集合的根；

这样在 n-1 次合并之后，得到一棵恰有 n 个叶子的二叉树，满足：

关于kruskal重构树，参考（https://oi-wiki.org/graph/mst/）

总复杂度 O(mlogm + (n+q)logn)，期望得分100分。

习题

【P3168 [CQOI2015]任务查询系统】

https://www.luogu.com.cn/problem/P3168

按时间建关于优先级的主席树，维护区间和/支持线段树上二分。

#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;
const int maxn=2e5+5;
ll sum[maxn*50];
int n,m,rt[maxn],ls[maxn*50],rs[maxn*50],num[maxn*50],cnt;
vector<pair<int, int> > q[maxn];
int cpydot(int id)
{
    cnt++;
    ls[cnt]=ls[id],rs[cnt]=rs[id];
    num[cnt]=num[id],sum[cnt]=sum[id];
    return cnt;
}
void pushup(int id)
{
    num[id]=num[ls[id]]+num[rs[id]];
    sum[id]=sum[ls[id]]+sum[rs[id]];
}
int update(int id,int l,int r,int x,int y)
{
    id=cpydot(id);
    if(l==r)
    {
        num[id]+=y;
        sum[id]+=y*l;
        return id;
    }
    int mid=(l+r)>>1;
    if(x<=mid) ls[id]=update(ls[id],l,mid,x,y);
    else rs[id]=update(rs[id],mid+1,r,x,y);
    pushup(id);
    return id;
}
ll query(int id,int l,int r,int x)
{
    if(x>=num[id]) return sum[id];
    if(l==r) return 1ll*l*x;
    int mid=(l+r)>>1;
    if(num[ls[id]]>=x) return query(ls[id],l,mid,x);
    else return sum[ls[id]]+query(rs[id],mid+1,r,x-num[ls[id]]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int l,r,val,x,k,a,b,c;
    ll lst=1;
    for(int i=1;i<=n;i++)
    {
        cin>>l>>r>>val;
        q[l].push_back(make_pair(val,1));
        q[r+1].push_back(make_pair(val,-1));
    }
    for(int i=1;i<=m;i++)
    {
        rt[i]=rt[i-1];
        for(int j=0;j<q[i].size();j++)
            rt[i]=update(rt[i],1,1e7,q[i][j].first,q[i][j].second);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>a>>b>>c;
        k=(a*lst+b)%c+1;
        lst=query(rt[x],1,1e7,k);
        cout<<lst<<'\n';
    }
    return 0;
}

【CF891C Envy】

https://www.luogu.com.cn/problem/CF891C

kruskal + 带撤销并查集

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
struct edge
{
    int u,v,w;
};
bool cmp(edge A,edge B)
{
    return A.w<B.w;
}
int fa[maxn],sz[maxn],n,m,q,ans[maxn],cnt;
int id[maxn],szid[maxn],num,vis[maxn];
edge e[maxn],cpy[maxn];
struct node
{
    int eid,qid;
};
node a[maxn];
bool cmp1(node A,node B)
{
    if(e[A.eid].w==e[B.eid].w) return A.qid<B.qid;
    return e[A.eid].w<e[B.eid].w;
}
int get_fa(int x)
{
    if(fa[x]==x) return x;
    return get_fa(fa[x]);
}
void merge(int x,int y)
{
    int fx=get_fa(x),fy=get_fa(y);
    if(fx==fy) return;
    if(sz[fx]>sz[fy]) swap(fx,fy);
    fa[fx]=fy;
    num++;
    id[num]=fx;
    szid[num]=fy;
    sz[fy]+=sz[fx];
}
void del()
{
    fa[id[num]]=id[num];
    sz[szid[num]]-=sz[id[num]];
    num--;
}
void print()
{
    for(int i=1;i<=n;i++) cout<<fa[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) cout<<sz[i]<<" ";
    cout<<endl;
}
void get_ans()
{
    for(int i=1;i<=n;i++) sz[i]=1,fa[i]=i;
    for(int i=1;i<=q;i++) ans[i]=1;
    int pos=0,now;
    for(int i=1;i<=m;i++)
    {
        //cout<<i<<":"<<endl;
        //print();
        if(cpy[i].w!=cpy[i-1].w)
        {
            while(e[a[pos+1].eid].w<=cpy[i].w && pos<cnt)
            {
                pos++;
                if(get_fa(e[a[pos].eid].u)==get_fa(e[a[pos].eid].v)) ans[a[pos].qid]=0;
                else
                {
                    merge(e[a[pos].eid].u,e[a[pos].eid].v),vis[pos]=1;
                    //cout<<"merge:"<<pos<<" "<<a[pos].qid<<" "<<e[a[pos].eid].u<<" "<<e[a[pos].eid].v<<endl;
                }
                if(a[pos+1].qid!=a[pos].qid)
                {
                    now=pos;
                    while(a[now].qid==a[pos].qid && now>0 && e[a[now].eid].w==cpy[i].w)
                    {
                        if(vis[now]==1)
                        {
                    //        cout<<"del:"<<now<<" "<<a[now].qid<<endl;
                            del();
                    //        print();
                        }
                        now--;
                    }
                }
            }
        }
        merge(cpy[i].u,cpy[i].v);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k,x;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
        cpy[i]=e[i];
    }
    sort(cpy+1,cpy+1+m,cmp);
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            cin>>x;
            a[++cnt].eid=x;
            a[cnt].qid=i;
        }
    }
    sort(a+1,a+1+cnt,cmp1);
    get_ans();
    for(int i=1;i<=q;i++)
    {
        if(ans[i]==1) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

拓展1：询问每条边，要保证其一定出现在mst上，最大边权是多少。

拓展2：1次操作可以选1条边权值+1，指定一条边，要保证其出现在mst上，最小操作次数是多少。

【P4648 [IOI2007] pairs 动物对数】

https://www.luogu.com.cn/problem/P4648

一维：树状数组；二维：扫描线；三维：前缀和

【P2163 [SHOI2007]园丁的烦恼】

https://www.luogu.com.cn/problem/P2163

离线二维数点，扫描线。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e5+5;
struct node
{
    int x,y;
};
bool cmp(node A,node B)
{
    if(A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}
node a[maxn];
struct Node
{
    int id,x,l,r,add;
};
Node q[maxn*2];
bool cmpq(Node A,Node B)
{
    return A.x<B.x;
}
int n,m,ans[maxn],cnt,sum[maxn*20],ls[maxn*20],rs[maxn*20],dot;
void pushup(int id)
{
    sum[id]=sum[ls[id]]+sum[rs[id]];
}
int upd(int id,int l,int r,int x)
{
    if(id==0) id=++dot;
    if(l==r)
    {
        sum[id]++;
        return id;
    }
    int mid=(l+r)>>1;
    if(x<=mid) ls[id]=upd(ls[id],l,mid,x);
    else rs[id]=upd(rs[id],mid+1,r,x);
    pushup(id);
    return id;
}
int query(int id,int l,int r,int x,int y)
{
    if(l>=x && r<=y) return sum[id];
    int ret=0,mid=(l+r)>>1;
    if(x<=mid) ret+=query(ls[id],l,mid,x,y);
    if(y>mid) ret+=query(rs[id],mid+1,r,x,y);
    return ret;
}
int rt;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int x1,x2,y1,y2;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=m;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        q[++cnt]=(Node){i,x1-1,y1,y2,-1};
        q[++cnt]=(Node){i,x2,y1,y2,1};
    }
    sort(q+1,q+1+cnt,cmpq);
    int pos=0;
    for(int i=1;i<=cnt;i++)
    {
        while(pos<n && a[pos+1].x<=q[i].x)
        {
            pos++;
            rt=upd(rt,0,1e7,a[pos].y);
        }
        ans[q[i].id]+=q[i].add*query(rt,0,1e7,q[i].l,q[i].r);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

【CF484E Sign on Fence】

https://www.luogu.com.cn/problem/CF484E

先按高度排序，按高度建关于下标的主席树，维护区间最长连续段长度。

每次询问先二分，然后在对应线段树上查询区间最长连续段长度。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
struct node
{
    int pos,h;
};
node a[maxn];
bool cmp(node A,node B)
{
    return A.h>B.h;
}
int n,m,rt[maxn],cnt;
struct Tree
{
    int ls,rs,lm,rm,Max,len;
};
Tree d[maxn<<6];
int cpydot(int id)
{
    cnt++;
    d[cnt]=d[id];
    return cnt;
}
Tree pushup(Tree ls,Tree rs)
{
    Tree ret;
    ret.lm=ls.lm;
    if(ls.len!=0 && ls.lm==ls.len) ret.lm=ls.lm+rs.lm;
    ret.rm=rs.rm;
    if(rs.len!=0 && rs.rm==rs.len) ret.rm=ls.rm+rs.rm;
    ret.Max=max(max(ls.Max,rs.Max),ls.rm+rs.lm);
    ret.len=ls.len+rs.len;
    return ret;
}
int update(int id,int l,int r,int x)
{
    id=cpydot(id);
    if(l==r)
    {
        d[id].len=d[id].lm=d[id].rm=d[id].Max=1;
        return id;
    }
    int mid=(l+r)>>1;
    if(x<=mid) d[id].ls=update(d[id].ls,l,mid,x);
    else d[id].rs=update(d[id].rs,mid+1,r,x);
    int ls=d[id].ls,rs=d[id].rs;
    d[id]=pushup(d[d[id].ls],d[d[id].rs]);
    d[id].ls=ls,d[id].rs=rs;
    d[id].len=r-l+1;
    return id;
}
Tree query(int id,int l,int r,int x,int y)
{
    if(l>=x && r<=y) return d[id];
    int mid=(l+r)>>1;
    if(x<=mid && y>mid)
        return pushup(query(d[id].ls,l,mid,x,y),query(d[id].rs,mid+1,r,x,y));
    else if(x<=mid) return query(d[id].ls,l,mid,x,y);
    else return query(d[id].rs,mid+1,r,x,y);
}
int get_ans(int l,int r,int k)
{
    int L=1,R=n,mid,ret=n;
    while(L<=R)
    {
        mid=(L+R)>>1;
        if(query(rt[mid],1,n,l,r).Max>=k)
        {
            R=mid-1;
            ret=min(ret,mid);
        }
        else L=mid+1;
    }
    return a[ret].h;
}
int main()
{
    int l,r,k;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        a[i].pos=i;
        cin>>a[i].h;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) rt[i]=update(rt[i-1],1,n,a[i].pos);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>k;
        cout<<get_ans(l,r,k)<<'\n';
    }
    return 0;
}

【P4602 [CTSC2018]混合果汁】

https://www.luogu.com.cn/problem/P4602

二分答案之后有很好的贪心性质，肯定是按价格升序购买；按美味度从大->小建立价格的主席树，代表每个美味度后缀的果汁集合，维护区间体积总量和 \sum l 和总价格 \sum l\times p，这样在外层二分之后，就可以在线段树上继续二分来计算总价格限制下的最大体积。

总复杂度2个log。

【P4137 Rmq Problem / mex】

https://www.luogu.com.cn/problem/P4137

静态区间mex查询。

首先预处理前驱数组 pre[i] 为 a[i] 上一次出现的位置，那么区间 [l,r] 的mex是最小的 a[i] 满足 pre[i]<l,i\in[l,r]。建立所有前缀的 a[i] 值域主席树，维护区间中 pre 的最小值，支持线段树上二分。

总复杂度1个log。

也可以离线，按 r 升序回答询问，这样空间线性。

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int maxn=2e5+5;
int n,a[maxn],lst[maxn],m,ans[maxn];
vector<pair<int, int> > q[maxn];
multiset<int> Min[maxn];
int Tree[maxn<<2],Maxa=2e5;
void pushup(int id)
{
    Tree[id]=min(Tree[id<<1],Tree[id<<1|1]);
}
void update(int id,int l,int r,int x,int y)
{
    if(l==r)
    {
        Tree[id]=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(id<<1,l,mid,x,y);
    else update(id<<1|1,mid+1,r,x,y);
    pushup(id);
}
int query(int id,int l,int r,int x,int y)
{
    if(l>=x && r<=y) return Tree[id];
    int ret=1e9,mid=(l+r)>>1;
    if(x<=mid) ret=min(ret,query(id<<1,l,mid,x,y));
    if(y>mid) ret=min(ret,query(id<<1|1,mid+1,r,x,y));
    return ret;
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        if(l==0) Tree[id]=0;
        else Tree[id]=1e9;
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l,r;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        q[r].push_back(make_pair(i,l));
    }
    for(int i=0;i<=Maxa;i++) Min[0].insert(i);
    build(1,0,n);
    for(int i=1;i<=n;i++)
    {
        Min[lst[a[i]]].erase(Min[lst[a[i]]].lower_bound(a[i]));
        if(Min[lst[a[i]]].empty()) update(1,0,n,lst[a[i]],1e9);
        else update(1,0,n,lst[a[i]],*Min[lst[a[i]]].begin());
        lst[a[i]]=i;
        Min[lst[a[i]]].insert(a[i]);
        update(1,0,n,lst[a[i]],*Min[lst[a[i]]].begin());
        //if(i==4) print(1,0,n);
        for(int j=0;j<q[i].size();j++)
            ans[q[i][j].first]=query(1,0,n,0,q[i][j].second-1);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}