[BZOJ2908]又是nand
试题描述
首先知道A nand B=not(A and B) （运算操作限制了数位位数为K）比如2 nand 3，K=3，则2 nand 3=not (2 and 3)=not 2=5。
给出一棵树，树上每个点都有点权，定义树上从a到b的费用为0与路径上的点的权值顺次nand的结果，例如：从2号点到5号点顺次经过2->3->5，权值分别为5、7、2，K=3，那么最终结果为0 nand 5 nand 7 nand 2=7 nand 7 nand 2=0 nand 2=7，现在这棵树需要支持以下操作。
① Replace a b:将点a（1≤a≤N）的权值改为b。
② Query a b:输出点a到点b的费用。
请众神给出一个程序支持这些操作。
输入
第一行N，M，K，树的节点数量、总操作个数和运算位数。
接下来一行N个数字，依次表示节点i的权值。
接下来N-1行，每行两个数字a,b（1≤a,b≤N）表示a,b间有一条树边。
接下来M行，每行一个操作，为以上2类操作之一。
输出
对于操作②每个输出一行，如题目所述。
输入示例
3 3 3 2 7 3 1 2 2 3 Query 2 3 Replace 1 3 Query 1 1
输出示例
4 7
数据规模及约定
100%的数据N、M≤100000，K≤32
题解
线段树题强行套在树上。。。
注意到 nand 运算没有结合律，所以不能直接维护。进一步分析发现 0 nand x = x nand 0 = 1 (x ∈ {0, 1})，所以我们只用关心一条路径上最后一个 0 的位置，然后数它后面 1 的个数，分奇偶性讨论一下就可以了。注意整条链权值都是 1 的情况特殊处理一下。什么你说我上面只讨论了一位二进制的情况？因为最多不超过 32 位，所以我们建 32 棵线段树就好了。
还有，因为询问有方向，所以线段树需要维护区间中最后一个和最靠前一个 0 的位置。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
#define LL long long
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
LL read() {
LL 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;
}
#define maxn 100005
#define maxm 200005
int n, q, k, m, head[maxn], next[maxm], to[maxm];
LL val[maxn];
void AddEdge(int a, int b) {
to[++m] = b; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; next[m] = head[a]; head[a] = m;
return ;
}
int siz[maxn], son[maxn], fa[maxn], dep[maxn], top[maxn], pos[maxn], w, qos[maxn];
void build(int u) {
siz[u] = 1;
for(int e = head[u]; e; e = next[e]) if(fa[u] != to[e]) {
fa[to[e]] = u;
dep[to[e]] = dep[u] + 1;
build(to[e]);
siz[u] += siz[to[e]];
if(!son[u] || siz[son[u]] < siz[to[e]]) son[u] = to[e];
}
return ;
}
void build(int u, int tp) {
pos[u] = ++w; top[u] = tp; qos[w] = u;
if(son[u]) build(son[u], tp);
for(int e = head[u]; e; e = next[e]) if(to[e] != fa[u] && to[e] != son[u])
build(to[e], to[e]);
return ;
}
int mx[33][maxn<<2], mn[33][maxn<<2];
LL V[maxn];
void build(int t, int L, int R, int o) {
if(L == R) {
int x = V[L] - (V[L] >> (LL)t + 1ll << (LL)t + 1ll) >> (LL)t;
if(x) mx[t][o] = -1, mn[t][o] = n + 1;
else mx[t][o] = mn[t][o] = L;
return ;
}
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
build(t, L, M, lc); build(t, M+1, R, rc);
mx[t][o] = max(mx[t][lc], mx[t][rc]);
mn[t][o] = min(mn[t][lc], mn[t][rc]);
return ;
}
void update(int t, int L, int R, int o, int p) {
if(L == R) {
int x = V[L] - (V[L] >> (LL)t + 1ll << (LL)t + 1ll) >> (LL)t;
if(x) mx[t][o] = -1, mn[t][o] = n + 1;
else mx[t][o] = mn[t][o] = L;
return ;
}
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
if(p <= M) update(t, L, M, lc, p);
else update(t, M+1, R, rc, p);
mx[t][o] = max(mx[t][lc], mx[t][rc]);
mn[t][o] = min(mn[t][lc], mn[t][rc]);
return ;
}
int ql, qr;
int querymx(int t, int L, int R, int o) {
if(ql <= L && R <= qr) return mx[t][o];
int M = L + R >> 1, lc = o << 1, rc = lc | 1, ans = -1;
if(ql <= M) ans = max(ans, querymx(t, L, M, lc));
if(qr > M) ans = max(ans, querymx(t, M+1, R, rc));
return ans;
}
int querymn(int t, int L, int R, int o) {
if(ql <= L && R <= qr) return mn[t][o];
int M = L + R >> 1, lc = o << 1, rc = lc | 1, ans = n + 1;
if(ql <= M) ans = min(ans, querymn(t, L, M, lc));
if(qr > M) ans = min(ans, querymn(t, M+1, R, rc));
return ans;
}
int lca(int a, int b) {
int f1 = top[a], f2 = top[b];
// puts("lcahere");
while(f1 != f2) {
// printf("%d %d %d %d
", a, f1, b, f2);
if(dep[f1] < dep[f2]) swap(f1, f2), swap(a, b);
a = fa[f1]; f1 = top[a];
}
if(dep[a] > dep[b]) swap(a, b);
return a;
}
int last[40], last2[40];
LL query(int a, int b) {
memset(last, -1, sizeof(last));
memset(last2, -1, sizeof(last2));
int c = lca(a, b), f1 = top[a], f2 = top[b], A = a, B = b;
// puts("here");
while(f1 != top[c]) {
ql = pos[f1]; qr = pos[a];
for(int i = 0; i < k; i++) {
int tmp = querymn(i, 1, n, 1);
if(tmp <= n) last[i] = qos[tmp];
}
a = fa[f1]; f1 = top[a];
}
ql = pos[c]; qr = pos[a];
for(int i = 0; i < k; i++) {
int tmp = querymn(i, 1, n, 1);
if(tmp <= n) last[i] = qos[tmp];
}
while(f2 != top[c]) {
ql = pos[f2]; qr = pos[b];
for(int i = 0; i < k; i++) {
int tmp = querymx(i, 1, n, 1);
if(last2[i] < 0 && tmp >= 0) last2[i] = qos[tmp];
}
b = fa[f2]; f2 = top[b];
}
ql = pos[c]; qr = pos[b];
for(int i = 0; i < k; i++) {
int tmp = querymx(i, 1, n, 1);
if(last2[i] < 0 && tmp >= 0) last2[i] = qos[tmp];
}
// for(int i = 0; i < k; i++) printf("%d ", last[i]); putchar('
');
// for(int i = 0; i < k; i++) printf("%d ", last2[i]); putchar('
');
LL ret = 0;
// printf("lca: %d
", c);
for(int i = 0; i < k; i++) {
int dis;
if(last[i] < 0 && last2[i] < 0) dis = dep[A] + dep[B] - dep[c] - dep[c];
else {
if(last2[i] >= 0) dis = dep[B] - dep[last2[i]];
else dis = dep[last[i]] + dep[B] - dep[c] - dep[c];
}
// printf("%d ", dis);
ret |= ((((LL)dis & 1ll) ^ 1ll) << (LL)i);
}
// putchar('
');
return ret;
}
int main() {
n = read(); q = read(); k = read();
for(int i = 1; i <= n; i++) val[i] = read();
for(int i = 1; i < n; i++) {
int a = read(), b = read();
AddEdge(a, b);
}
build(1);
build(1, 1);
for(int i = 1; i <= n; i++) V[pos[i]] = val[i];
for(int i = 0; i < k; i++) build(i, 1, n, 1);
while(q--) {
char tp = Getchar();
while(!isalpha(tp)) tp = Getchar();
LL a = read(), b = read();
if(tp == 'Q') printf("%lld
", query(a, b));
if(tp == 'R') {
V[pos[a]] = b;
for(int i = 0; i < k; i++) update(i, 1, n, 1, pos[a]);
}
}
return 0;
}