可持久化数据结构

可持久化

我居然在这个时候还在学新算法。
好吧，这一切都是为了noip2017DAY1T3列队。表示自己没怎么看懂动态开点线段树。然后就怒学一波主席树。发现也不难啊~为什么才学的时候觉得那么遥不可及。

每次插入，就是建一棵新的树也就是log(n)的空间复杂度。总空间复杂度O(nlogn^2).发现当题目强制在线的时候，主席树才有用处。否则，就直接将询问排序（常数翻倍）。

这题是主席树求区间第k大。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
int n,m,a[maxn],rt[maxn],p,x,y,z;
int cnt,s[maxn];
struct node{
    int lc,rc,val;
}t[maxn << 6];
void inserts(int &u,int l,int r,int a){
    if(!u) u = ++cnt;
    t[u].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(a <= mid) inserts(t[u].lc,l,mid,a);
    else inserts(t[u].rc,mid + 1,r,a);
}
void merge(int &u1,int u2){
    if(!u1) {u1 = u2;return;}
    if(!u2) return;
    t[u1].val += t[u2].val;
    merge(t[u1].lc,t[u2].lc);
    merge(t[u1].rc,t[u2].rc);
}
int query(int u1,int u2,int l,int r,int k){
    if(l == r) return s[l];
    int mid = (l + r) >> 1;
    int tmp = t[t[u1].lc].val - t[t[u2].lc].val;
    if(k <= tmp) return query(t[u1].lc,t[u2].lc,l,mid,k);
    return query(t[u1].rc,t[u2].rc,mid + 1,r,k - tmp);
}
int main(){
//  freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i){scanf("%d",&a[i]);s[i] = a[i];}
    sort(s + 1,s + n + 1);
    p = unique(s + 1,s + n + 1) - s - 1;
    for(int i = 1; i <= p; ++i) {
        inserts(rt[i],1,n,lower_bound(s + 1,s + p + 1,a[i]) - s);
        merge(rt[i],rt[i - 1]);
    }
    while(m--){
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",query(rt[y],rt[x - 1],1,n,z));
    }
    return 0;
}

51NOD 1295 XOR key
给出一个长度为N的正整数数组A，再给出Q个查询，每个查询包括3个数，L, R, X (L <= R)。求A[L] 至 A[R] 这R - L + 1个数中，与X 进行异或运算(Xor)，得到的最大值是多少？

可持久化trie树。
这里把所有rt向后移了一位。因为原题中的L可能为0.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int read(){
    char ch;int op=1;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
    int ret=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
    return ret*op;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10) write(x/10);
    putchar('0'+x%10);
}
const int N=50005,M=3000000;
int n,Q,idx=1,rt[N]={1},son[M][2],sz[M];
void insert(int i,int x){
    int now=rt[i]=++idx;
    int old=rt[i-1];
    for(int i=31;i>=0;--i){
        sz[now]=sz[old]+1;
        int cur=(x>>i)&1;
        son[now][cur^1]=son[old][cur^1];
        son[now][cur]=++idx;
        now=son[now][cur];
        old=son[old][cur];
    }
    sz[now]=sz[old]+1;
}
int query(int l,int r,int x){
    int old=rt[l],now=rt[r],ans=0;
    for(int i=31;i>=0;--i){
        int cur=(x>>i)&1;
        int delta_sze=sz[son[now][!cur]]-sz[son[old][!cur]];
        if(delta_sze) now=son[now][!cur],old=son[old][!cur],ans=ans<<1|1;
        else now=son[now][cur],old=son[old][cur],ans=ans<<1;
    }
    return ans;
}
int main(){
//  freopen("a.txt","r",stdin);
    n=read();Q=read();
    for(int i=1;i<=n;++i)   {
        insert(i,read());
    }
    int l,r,x;
    while(Q--){
        x=read();l=read();r=read();
        write(query(l,r+1,x));
        putchar('\n');
    }
    return 0;
}