【xsy1629】可持久化序列 - 可持久化平衡树
http://www.cnblogs.com/Sdchr/p/6258827.html
【bzoj4260】REBXOR - Trie
事实上只是一道Trie树的题。
只是被林导钦定成可持久化的了。
区间异或和,转化为前缀异或和。
预处理向前最大的异或和,向后最大的异或和,和前缀最大异或和,枚举分割点求答案。
#include <cstdio>
#include <cctype>
#include <climits>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
const int N=524288;
const int B=30;
const int S=16777216;
const int MIN=INT_MIN;
int n;
int a[N];
int pre[N],tot_Pre[N];
int suf[N];
int res;
namespace Trie {
int rt,tot;
struct Node {
int c[2];
Node(void) {
c[0]=c[1]=0;
}
}tr[S];
void Init(void) {
rep(i,1,tot) tr[i]=Node();
rt=tot=1;
}
void Ins(int &x,int num,int bit) {
if (!x) x=++tot;
if (bit==-1) return;
Ins(tr[x].c[num>>bit&1],num,bit-1);
}
int Query_Max(int x,int num,int bit) {
if (bit==-1) return 0;
int dir=((num>>bit&1)^1);
if (tr[x].c[dir]>0) {
int t=Query_Max(tr[x].c[dir],num,bit-1);
return t+(1<<bit);
}
else {
int t=Query_Max(tr[x].c[dir^1],num,bit-1);
return t;
}
}
}
using namespace Trie;
int rd(void) {
int x=0,f=1; char c=getchar();
while (!isdigit(c)) {
if (c=='-') f=-1;
c=getchar();
}
while (isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=rd();
rep(i,1,n) a[i]=rd();
rep(i,1,n) a[i]^=a[i-1];
Init();
rep(i,1,n) {
Ins(rt,a[i-1],B);
pre[i]=Query_Max(rt,a[i],B);
}
tot_Pre[1]=pre[1];
rep(i,2,n)
tot_Pre[i]=max(tot_Pre[i-1],pre[i]);
Init();
per(i,n,1) {
Ins(rt,a[i],B);
suf[i]=Query_Max(rt,a[i-1],B);
}
res=MIN;
per(i,n,2) {
int t=tot_Pre[i-1]+suf[i];
res=max(res,t);
}
printf("%d\n",res);
return 0;
}
【bzoj3439】Kpm的MC密码 - Trie + Treap启发式合并
传送门
http://www.lydsy.com/JudgeOnline/problem.php?id=3439
分析
把串反过来,那么相当于问每一个字符串的后缀中编号第\(k\)小的。
考虑建一棵Trie,那么就是询问某个子树内编号的第\(k\)小。
方法1:
转化为dfs序,用可持久化线段树来求解。
或者离线后乱搞。
方法2:
把Trie进行DFS,启发式合并。
代码
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define VI vector<int>
#define pb push_back
const int L=524288;
const int A=26;
const int N=131072;
int n;
char s[L];
int rt,tot;
struct Trie {
int c[A];
VI pt;
}tr[L];
int k[N];
int ans[N];
int root[L]; //int tot;
struct Treap {
int c[2];
int key,fix;
int siz;
Treap(int _key=0,int _siz=0) {
c[0]=c[1]=0;
key=_key,fix=rand();
siz=_siz;
}
}trp[L];
struct D {
int c[2];
D(void) {
c[0]=c[1]=0;
}
};
void Ins_Trie(int &x,char *s,int len,int id) {
if (!x) x=++tot;
if (!len) {
tr[x].pt.pb(id);
return;
}
Ins_Trie(tr[x].c[s[len]-'a'],s,len-1,id);
}
int New_Node(int key) {
int x=++tot;
trp[x]=Treap(key,1);
return x;
}
void Update(int x) {
trp[x].siz=trp[trp[x].c[0]].siz+trp[trp[x].c[1]].siz+1;
}
int Merge(int x1,int x2) {
if (!x1) return x2;
if (!x2) return x1;
if (trp[x1].fix<trp[x2].fix) {
trp[x1].c[1]=Merge(trp[x1].c[1],x2);
Update(x1);
return x1;
}
else {
trp[x2].c[0]=Merge(x1,trp[x2].c[0]);
Update(x2);
return x2;
}
}
D Split_Key(int x,int key) {
D t; if (!x) return t;
if (key<trp[x].key) {
t=Split_Key(trp[x].c[0],key);
trp[x].c[0]=t.c[1]; Update(x);
t.c[1]=x;
}
else {
t=Split_Key(trp[x].c[1],key);
trp[x].c[1]=t.c[0]; Update(x);
t.c[0]=x;
}
return t;
}
D Split(int x,int rk) {
D t; if (!x) return t;
if (rk<=trp[trp[x].c[0]].siz) {
t=Split(trp[x].c[0],rk);
trp[x].c[0]=t.c[1]; Update(x);
t.c[1]=x;
}
else if (rk==trp[trp[x].c[0]].siz+1) {
t.c[1]=trp[x].c[1];
trp[x].c[1]=0; Update(x);
t.c[0]=x;
}
else {
t=Split(trp[x].c[1],rk-1-trp[trp[x].c[0]].siz);
trp[x].c[1]=t.c[0]; Update(x);
t.c[0]=x;
}
return t;
}
void Add_Point(int &to,int x) {
D t=Split_Key(to,trp[x].key);
to=Merge(t.c[0],x); to=Merge(to,t.c[1]);
}
void Add_Tree(int &to,int x) {
if (!x) return;
Add_Tree(to,trp[x].c[0]);
Add_Tree(to,trp[x].c[1]);
trp[x].c[0]=trp[x].c[1]=0; Update(x);
Add_Point(to,x);
}
int Join(int x1,int x2) {
if (trp[x1].siz<trp[x2].siz) swap(x1,x2);
Add_Tree(x1,x2);
return x1;
}
int Query_Kth(int x,int rk) {
int siz=trp[x].siz;
if (!(1<=rk&&rk<=siz)) return -1;
D t1=Split(x,rk-1);
D t2=Split(t1.c[1],1);
int g=trp[t2.c[0]].key;
x=Merge(t1.c[0],t2.c[0]); x=Merge(x,t2.c[1]);
return g;
}
void DFS(int x) {
rep(i,0,A-1)
if (tr[x].c[i]>0)
DFS(tr[x].c[i]);
rep(i,0,A-1)
if (tr[x].c[i]>0)
root[x]=Join(root[x],root[tr[x].c[i]]);
rep(i,1,tr[x].pt.size()) {
int p=New_Node(tr[x].pt[i-1]);
Add_Point(root[x],p);
}
rep(i,1,tr[x].pt.size()) {
int p=tr[x].pt[i-1];
ans[p]=Query_Kth(root[x],k[p]);
}
}
int rd(void) {
int x=0,f=1; char c=getchar();
while (!isdigit(c)) {
if (c=='-') f=-1;
c=getchar();
}
while (isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
srand(time(0));
n=rd(); rt=tot=1;
rep(i,1,n) {
scanf("%s",s+1);
Ins_Trie(rt,s,strlen(s+1),i);
}
rep(i,1,n) k[i]=rd();
DFS(rt);
rep(i,1,n)
printf("%d\n",ans[i]);
return 0;
}
小结
(1)对于一棵树上的子树的离线询问,可以考虑使用启发式合并来求解。
(2)树上询问的处理技巧:
- dfs序的性质,虚树
- 树链剖分
- LCT
- 树上倍增,树上倍增dp
- 树上莫队
- 点分治
- 离线dfs,启发式合并
【bzoj3261】最大异或和 - 可持久化Trie
代码
#include <cstdio>
#include <cctype>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
const int LEN=1048576;
const int S=16777216;
const int BIT=23;
int n,a[LEN];
int m;
int tot,rt[LEN],tms;
struct Trie {
int c[2],cnt;
Trie(void) {
c[0]=c[1]=cnt=0;
}
}tr[S];
int rd(void) {
int x=0,f=1; char c=getchar();
while (!isdigit(c)) {
if (c=='-') f=-1;
c=getchar();
}
while (isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int Ins(int x,int bit,int num) {
int now=++tot; tr[now]=tr[x]; tr[now].cnt++;
if (bit==-1) return now;
tr[now].c[num>>bit&1]=Ins(tr[x].c[num>>bit&1],bit-1,num);
return now;
}
int Query(int x1,int x2,int bit,int num) {
if (bit==-1) return 0;
int prefer=((num>>bit&1)^1);
int cnt=tr[tr[x2].c[prefer]].cnt-tr[tr[x1].c[prefer]].cnt;
if (cnt>0) {
int t=Query(tr[x1].c[prefer],tr[x2].c[prefer],bit-1,num);
return t+(1<<bit);
}
else {
int t=Query(tr[x1].c[prefer^1],tr[x2].c[prefer^1],bit-1,num);
return t;
}
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=rd(),m=rd();
rep(i,1,n) a[i]=rd();
rep(i,2,n) a[i]^=a[i-1];
rep(i,0,n)
rt[i]=Ins(rt[i-1],BIT,a[i]);
tms=0;
rep(i,1,m) {
scanf("\n"); char c=getchar();
if (c=='A') {
int x=rd(); a[n+1]=(x^a[n]);
rt[n+1]=Ins(rt[n],BIT,a[n+1]);
n++;
}
else {
int l=rd(),r=rd(),x=rd();
int ans=Query(rt[l-2>=0?l-2:n+1],rt[r-1],BIT,a[n]^x);
printf("%d\n",ans);
}
}
return 0;
}
【bzoj3166】ALO - Treap+可持久化Trie树
枚举次大值的坐标,那么可以通过前驱、后继得到一段区间。
#include <cstdio>
#include <cctype>
#include <ctime>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
const int N=65536;
const int S=2097152;
const int BIT=30;
int n;
int a[N];
int tot,rt[N];
struct Trie {
int c[2]; int cnt;
Trie(void) {
c[0]=c[1]=cnt=0;
}
}tr[S];
int ord[N]; int mx;
int root;
struct Treap {
int c[2];
int key,fix;
int siz;
Treap(int _key=0,int _siz=0) {
c[0]=c[1]=0;
key=_key,fix=rand();
siz=_siz;
}
}p[N];
struct D {
int c[2];
D(void) {
c[0]=c[1]=0;
}
};
int ans;
int rd(void) {
int x=0,f=1; char c=getchar();
while (!isdigit(c)) {
if (c=='-') f=-1;
c=getchar();
}
while (isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int Ins_Trie(int x,int bit,int num) {
int now=++tot; tr[now]=tr[x]; tr[now].cnt++;
if (bit==-1) return now;
tr[now].c[num>>bit&1]=Ins_Trie(tr[x].c[num>>bit&1],bit-1,num);
return now;
}
int Query_Trie(int x1,int x2,int bit,int num) {
if (bit==-1) return 0;
int prefer=((num>>bit&1)^1);
int cnt=tr[tr[x2].c[prefer]].cnt-tr[tr[x1].c[prefer]].cnt;
if (cnt>0) {
int t=Query_Trie(tr[x1].c[prefer],tr[x2].c[prefer],bit-1,num);
return t+(1<<bit);
}
else {
int t=Query_Trie(tr[x1].c[prefer^1],tr[x2].c[prefer^1],bit-1,num);
return t;
}
}
int New_Node(int key) {
int x=++tot;
p[x]=Treap(key,1);
return x;
}
void Update(int x) {
p[x].siz=p[p[x].c[0]].siz+p[p[x].c[1]].siz+1;
}
int Merge(int x1,int x2) {
if (!x1) return x2;
if (!x2) return x1;
if (p[x1].fix<p[x2].fix) {
p[x1].c[1]=Merge(p[x1].c[1],x2);
Update(x1);
return x1;
}
else {
p[x2].c[0]=Merge(x1,p[x2].c[0]);
Update(x2);
return x2;
}
}
D Split_Key(int x,int key) {
D t; if (!x) return t;
if (key<p[x].key) {
t=Split_Key(p[x].c[0],key);
p[x].c[0]=t.c[1]; Update(x);
t.c[1]=x;
}
else {
t=Split_Key(p[x].c[1],key);
p[x].c[1]=t.c[0]; Update(x);
t.c[0]=x;
}
return t;
}
D Split(int x,int rk) {
D t; if (!x) return t;
if (rk<=p[p[x].c[0]].siz) {
t=Split(p[x].c[0],rk);
p[x].c[0]=t.c[1]; Update(x);
t.c[1]=x;
}
else if (rk==p[p[x].c[0]].siz+1) {
t.c[1]=p[x].c[1];
p[x].c[1]=0; Update(x);
t.c[0]=x;
}
else {
t=Split(p[x].c[1],rk-1-p[p[x].c[0]].siz);
p[x].c[1]=t.c[0]; Update(x);
t.c[0]=x;
}
return t;
}
int Pre_Pre(int x) {
D t1=Split_Key(root,x);
int siz=p[t1.c[0]].siz,id;
if (siz==1) {
id=-1;
root=Merge(t1.c[0],t1.c[1]);
}
else if (siz==2) {
id=0;
root=Merge(t1.c[0],t1.c[1]);
}
else {
D t2=Split(t1.c[0],siz-3);
D t3=Split(t2.c[1],1);
id=p[t3.c[0]].key;
root=Merge(t3.c[0],t3.c[1]);
root=Merge(t2.c[0],root);
root=Merge(root,t1.c[1]);
}
return id;
}
int Nxt_Nxt(int x) {
D t1=Split_Key(root,x-1);
int siz=p[t1.c[1]].siz,id;
if (siz==1) {
id=-1;
root=Merge(t1.c[0],t1.c[1]);
}
else if (siz==2) {
id=n+1;
root=Merge(t1.c[0],t1.c[1]);
}
else {
D t2=Split(t1.c[1],2);
D t3=Split(t2.c[1],1);
id=p[t3.c[0]].key;
root=Merge(t3.c[0],t3.c[1]);
root=Merge(t2.c[0],root);
root=Merge(t1.c[0],root);
}
return id;
}
void Insert(int &rt,int key) {
int x=New_Node(key);
D t=Split_Key(rt,key);
rt=Merge(t.c[0],x); rt=Merge(rt,t.c[1]);
}
int cmp(int x,int y) {
return a[x]>a[y];
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
srand(2016+02+20);
n=rd();
rep(i,1,n) a[i]=rd();
mx=*max_element(a+1,a+n+1);
rep(i,1,n)
rt[i]=Ins_Trie(rt[i-1],BIT,a[i]);
rep(i,1,n) ord[i]=i;
sort(ord+1,ord+n+1,cmp);
tot=0;
rep(i,1,n) {
int loc=ord[i];
Insert(root,loc);
int x=Nxt_Nxt(loc);
if (!(x==-1&&mx==a[loc])) {
if (x==-1) x=n+1;
if (loc+1<=x-1) {
int t=Query_Trie(rt[loc],rt[x-1],BIT,a[loc]);
ans=max(ans,t);
}
}
x=Pre_Pre(loc);
if (!(x==-1&&mx==a[loc])) {
if (x==-1) x=0;
if (x+1<=loc-1) {
int t=Query_Trie(rt[x],rt[loc-1],BIT,a[loc]);
ans=max(ans,t);
}
}
}
printf("%d\n",ans);
return 0;
}