主席树

wuhuangjian · 2019-08-29 18:28:44 · 个人记录

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

此线段树维护权值而非编号，记录每个权值出现的次数，代码中sum的可信性就在于此

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
typedef long long LL;
const int N=2e5+5;
struct node{
    int val, l, r;
}t[N*20];
LL a[N], b[N];
int rt[N],tot;
void insert(int &x, int y, int l, int r, int k){
    x = ++tot; 
    t[x] = t[y],t[x].val++;
    if (l == r) return;
    if (k <= mid) insert(t[x].l, t[y].l, l, mid, k);
    else insert(t[x].r, t[y].r, mid + 1, r, k);
}
int query(int x, int y, int l, int r, int k){
    if (l==r) return l;
    int sum = t[t[y].l].val - t[t[x].l].val;
    if (sum >= k) return query(t[x].l, t[y].l, l, mid, k);
    else return query(t[x].r, t[y].r, mid + 1, r, k - sum);
}
int main(){
    int n, m;
    cin>>n>>m;
    for (int i=1; i<=n; i++) scanf("%lld", &a[i]), b[i] = a[i];
    sort(b+1,b+n+1);
    int cnt = unique(b+1,b+n+1) - (b+1);
    for (int i=1; i<=n; i++) a[i] = lower_bound(b+1,b+cnt+1,a[i]) - b;
    for (int i=1; i<=n; i++) insert(rt[i], rt[i - 1], 1, cnt, (int)a[i]);//插入n条链 
    while (m--){
        int x, y, k;
        scanf("%d%d%d", &x, &y, &k);
        printf("%lld\n", b[query(rt[x - 1], rt[y], 1, cnt, k)]);
    }
}

P3302 [SDOI2013]森林

这道题考察了主席树、LCA、启发式合并、离散化等很多知识点。

做了很久

#include<bits/stdc++.h>
#define res register int
#define mid ((l+r)>>1)
using namespace std;
typedef long long LL;
const int N=1e5+5;
struct node{
    int val, l, r;
}t[N<<7];
int a[N], b[N],dep[N],dis[21][N];
int rt[N],tot,n,m,x,y,las,s,from[N],size[N];
int ver[N*2],nxt[N*2],head[N],sum,cnt;
void add(int x,int y){ver[++sum]=y;nxt[sum]=head[x];head[x]=sum;}
void insert(int &x, int y, int l, int r, int k){
    x = ++tot; 
    t[x] = t[y],t[x].val++;
    if (l == r) return;
    if (k <= mid) insert(t[x].l, t[y].l, l, mid, k);
    else insert(t[x].r, t[y].r, mid + 1, r, k);
}
int query(int f,int z,int x, int y, int l, int r, int k){
    if (l==r) return l;
    int sum = t[t[y].l].val+ t[t[x].l].val-t[t[z].l].val-t[t[f].l].val;
    if (sum >= k) return query(t[f].l,t[z].l,t[x].l, t[y].l, l, mid, k);
    else return query(t[f].r,t[z].r,t[x].r, t[y].r, mid + 1, r, k - sum);
}
void dfs(int x,int fa,int root){
    insert(rt[x],rt[fa],1,cnt,a[x]);
    dep[x]=dep[fa]+1;
    size[root]++;from[x]=root;
    dis[0][x]=fa;
    for(res i=1;i<=20;i++)
        dis[i][x]=dis[i-1][dis[i-1][x]];
    for(res i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x,root);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(res i=20;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])x=dis[i][x];
    if(x==y)return x;
    for(res i=20;i>=0;i--)if(dis[i][x]!=dis[i][y])x=dis[i][x],y=dis[i][y];
    return dis[0][x];
}
int main(){
    int T;
    cin>>T;
    cin>>n>>m>>s;
    for (res i=1; i<=n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b+1,b+n+1);
    cnt = unique(b+1,b+n+1) - (b+1);
    for (res i=1; i<=n; i++) a[i] = lower_bound(b+1,b+cnt+1,a[i]) - b;
    for(res i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}
    for(int i=1;i<=cnt;i++)if(!from[i])dfs(i,0,i);

    for(res i=1;i<=s;i++){
        int u, v, k;char ch;cin>>ch;
        if(ch=='Q'){
            scanf("%d%d%d", &u, &v, &k);
            u^=las,v^=las,k^=las;
            int z=lca(u,v);
            las=b[query(rt[dis[0][z]], rt[z],rt[u],rt[v] ,1, cnt, k)];
            printf("%d\n",las);
        }
        else{
            scanf("%d%d", &x, &y);
            x^=las,y^=las;
            add(x,y);add(y,x);
            int fx=from[x],fy=from[y];
            if(size[fy]<size[fx])dfs(y,x,fx);
            else dfs(x,y,fy);
        }
    }
    return 0;
}

P2839 [国家集训队]middle

考虑二分答案