TJOI2018 Day2 T2

TJOI2018 Day2 T2

​​ 求子树或x-y路径上任意一个数和某个数异或值最大

分别dfs序和到根建可持久化trie树

每次加加减减得到互相的关系 在trie树上贪心即可

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;struct node{ int sum[2],ch[2];}tree1[N*33],tree2[N*33];struct node1{ int y,next;}data[N<<1];int h[N],cnt1,cnt2,num,rt1[N],rt2[N],fa[N][20],v[N],dep[N],Log[N],n,q,in[N],out[N],ans,bin[33];inline void init1(int &x){tree1[++cnt1]=tree1[x];x=cnt1;}inline void insert1(int &x,int v){ init1(x);int p=x; for (int i=30,op;~i;--i){ op=(v&bin[i])>0; ++tree1[p].sum[op];init1(tree1[p].ch[op]);p=tree1[p].ch[op]; }}inline void init2(int &x){tree2[++cnt2]=tree2[x];x=cnt2;}inline void insert2(int &x,int v){ init2(x);int p=x; for (int i=30,op;~i;--i){ op=(v&bin[i])>0; ++tree2[p].sum[op];init2(tree2[p].ch[op]);p=tree2[p].ch[op]; }}inline void query1(int rt1,int rt2,int v){ for (int i=30,op;~i;--i){ op=(v&bin[i])>0; if (tree1[rt2].sum[op^1]-tree1[rt1].sum[op^1]){ ans+=bin[i];rt2=tree1[rt2].ch[op^1];rt1=tree1[rt1].ch[op^1]; }else rt2=tree1[rt2].ch[op],rt1=tree1[rt1].ch[op]; }}inline void query2(int rt1,int rt2,int rt3,int rt4,int v){ for (int i=30,op;~i;--i){ op=(v&bin[i])>0; if (tree2[rt4].sum[op^1]+tree2[rt3].sum[op^1]-tree2[rt2].sum[op^1]-tree2[rt1].sum[op^1]){ rt4=tree2[rt4].ch[op^1];rt3=tree2[rt3].ch[op^1];ans+=bin[i]; rt2=tree2[rt2].ch[op^1];rt1=tree2[rt1].ch[op^1]; }else{ rt4=tree2[rt4].ch[op];rt3=tree2[rt3].ch[op]; rt2=tree2[rt2].ch[op];rt1=tree2[rt1].ch[op]; } }}inline void dfs(int x){ in[x]=++num;rt1[in[x]]=rt1[in[x]-1];insert1(rt1[in[x]],v[x]);insert2(rt2[x],v[x]); for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa[x][0]) continue; fa[y][0]=x;dep[y]=dep[x]+1;rt2[y]=rt2[x]; for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1];dfs(y); }out[x]=num;}inline int lca(int x,int y){ if (dep[x]>1]+1; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。