可持久化线段树就类似于主席树，所以先不放题了。
bzoj3673||3674 可持久化并查集
思路：用可持久化线段树来维护每个点的fa信息，然后按秩合并（相当于点的高度）查找的时候顺着父亲暴力查找。这里我们可以找到爸爸儿子那一级就可以了，可以省一些时间。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxnode 8000005 using namespace std; int tot=0,fa[maxnode]={0},deep[maxnode]={0},root[200005]={0},ls[maxnode]={0},rs[maxnode]={0},n; void build(int &i,int l,int r) { int mid; if (!i) i=++tot; if (l==r){fa[i]=l;return;} mid=(l+r)/2; build(ls[i],l,mid);build(rs[i],mid+1,r); } int ask(int i,int l,int r,int x) { if (l==r) return i; int mid=(l+r)/2; if (x<=mid) return ask(ls[i],l,mid,x); else return ask(rs[i],mid+1,r,x); } int find(int i,int x) { int j=ask(i,1,n,x); if (x==fa[j]) return j; return find(i,fa[j]); } void merge(int i,int &j,int l,int r,int x,int y) { j=++tot;int mid; if (l==r){fa[j]=y;return;} ls[j]=ls[i];rs[j]=rs[i];mid=(l+r)/2; if (x<=mid) merge(ls[i],ls[j],l,mid,x,y); else merge(rs[i],rs[j],mid+1,r,x,y); } void add(int i,int l,int r,int x) { if (l==r) {++deep[i];return;} int mid=(l+r)/2; if (x<=mid) add(ls[i],l,mid,x); else add(rs[i],mid+1,r,x); } int main() { int m,i,j,a,b,k,p,q,last=0; scanf("%d%d",&n,&m);build(root[0],1,n); for (i=1;i<=m;++i) { scanf("%d",&k); if (k==1) { scanf("%d%d",&a,&b);a^=last;b^=last; root[i]=root[i-1]; p=find(root[i],a);q=find(root[i],b); if (fa[p]==fa[q]) continue; if (deep[p]>deep[q]) swap(p,q); merge(root[i-1],root[i],1,n,fa[p],fa[q]); if (deep[p]==deep[q]) add(root[i],1,n,fa[q]); } if (k==2) {scanf("%d",&a);a^=last;root[i]=root[a];} if (k==3) { scanf("%d%d",&a,&b);a^=last;b^=last; root[i]=root[i-1]; p=find(root[i],a);q=find(root[i],b); if (fa[p]==fa[q]) last=1; else last=0; printf("%d\n",last); } } }
舰队
题目大意：求出原数列的一个区间，选其中一个值使次大值xor这个值最大。
思路：建立一个像主席树的一样的trie，然后对于每个位置求出它左右离他最近的各两个，那它是次大值的区间就是（左2，右1]和[左1，右2），求这几个值可以用链表的思想，从小到大删掉元素，相应的更新。对于这些区间就可以在trie上贪心了（从高位开始，尽量取相反位）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxnode 50005 #define up 30 using namespace std; struct use{ int nn,po; }ai[maxnode]={0}; int trie[1600005][3]={0},mx[maxnode][5]={0},next[maxnode]={0},pre[maxnode]={0},num[maxnode][50]={0}, root[maxnode]={0},tt=0; int cmp(const use&x,const use&y){return x.nn==y.nn ? x.po<y.po : x.nn<y.nn;} int getnum(int x,int i) { int j=0; while(x){num[i][++j]=x%2;x/=2;} } void ins(int x,int &y,int w,int k) { int i,j; trie[y=++tt][2]=trie[x][2]+1; if (w<=0) return; j=num[k][w]; ins(trie[x][j],trie[y][j],w-1,k); trie[y][j^1]=trie[x][j^1]; } int ask(int l,int r,int w,int k) { int j;j=num[k][w]; if (w<=0) return 0; if (trie[trie[r][j^1]][2]-trie[trie[l][j^1]][2]>0) return ask(trie[l][j^1],trie[r][j^1],w-1,k)|(1<<(w-1)); else return ask(trie[l][j],trie[r][j],w-1,k); } int main() { freopen("collection.in","r",stdin); freopen("collection.out","w",stdout); int n,i,j,ans=0; scanf("%d",&n); for (i=1;i<=n;++i) { scanf("%d",&ai[i].nn); getnum(ai[i].nn,i);ai[i].po=i; next[i]=i+1;pre[i]=i-1; }next[0]=1;next[n+1]=n+1;pre[n+1]=n; sort(ai+1,ai+n+1,cmp); for (i=1;i<=n;++i) { mx[ai[i].po][0]=pre[pre[ai[i].po]]; mx[ai[i].po][1]=pre[ai[i].po]; mx[ai[i].po][2]=next[ai[i].po]; mx[ai[i].po][3]=next[next[ai[i].po]]; next[pre[ai[i].po]]=next[ai[i].po]; pre[next[ai[i].po]]=pre[ai[i].po]; } for (i=1;i<=n;++i) ins(root[i-1],root[i],up,i); for (i=1;i<=n;++i) { if (mx[i][1]) ans=max(ans,ask(root[mx[i][0]],root[mx[i][2]-1],up,i)); if (mx[i][2]!=n+1) ans=max(ans,ask(root[mx[i][1]],root[mx[i][3]-1],up,i)); } printf("%d\n",ans); fclose(stdin); fclose(stdout); }