# 洛谷P4592 [TJOI2018]异或(可持久化01Trie)

## 题意

```#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 10, SS = MAXN * 42 + 10;
const int B = 31;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, Q, a[MAXN], siz[MAXN], son[MAXN], top[MAXN], fa[MAXN], dep[MAXN], dfn[MAXN], cnt, rev[MAXN];
vector<int> v[MAXN];
struct Trie {
int ch[SS][2], siz[SS], tot, root[SS];
void insert(int &k, int pre, int v) {
k = ++tot; int now = k;
for(int i = B; ~i; i--) {
int nxt = v >> i & 1;
ch[now][nxt ^ 1] = ch[pre][nxt ^ 1];
now = ch[now][nxt] = ++tot; pre = ch[pre][nxt];
siz[now] = siz[pre] + 1;
}
}
int Query1(int pre, int now, int v) {
int ans = 0;
for(int i = B; ~i; i--) {
int nxt = v >> i & 1;
if(siz[ch[now][nxt ^ 1]] - siz[ch[pre][nxt ^ 1]]) ans += (1 << i), now = ch[now][nxt ^ 1], pre = ch[pre][nxt ^ 1];
else now = ch[now][nxt], pre = ch[pre][nxt];
}
return ans;
}
int Query2(int x, int y, int lca, int fafa, int v) {
int ans = 0;
for(int i = B; ~i; i--) {
int nxt = v >> i & 1;
if(siz[ch[x][nxt ^ 1]] + siz[ch[y][nxt ^ 1]] - siz[ch[lca][nxt ^ 1]] - siz[ch[fafa][nxt ^ 1]])
ans += (1 << i), x = ch[x][nxt ^ 1], y = ch[y][nxt ^ 1], lca = ch[lca][nxt ^ 1], fafa = ch[fafa][nxt ^ 1];
else x = ch[x][nxt], y = ch[y][nxt], lca = ch[lca][nxt], fafa = ch[fafa][nxt];
}
return ans;
}
} T[2];
void dfs1(int x, int _fa) {
siz[x] = 1; T[1].insert(T[1].root[x], T[1].root[_fa], a[x]); dep[x] = dep[_fa] + 1;
dfn[x] = ++cnt; rev[cnt] = x; fa[x] = _fa;
for(auto &to : v[x]) {
if(to == _fa) continue;
dfs1(to, x);
siz[x] += siz[to];
if(siz[to] > siz[son[x]]) son[x] = to;
}
}
void dfs2(int x, int topf) {
top[x] = topf;
if(!son[x]) return ;
dfs2(son[x], topf);
for(auto &to : v[x]) {
if(top[to]) continue;
dfs2(to, to);
}
}
int LCA(int x, int y) {
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
signed main() {
for(int i = 1; i <= N; i++) a[i] = read();
for(int i = 1; i <= N - 1; i++) {
v[x].push_back(y);
v[y].push_back(x);
}
dfs1(1, 0);
dfs2(1, 1);
for(int i = 1; i <= N; i++)
T[0].insert(T[0].root[i], T[0].root[i - 1], a[rev[i]]);
while(Q--) {
if(opt == 1) cout << T[0].Query1(T[0].root[dfn[x] - 1], T[0].root[dfn[x] + siz[x] - 1], y) << '\n';
else {
int lca = LCA(x, y);
z = read(), cout << T[1].Query2(T[1].root[x], T[1].root[y], T[1].root[lca], T[1].root[fa[lca]], z) << '\n';
}
}
return 0;
}```

0 条评论

• ### PHP扩展开发（七）Zend 线程安全

在PHP诞生的初期，它总是以单线程的CGI方式运行的，因此，根本不需要考虑多线程问题，因为进程的处理不会超过单个请求。

• ### Infor Baan ERP LN里的On Case用法

对于程序员来讲，if,elseif这种判断语句肯定用的比较多，在asp里有select case，在.net里面有switch case的用法，在Baan里面有...

• ### 【译】JWT – Json Web Token

JWT是一种用于双方之间传递安全信息的简洁的、URL安全的表述性声明规范。JWT作为一个开放的标准（RFC 7519），定义了一种简洁的，自包含的方法用于通信双...

• ### PHP扩展开发（六）PHP扩展生命周期

上述代码经过宏替换之后，实际上是声明了一个名为zend_sample4_globals的结构体。

• ### 分享几个Flowportal.Net BPM中的几个有用的Sql语句

第一个要分享的是获取当前的申请状态以及当前的处理人，虽然我们很容易通过BPMInstProcSteps这张表找到FinishAt is Null的记录，但是如果...

• ### Php扩展开发(四)Php扩展开发相关问题

在./configure的时候，增加选项enable-maintainer-zts将会按照线程安全的方式进行 编译时检查，即使在Cli模式下使用，也会检查是否...

• ### 一段从Infor ERP LN(Baan)的Oracle数据库中导出数据到SQL Server的SQL语句

保存一段从Baan ERP LN的Oracle数据库中导出数据到SQL Server的SQL语句，前提是在MSSQL 2005中建立Link Server。

• ### Vagrant使用技巧

在使用Vagrant过程中，难免会出现一些不稳定的因素而造成一些使用上的bug，因此，Vagrant提供了Debug日志的方式用于调试，可以方便的查找错误的原因...

• ### 【译】YAML格式入门

根据官方的YAML站点所述，YAML是面向所有编程语言的对人类友好的数据序列化标准。

• ### 我的ODP.NET开发之路3-Oracle Package/Procedure/Function

上周的项目进展比较大，完成了几个重大的功能。这其中涉及到在Oracle中创建新表、序列、索引、触发器、包、存储过程、函数，当然了也在实战中学习了几个.Net的D...