淄博网站建设公司有几家,网站做视频在线观看网址,北京做网站优化多少钱,做茶网站【BZOJ2908】又是nand escription 首先知道A nand Bnot(A and B) #xff08;运算操作限制了数位位数为K#xff09;比如2 nand 3#xff0c;K3#xff0c;则2 nand 3not (2 and 3)not 25。给出一棵树#xff0c;树上每个点都有点权#xff0c;定义树上从a到b的费用为0与…【BZOJ2908】又是nand escription 首先知道A nand Bnot(A and B) 运算操作限制了数位位数为K比如2 nand 3K3则2 nand 3not (2 and 3)not 25。 给出一棵树树上每个点都有点权定义树上从a到b的费用为0与路径上的点的权值顺次nand的结果例如从2号点到5号点顺次经过2-3-5权值分别为5、7、2K3那么最终结果为0 nand 5 nand 7 nand 27 nand 7 nand 20 nand 27现在这棵树需要支持以下操作。 ① Replace a b:将点a1≤a≤N的权值改为b。 ② Query a b:输出点a到点b的费用。 请众神给出一个程序支持这些操作。 Input 第一行NMK树的节点数量、总操作个数和运算位数。 接下来一行N个数字依次表示节点i的权值。 接下来N-1行每行两个数字a,b1≤a,b≤N表示a,b间有一条树边。 接下来M行每行一个操作为以上2类操作之一。 N、M≤100000K≤32 Output 对于操作②每个输出一行如题目所述。 Sample Input 3 3 3 2 7 3 1 2 2 3 Query 2 3 Replace 1 3 Query 1 1 Sample Output 4 7 题解网上都说要拆位那么我也拆位吧~不拆位好像也能做 首先nand满足交换律但不满足结合律。 我们先树剖然后对于每一位都用线段树维护tl[d][x]代表如果该位是d从左边来经过这个区间后会变成的数tr[d][x]代表如果该位是d从右往左经过这个区间后会变成的数。然后就是区间合并的事了~ 对于询问a,b我们先求出从a向上走到lca的变化再求出从lca向下走到b的变化即可。 #include cstdio
#include cstring
#include iostream
#define lson x1
#define rson x1|1
using namespace std;
int n,m,k,cnt;
char str[10];
const int maxn100010;
int to[maxn1],next[maxn1],head[maxn],fa[maxn],dep[maxn],siz[maxn],top[maxn],son[maxn],p[maxn],q[maxn],st[maxn];
unsigned v[maxn];
struct seg
{bool tl[2][maxn2],tr[2][maxn2];void pushup(int x){tl[0][x]tl[tl[0][lson]][rson],tl[1][x]tl[tl[1][lson]][rson];tr[0][x]tr[tr[0][rson]][lson],tr[1][x]tr[tr[1][rson]][lson];}void build(int l,int r,int x,int a){if(lr){tl[0][x]tr[0][x]1,tl[1][x]tr[1][x]!((v[q[l]]a)1);return ;}int midlr1;build(l,mid,lson,a),build(mid1,r,rson,a);pushup(x);}void updata(int l,int r,int x,int a,bool b){if(lr){tl[0][x]tr[0][x]1,tl[1][x]tr[1][x]!b;return ;}int midlr1;if(amid) updata(l,mid,lson,a,b);else updata(mid1,r,rson,a,b);pushup(x);}bool ql(int l,int r,int x,int a,int b,bool c){if(alrb) return tl[c][x];int midlr1;if(bmid) return ql(l,mid,lson,a,b,c);if(amid) return ql(mid1,r,rson,a,b,c);return ql(mid1,r,rson,a,b,ql(l,mid,lson,a,b,c));}bool qr(int l,int r,int x,int a,int b,bool c){if(alrb) return tr[c][x];int midlr1;if(bmid) return qr(l,mid,lson,a,b,c);if(amid) return qr(mid1,r,rson,a,b,c);return qr(l,mid,lson,a,b,qr(mid1,r,rson,a,b,c));}
}s[33];
inline int rd()
{int ret0; char gcgetchar();while(gc0||gc9) gcgetchar();while(gc0gc9) retret*10gc-0,gcgetchar();return ret;
}
void dfs1(int x)
{siz[x]1;for(int ihead[x];i!-1;inext[i]){if(to[i]!fa[x]){fa[to[i]]x,dep[to[i]]dep[x]1,dfs1(to[i]),siz[x]siz[to[i]];if(siz[to[i]]siz[son[x]]) son[x]to[i];}}
}
void dfs2(int x,int tp)
{top[x]tp,p[x]p[0],q[p[0]]x;if(son[x]) dfs2(son[x],tp);for(int ihead[x];i!-1;inext[i]) if(to[i]!fa[x]to[i]!son[x]) dfs2(to[i],to[i]);
}
void add(int a,int b)
{to[cnt]b,next[cnt]head[a],head[a]cnt;
}
void ask(int x,int y)
{unsigned int ret0;int i;st[0]0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]){for(i0;ik;i) retret-(ret(1i))(s[i].qr(1,n,1,p[top[x]],p[x],(reti)1)i);xfa[top[x]];}else st[st[0]]y,yfa[top[y]];}if(dep[x]dep[y]) for(i0;ik;i) retret-(ret(1i))(s[i].ql(1,n,1,p[x],p[y],(reti)1)i);else for(i0;ik;i) retret-(ret(1i))(s[i].qr(1,n,1,p[y],p[x],(reti)1)i);for(yst[0];y;y--) for(i0;ik;i) retret-(ret(1i))(s[i].ql(1,n,1,p[top[st[y]]],p[st[y]],(reti)1)i);printf(%u\n,ret);
}
int main()
{nrd(),mrd(),krd();int i,j,a,b;for(i1;in;i) scanf(%u,v[i]);memset(head,-1,sizeof(head));for(i1;in;i) ard(),brd(),add(a,b),add(b,a);dep[1]1,dfs1(1),dfs2(1,1);for(i0;ik;i) s[i].build(1,n,1,i);for(i1;im;i){scanf(%s,str);if(str[0]Q) ard(),brd(),ask(a,b);else{ard(),scanf(%u,v[a]);for(j0;jk;j) s[j].updata(1,n,1,p[a],(v[a]j)1);}}return 0;
}//3 3 3 2 7 3 1 2 2 3 Query 2 3 Replace 1 3 Query 1 1 转载于:https://www.cnblogs.com/CQzhangyu/p/7327672.html
