主席树学习笔记主席树学习笔记

主席树学习笔记
主席树学习笔记

说在前边：

之前了解过主席树的基础的思想，但是没有系统学习过，所以打算通过一些题目重新学习。

POJ2104

题意：静态区间查询 k-th number
思路：对每个位置开一颗权值线段树，维护前缀区间每个数字出现的次数，这样只需实现两棵线段树相减，利用简单的二分思想即可求出 k-th number。
问题：内存不足以开n颗线段树，时间自然也不够。
解决方法：注意到相邻两个位置，只会一个位置不同，那么发生改变的只有包含这个位置的一条链。那建树时，可以把新建这一条链，其他的边都接在上一个位置的线段树上即可。通过这样的方式我们保存了历史版本的线段树。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;
const int N = 1e5 + 100;
using namespace std;
int n, m;
struct node{ll v; int id;}a[N];
bool cmp(node a,node b){return a.v<b.v;}
int root[N], fid[N], tot;
struct tree{int l,r,num;}T[N*20];
void ins(int &x,int p,int l,int r) {
    T[++tot]=T[x]; x = tot; ++T[x].num;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(p <= mid) ins(T[x].l,p,l,mid);
    else ins(T[x].r,p,mid+1,r);
}
int ask(int pl,int pr,int k,int l,int r) {
    if(l==r)return l;
    int mid = (l+r)>>1;
    if(T[T[pr].l].num-T[T[pl].l].num>=k) return ask(T[pl].l,T[pr].l,k,l,mid);
    else return ask(T[pl].r, T[pr].r,k-(T[T[pr].l].num-T[T[pl].l].num),mid+1,r);
}
int main() {
    scanf("%d%d",&n,&m);
    rep(i,1,n)scanf("%lld",&a[i].v),a[i].id=i;
    sort(a+1,a+1+n,cmp);
    rep(i,1,n)fid[a[i].id]=i;
    rep(i,1,n)root[i]=root[i-1],ins(root[i],fid[i],1,n);
    rep(i,1,m) {int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%lld
",a[ask(root[l-1],root[r],k,1,n)]);
    }
    return 0;
}

BZOJ1901

题意：动态区间查询 k-th number
思路：利用静态主席树思想维护权值线段树的前缀和，而本题要维护动态前缀和，那就可以想到利用树状数组，维护动态前缀和。
实现：

实现单点修改操作：主席树的关键 - 保存历史版本，所以显然不能在已经建好的树上操作。需要新开一个节点作为这个位置新的根，在这个位置原来的位置上加一条新链。这个操作我们在实现静态前缀和的时候已经掌握了。前缀和时第i棵树是由第i-1棵树修改得到的，而修改操作中，新的这棵树是由它原先这个位置的值修改得到的。他们的本质都是修改操作。
实现动态前缀和：T[i]表示树状数组中的下表为i代表的区间。利用主席树维护每个位置，前缀和利用树状数组来完成

//bzoj1901 ac
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define mem(W) memset(W,0,sizeof(W))
const int N = 6e4+5;
const int M = 1e4+5;
inline int read() {
    char c=getchar(); int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
using namespace std;
int n,m,a[N];
vector<int> v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
struct node{int l,r,k;bool opt;} A[M];
struct tree{int l,r,num;}T[N*200];
int root[N],tot;
void ins(int &rt,int pre,int p,int l,int r,int d) {
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,l,mid,d);
    else ins(T[rt].r,T[pre].r,p,mid+1,r,d);
}
void update(int p,int v) {
    for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(a[p]),1,num,-1);
    for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(v),1,num,1);
    a[p]=v;
}
int L[N],R[N],cntl,cntr;
int qury(int l,int r,int k) {
    if(l==r)return l;
    int mid=(l+r)>>1,sum=0;
    rep(i,1,cntr) sum+=T[T[R[i]].l].num;
    rep(i,1,cntl) sum-=T[T[L[i]].l].num;

    if(k<=sum) {
        rep(i,1,cntl) L[i]=T[L[i]].l;
        rep(i,1,cntr) R[i]=T[R[i]].l;
        return qury(l,mid,k);
    }
    else {
        rep(i,1,cntl) L[i]=T[L[i]].r;
        rep(i,1,cntr) R[i]=T[R[i]].r;
        return qury(mid+1,r,k-sum);
    }
}
int main() {
    int K;
    scanf("%d",&K);
    while(K--) {char s[5];
        scanf("%d%d",&n,&m); v.clear(); tot=0; mem(root);mem(T);
        rep(i,1,n) scanf("%d",a+i), v.pb(a[i]);
        rep(i,1,m) {
            scanf(" %s",s);
            if(s[0]=='Q')A[i].opt=1,scanf("%d%d%d",&A[i].l,&A[i].r,&A[i].k);
            else A[i].opt=0,scanf("%d%d",&A[i].l,&A[i].r),v.pb(A[i].r);
        }
        sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
        num = v.size();
        rep(i,1,n) for(int j=i;j<=n;j+=(j&(-j))) ins(root[j],root[j],id(a[i]),1,num,1);
        rep(ti,1,m) {
            if(A[ti].opt) {
                cntl=cntr=0;
                for(int i=A[ti].l-1;i;i-=(i&(-i))) L[++cntl]=root[i];
                for(int i=A[ti].r;i;i-=(i&(-i))) R[++cntr]=root[i];
                printf("%d
",v[qury(1,num,A[ti].k)-1]);
            }
            else
                update(A[ti].l,A[ti].r);
        }
    }
    return 0;
}

ZOJ2112

题意：与BZOJ1901相同，动态区间查询 k-th number，内存限制
思路：如果用上题的做法，内存无法接受。那么思考有什么地方可以减少节点的数量。注意到一开始读入的n个数，完全可以与后面的操作独立开，一颗静态的主席树，一颗用来修改，查询时将两棵树的信息合并即可。这样这n棵数的空间复杂度少了一个树状数组的log

//bzoj1901 ac
//zoj2112 ac
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define mem(W) memset(W,0,sizeof(W))
const int N = 6e4+5;
const int M = 1e4+5;
inline int read() {
    char c=getchar(); int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
using namespace std;
int n,m,a[N];
vector<int> v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
struct node{int l,r,k;bool opt;} A[M];
struct tree{int l,r,num;}T[N*32];
int root[N],root0[N],tot;
void ins(int &rt,int pre,int p,int l,int r,int d) {
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,l,mid,d);
    else ins(T[rt].r,T[pre].r,p,mid+1,r,d);
}
void update(int p,int v) {
    for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(a[p]),1,num,-1);
    for(int i=p;i<=n;i+=(i&-i)) ins(root[i],root[i],id(v),1,num,1);
    a[p]=v;
}
int L[N],R[N],cntl,cntr;
int qury(int l,int r,int ls,int rs,int k) {
    if(l==r)return l;
    int mid=(l+r)>>1,sum=0;
    rep(i,1,cntr) sum+=T[T[R[i]].l].num;
    rep(i,1,cntl) sum-=T[T[L[i]].l].num;
    sum += (T[T[rs].l].num-T[T[ls].l].num);
    if(k<=sum) {
        rep(i,1,cntl) L[i]=T[L[i]].l;
        rep(i,1,cntr) R[i]=T[R[i]].l;
        return qury(l,mid,T[ls].l,T[rs].l,k);
    }
    else {
        rep(i,1,cntl) L[i]=T[L[i]].r;
        rep(i,1,cntr) R[i]=T[R[i]].r;
        return qury(mid+1,r,T[ls].r,T[rs].r,k-sum);
    }
}
int main() {
    int K;
    scanf("%d",&K);
    while(K--) {char s[5];
        scanf("%d%d",&n,&m); v.clear(); tot=0; mem(root);mem(T);
        rep(i,1,n) scanf("%d",a+i), v.pb(a[i]);
        rep(i,1,m) {
            scanf(" %s",s);
            if(s[0]=='Q')A[i].opt=1,scanf("%d%d%d",&A[i].l,&A[i].r,&A[i].k);
            else A[i].opt=0,scanf("%d%d",&A[i].l,&A[i].r),v.pb(A[i].r);
        }
        sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
        num = v.size();
        rep(i,1,n) root0[i]=root0[i-1],ins(root0[i],root0[i],id(a[i]),1,num,1);
        rep(ti,1,m) {
            if(A[ti].opt) {
                cntl=cntr=0;
                for(int i=A[ti].l-1;i;i-=(i&(-i))) L[++cntl]=root[i];
                for(int i=A[ti].r;i;i-=(i&(-i))) R[++cntr]=root[i];
                printf("%d
",v[qury(1,num,root0[A[ti].l-1],root0[A[ti].r],A[ti].k)-1]);
            }
            else
                update(A[ti].l,A[ti].r);
        }
    }
    return 0;
}

洛谷P3567

题意：静态区间查询出现大于(r-l+1)/2次的数。
思路：出现超过(r-l+1)/2次的数至多有一个，所以直接在静态主席树上查询，区间内大于(r-l+1)/2的位置即可，与静态区间第k大的区别就是递归到右边时，不修改k值

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long ll;
const int N = 500000+100;
using namespace std;
int n,m,a[N];
struct chair_tree{int l,r,num;}T[N*30];
int root[N],tot;
void ins(int &rt,int pre,int p,int d,int l,int r) {
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r)return;
    int mid = (l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);
    else ins(T[rt].r,T[pre].r,p,d,mid+1,r);
}
int ask(int rtl,int rtr,int l,int r,int X) {
    if(l==r) return l;
    int mid = (l+r)>>1;
    if((T[T[rtr].l].num-T[T[rtl].l].num)*2>X) return ask(T[rtl].l,T[rtr].l,l,mid,X);
    else if((T[T[rtr].r].num-T[T[rtl].r].num)*2>X) return ask(T[rtl].r,T[rtr].r,mid+1,r,X);
    else return 0;
}
int main() {
    scanf("%d%d",&n,&m);
    rep(i,1,n)scanf("%d",&a[i]);
    rep(i,1,n)ins(root[i],root[i-1],a[i],1,1,n);
    rep(i,1,m) {int l,r;
        scanf("%d%d",&l,&r);
        printf("%d
",ask(root[l-1],root[r],1,n,r-l+1));
    }
    return 0;
}

BZOJ2588

题意：无修改树上查询路径上的第k大
思路：考虑如何树上主席树，对每个从根节点延伸出的链，建前缀的主席树。那么这条路径上就是：
(u的值 + v的值 - lca(u,v)的值 - fa[lca(u,v)]的值), 其他与静态区间第k大一致。
lca求法：倍增5260 ms，树剖3900 ms

倍增lca

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long ll;
const int N = 1e5 + 100;
using namespace std;
int n,m,a[N];
vector<int> v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
struct edge{int e,nxt;}E[N<<1];
int h[N],cc;
void add(int u,int v) {
    ++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc;
}
int fa[N][20],dep[N];
int lca(int u,int v) {
    if(dep[u]<dep[v])swap(u,v);
    for(int i=17;i>=0;--i)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    if(u==v)return u;
    for(int i=17;i>=0;--i) {
        if(fa[v][i]!=fa[u][i])v=fa[v][i],u=fa[u][i];
    }
    return fa[v][0];
}
struct chair_tree{int l,r,num;}T[N*20];
int root[N], tot;
void ins(int &rt,int pre,int p,int d,int l,int r) {
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);
    else ins(T[rt].r,T[pre].r,p,d,mid+1,r);
}
int vis[N];
void build_T() {
    queue<int> q;
    q.push(0);vis[0]=1;dep[0]=0;
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
        for(int i=h[u];~i;i=E[i].nxt) {
            int v=E[i].e;
            if(!vis[v]) {
                vis[v]=1;
                fa[v][0]=u;
                dep[v]=dep[u]+1;
                ins(root[v],root[u],id(a[v]),1,1,num);
                q.push(v);
            }
        }
    }
}
int ask(int ur,int vr,int lcar,int lcafr,int k,int l,int r) {
    if(l==r) return l;
    int mid=(l+r)>>1,sum=0;
    sum = T[T[ur].l].num - T[T[lcar].l].num + T[T[vr].l].num - T[T[lcafr].l].num;
    if(sum>=k) return ask(T[ur].l,T[vr].l,T[lcar].l,T[lcafr].l,k,l,mid);
    else return ask(T[ur].r,T[vr].r,T[lcar].r,T[lcafr].r,k-sum,mid+1,r);
}
int main() {
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&a[i]),v.pb(a[i]);
    sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
    num = v.size();
    memset(h,-1,sizeof(h));
    rep(i,1,n-1) {int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    a[0]=0; add(0,1),add(1,0);
    build_T();
    int lastans=0;
    rep(ti,1,m) {int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        x^=lastans;
        lastans = v[ask(root[x],root[y],root[lca(x,y)],root[fa[lca(x,y)][0]],k,1,num)-1];
        printf("%d
",lastans);
    }
    return 0;
}

树剖lca

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long ll;
const int N = 1e5 + 100;
using namespace std;
int n,m,a[N];
vector<int> v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
struct chair_tree{int l,r,num;}T[N*50];
int root[N], tot;
void ins(int &rt,int pre,int p,int d,int l,int r) {
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);
    else ins(T[rt].r,T[pre].r,p,d,mid+1,r);
}

struct edge{int e,nxt;}E[N<<1];
int h[N],cc;
void add(int u,int v) {
    ++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc;
}
int dep[N],fa[N],son[N],sz[N],top[N];
void dfs1(int u,int pre,int d) {
    dep[u]=d;
    fa[u]=pre;
    sz[u]=1;
    for(int i=h[u];~i;i=E[i].nxt) {
        int v=E[i].e;
        if(v!=pre) {
            ins(root[v],root[u],id(a[v]),1,1,num);
            dfs1(v,u,d+1);
            sz[u]+=sz[v];
            if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;
        }
    }
}
void dfs2(int u,int sp) {
    top[u]=sp;
    if(son[u]==-1)return;
    dfs2(son[u],sp);
    for(int i=h[u];~i;i=E[i].nxt) {
        int v=E[i].e;
        if(v!=fa[u]&&v!=son[u])dfs2(v,v);
    }
}
void init() {
    memset(son,-1,sizeof(son));
    dfs1(0,-1,1);
    dfs2(0,0);
}
int 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])swap(u,v);
    return u;
}
int ask(int ur,int vr,int lcar,int lcafr,int k,int l,int r) {
    if(l==r) return l;
    int mid=(l+r)>>1,sum=0;
    sum = T[T[ur].l].num - T[T[lcar].l].num + T[T[vr].l].num - T[T[lcafr].l].num;
    if(sum>=k) return ask(T[ur].l,T[vr].l,T[lcar].l,T[lcafr].l,k,l,mid);
    else return ask(T[ur].r,T[vr].r,T[lcar].r,T[lcafr].r,k-sum,mid+1,r);
}
int main() {
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&a[i]),v.pb(a[i]);
    sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
    num = v.size();
    memset(h,-1,sizeof(h));
    rep(i,1,n-1) {int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    a[0]=0; add(0,1),add(1,0);
    init();
    int lastans=0;
    rep(ti,1,m) {int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        x^=lastans;
        lastans = v[ask(root[x],root[y],root[lca(x,y)],root[fa[lca(x,y)]],k,1,num)-1];
        if(ti!=m)printf("%d
",lastans);
        else printf("%d",lastans);
    }
    return 0;
}

洛谷P4175

题意：带修改树上查询路径上的第k大
思路1：在前一题的基础上，考虑如何修改。当一个节点更新之后受影响的只有它的子树，处理dfs序，对于节点i相当于要修改([ L[i],R[i] ])这个区间的值，树状数组差分实现区间修改单点查询。
询问方法：看大佬Blog都是，直接将[1,L[i]]当作树上根到节点i的前缀，套用常规静态的方法。讲道理，感觉很奇怪。。。但还是过了
思路2：把修改改成单点修改，树剖的做法，也可以过，这个正确性很显然了。

做法1：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long ll;
inline int read() {
    char c=getchar();int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
using namespace std;
const int N = 1e5 + 100;
struct Q{int a,b,k;}q[N];
struct edge{int e,nxt;}E[N<<1];
int h[N],cc;
void add(int u,int v) {++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc;}
int n,m,a[N];
vector<int> mp;
int num;
int id(int x){return lower_bound(mp.begin(),mp.end(),x)-mp.begin()+1;}

struct chiarman{int l,r,num;}T[N*200];
int tot,rt[N],rtc[N]; 
void ins(int &rt,int pre,int p,int d,int l,int r) {
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);
    else ins(T[rt].r,T[pre].r,p,d,mid+1,r);
}


int dep[N],fa[N],son[N],sz[N],top[N],tid[N],L[N],R[N],pos;
void dfs1(int u,int pre,int d) {
    dep[u]=d;
    fa[u]=pre;
    sz[u]=1;
    for(int i=h[u];~i;i=E[i].nxt) {
        int v=E[i].e;
        if(v!=pre) {
            dfs1(v,u,d+1);
            sz[u]+=sz[v];
            if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;
        }
    }
}
void dfs2(int u,int sp) {
    top[u]=sp;
    L[u]=tid[u]=++pos;
    if(son[u]==-1)return;
    dfs2(son[u],sp);
    for(int i=h[u];~i;i=E[i].nxt) {
        int v=E[i].e;
        if(v!=fa[u]&&v!=son[u])dfs2(v,v);
    }
    R[u]=pos;
}
void init_tp() {
    memset(son,-1,sizeof(son));
    dfs1(1,0,1);
    dfs2(1,1);
}
int 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])swap(u,v);
    return u;
}

void build(int u){
    if(u==-1) return;
    ins(rt[u],rt[fa[u]],id(a[u]),1,1,num);
    build(son[u]);
    for(int i=h[u];~i;i=E[i].nxt)
        if(E[i].e!=fa[u]&&E[i].e!=son[u]) build(E[i].e);
}


void B_add(int x,int p,int d){
    for(int i=x;i<=pos;i+=(i&-i)) ins(rtc[i],rtc[i],p,d,1,num);
}


vector<int> A,B;
int ck(int k) {
    int sum=0;
    rep(i,0,A.size()-1)sum+=T[A[i]].num;
    rep(i,0,B.size()-1)sum-=T[B[i]].num;
    return (sum>=k);
}
int qury(int l,int r,int k) {
    if(l==r)return l;
    int mid=(l+r)>>1,sum=0;
    rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;
    rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;
    if(sum>=k) {
        rep(i,0,A.size()-1)A[i]=T[A[i]].r;
        rep(i,0,B.size()-1)B[i]=T[B[i]].r;
        return qury(mid+1,r,k);
    }
    else {
        rep(i,0,A.size()-1)A[i]=T[A[i]].l;
        rep(i,0,B.size()-1)B[i]=T[B[i]].l;
        return qury(l,mid,k-sum);
    }
}
int cal() {
    int sum=0;
    rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;
    rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;
    return sum;
}
void chai(int u,int v) {
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        for(int i=tid[u];i;i-=(i&-i))A.pb(rtc[i]);
        for(int i=tid[top[u]]-1;i;i-=(i&-i))B.pb(rtc[i]);

        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    for(int i=tid[v];i;i-=(i&-i))A.pb(rtc[i]);
    for(int i=tid[u]-1;i;i-=(i&-i))B.pb(rtc[i]);
    return ;
}

void ask(int u,int v,int k) {
    int p=lca(u,v);
    A.clear();B.clear();
    A.pb(rt[u]),A.pb(rt[v]),B.pb(rt[p]),B.pb(rt[fa[p]]);
    chai(u,v);

    if(!ck(k)) {puts("invalid request!");return;}
    printf("%d
",mp[qury(1,num,k)-1]);
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    memset(son,-1,sizeof(son));
    rep(i,1,n) a[i] = read(), mp.pb(a[i]);
    rep(i,1,n-1) {int u=read(),v=read();add(u,v),add(v,u);}
    rep(i,1,m) {q[i].k=read(),q[i].a=read(),q[i].b=read();if(q[i].k==0)mp.pb(q[i].b);}
    sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end());
    num = mp.size();

    init_tp();

    build(1);

    rep(i,1,m) {
        if(q[i].k==0) {
            B_add(tid[q[i].a],id(a[q[i].a]),-1);
            a[q[i].a]=q[i].b;
            B_add(tid[q[i].a],id(a[q[i].a]),1);
        }
        else {
            ask(q[i].a,q[i].b,q[i].k);
        }
    }
    return 0;
}

做法2：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long ll;
inline int read() {
    char c=getchar();int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
using namespace std;
const int N = 1e5 + 100;
struct Q{int a,b,k;}q[N];
struct edge{int e,nxt;}E[N<<1];
int h[N],cc;
void add(int u,int v) {++cc;E[cc].e=v;E[cc].nxt=h[u];h[u]=cc;}
int n,m,a[N];
vector<int> mp;
int num;
int id(int x){return lower_bound(mp.begin(),mp.end(),x)-mp.begin()+1;}

struct chiarman{int l,r,num;}T[N*200];
int tot,rt[N],rtc[N]; 
void ins(int &rt,int pre,int p,int d,int l,int r) {
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);
    else ins(T[rt].r,T[pre].r,p,d,mid+1,r);
}


int dep[N],fa[N],son[N],sz[N],top[N],tid[N],L[N],R[N],pos;
void dfs1(int u,int pre,int d) {
    dep[u]=d;
    fa[u]=pre;
    sz[u]=1;
    for(int i=h[u];~i;i=E[i].nxt) {
        int v=E[i].e;
        if(v!=pre) {
            dfs1(v,u,d+1);
            sz[u]+=sz[v];
            if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;
        }
    }
}
void dfs2(int u,int sp) {
    top[u]=sp;
    L[u]=tid[u]=++pos;
    if(son[u]==-1)return;
    dfs2(son[u],sp);
    for(int i=h[u];~i;i=E[i].nxt) {
        int v=E[i].e;
        if(v!=fa[u]&&v!=son[u])dfs2(v,v);
    }
    R[u]=pos;
}
void init_tp() {
    memset(son,-1,sizeof(son));
    dfs1(1,0,1);
    dfs2(1,1);
}
int 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])swap(u,v);
    return u;
}

void build(int u){
    if(u==-1) return;
    ins(rt[u],rt[fa[u]],id(a[u]),1,1,num);
    build(son[u]);
    for(int i=h[u];~i;i=E[i].nxt)
        if(E[i].e!=fa[u]&&E[i].e!=son[u]) build(E[i].e);
}


void B_add(int x,int p,int d){
    for(int i=x;i<=pos;i+=(i&-i)) ins(rtc[i],rtc[i],p,d,1,num);
}

vector<int> A,B;
int ck(int k) {
    int sum=0;
    rep(i,0,A.size()-1)sum+=T[A[i]].num;
    rep(i,0,B.size()-1)sum-=T[B[i]].num;
    return (sum>=k);
}
int qury(int l,int r,int k) {
    if(l==r)return l;
    int mid=(l+r)>>1,sum=0;
    rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;
    rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;
    if(sum>=k) {
        rep(i,0,A.size()-1)A[i]=T[A[i]].r;
        rep(i,0,B.size()-1)B[i]=T[B[i]].r;
        return qury(mid+1,r,k);
    }
    else {
        rep(i,0,A.size()-1)A[i]=T[A[i]].l;
        rep(i,0,B.size()-1)B[i]=T[B[i]].l;
        return qury(l,mid,k-sum);
    }
}
int cal() {
    int sum=0;
    rep(i,0,A.size()-1)sum+=T[T[A[i]].r].num;
    rep(i,0,B.size()-1)sum-=T[T[B[i]].r].num;
    return sum;
}
void chai(int u,int v) {
    while(top[u]!=top[v]) {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        for(int i=tid[u];i;i-=(i&-i))A.pb(rtc[i]);
        for(int i=tid[top[u]]-1;i;i-=(i&-i))B.pb(rtc[i]);

        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    for(int i=tid[v];i;i-=(i&-i))A.pb(rtc[i]);
    for(int i=tid[u]-1;i;i-=(i&-i))B.pb(rtc[i]);
    return ;
}

void ask(int u,int v,int k) {
    int p=lca(u,v);
    A.clear();B.clear();
    A.pb(rt[u]),A.pb(rt[v]),B.pb(rt[p]),B.pb(rt[fa[p]]);
    chai(u,v);

    if(!ck(k)) {puts("invalid request!");return;}
    printf("%d
",mp[qury(1,num,k)-1]);
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    memset(son,-1,sizeof(son));
    rep(i,1,n) a[i] = read(), mp.pb(a[i]);
    rep(i,1,n-1) {int u=read(),v=read();add(u,v),add(v,u);}
    rep(i,1,m) {q[i].k=read(),q[i].a=read(),q[i].b=read();if(q[i].k==0)mp.pb(q[i].b);}
    sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end());
    num = mp.size();

    init_tp();

    build(1);

    rep(i,1,m) {
        if(q[i].k==0) {
            B_add(tid[q[i].a],id(a[q[i].a]),-1);
            a[q[i].a]=q[i].b;
            B_add(tid[q[i].a],id(a[q[i].a]),1);
        }
        else {
            ask(q[i].a,q[i].b,q[i].k);
        }
    }
    return 0;
}

BZOJ2212

题意：现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。要求进行一系列交换，使得最终所有叶子节点的权值按照遍历序写出来，逆序对个数最少。
思路：动态开点，给每个叶子节点开一颗权值线段树，自底向上合并线段树，合并的过程中通过左右子树的权值线段树计算逆序数。
线段树合并及复杂度分析：大佬的Blog

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;
const int N = 8000010;
using namespace std;
int n,rt;
struct tr{int l,r,num;}tree[N],T[N];
int cc,tot,root[N];
void build(int &rt) {
    rt = ++cc;
    int x;
    scanf("%d",&x);
    if(x) tree[rt].num=x;
    else build(tree[rt].l),build(tree[rt].r);
}
void ins(int &rt,int pre,int p,int d,int l,int r){
    rt=++tot;T[rt]=T[pre];T[rt].num+=d;
    if(l==r){T[rt].num=1;return;}
    int mid=(l+r)>>1;
    if(p<=mid) ins(T[rt].l,T[pre].l,p,d,l,mid);
    else ins(T[rt].r,T[pre].r,p,d,mid+1,r);
    T[rt].num = T[T[rt].l].num + T[T[rt].r].num;
}
ll ans1,ans2,ans;
int merge(int x,int y) {
    if(!x)return y;
    if(!y)return x;
    ans1 += 1LL*T[T[x].l].num*T[T[y].r].num;
    ans2 += 1LL*T[T[x].r].num*T[T[y].l].num;
    T[x].l = merge(T[x].l,T[y].l);
    T[x].r = merge(T[x].r,T[y].r);
    T[x].num = T[T[x].l].num + T[T[x].r].num;
    return x;
}
void solve(int rt) {
    if(tree[rt].num) return;
    solve(tree[rt].l),solve(tree[rt].r);
    ans1=ans2=0;
    root[rt] = merge(root[tree[rt].l],root[tree[rt].r]);
    ans+=min(ans1,ans2);
}
int main() {
    scanf("%d",&n);
    build(rt);
    rep(i,1,cc)if(tree[i].num)ins(root[i],root[i],tree[i].num,1,1,n);
    solve(rt);
    printf("%lld
",ans);
    return 0;
}

主席树学习笔记 主席树学习笔记

说在前边：

POJ2104

BZOJ1901

ZOJ2112

洛谷P3567

BZOJ2588

洛谷P4175

BZOJ2212

这个专题就先到这了。。。

相关推荐

主席树学习笔记主席树学习笔记