首先考慮問題的簡化版
存在下面兩個操作

• 詢問$[l,r]$區間與非的值即$a_l\text{NAND}{a}_{l+1}\text{NAND}\dots \text{NAND}{a}_r$
• 單線修改$p,x$即$a_p=x$

這是一道去年校賽題最近才發現區間與非的板子題

首先直覺告訴我們要用線段樹維護此操作，但是區間與非沒有結合律，這樣的信息線段樹不能直接維護，不過位運算具有獨立性，我們可以一位一位去考慮。

考慮用線段樹每個節點維護$\text{L}[0/1],\text{R}[0/1]$

$\text{L}[0]$表示剛開是$0$，然后從左向右經過此區間是最終的數（此節點維護的區間）
$\text{L}[1]$表示剛開是$1$，然后從左向右經過此區間是最終的數
$\text{R}[0]$表示剛開是$0$，然后從右向左經過此區間是最終的數
$\text{R}[1]$表示剛開是$1$，然后從右向左經過此區間是最終的數

然后只需要維護32棵線段樹（按位），就可以區間詢問了。

2908. 又是nand

而此題就是套了個樹鏈剖分，并且注意詢問的時候有的區間是從左向右，有的區間是從右向左（yy一下樹剖的樣子即可）

#include<bits/stdc++.h> using namespace std; using u32=unsigned int; using pii=pair<int,int>; constexpr int N=100010; int n,m,bit; u32 a[N]; int h[N],e[2*N],ne[2*N],idx; int sz[N],son[N],fa[N],dep[N]; int dfn[N],top[N],id[N],timestamp; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;} struct Segment {struct node{int l,r;bool L[2],R[2];}tree[N<<2];void pushup(int u){tree[u].L[0]=tree[u<<1|1].L[tree[u<<1].L[0]];tree[u].L[1]=tree[u<<1|1].L[tree[u<<1].L[1]];tree[u].R[0]=tree[u<<1].R[tree[u<<1|1].R[0]];tree[u].R[1]=tree[u<<1].R[tree[u<<1|1].R[1]];}void build(int u,int l,int r,int k){tree[u].l=l,tree[u].r=r;if(l==r) {tree[u].L[0]=tree[u].R[0]=1;tree[u].L[1]=tree[u].R[1]=!(a[id[l]]>>k&1);return;}int mid=l+r>>1;build(u<<1,l,mid,k);build(u<<1|1,mid+1,r,k);pushup(u);}void modify(int u,int pos,bool x){if(tree[u].l==tree[u].r){tree[u].L[0]=tree[u].R[0]=1;tree[u].L[1]=tree[u].R[1]=(!x);return;}int mid=tree[u].l+tree[u].r>>1;if(pos<=mid) modify(u<<1,pos,x);elsemodify(u<<1|1,pos,x);pushup(u);}bool queryL(int u,int l,int r,bool c){if(l<=tree[u].l&&tree[u].r<=r) return tree[u].L[c];int mid=tree[u].l+tree[u].r>>1;if(r<=mid)return queryL(u<<1,l,r,c);else if(l>mid) return queryL(u<<1|1,l,r,c);else return queryL(u<<1|1,l,r,queryL(u<<1,l,r,c));}bool queryR(int u,int l,int r,bool c){if(l<=tree[u].l&&tree[u].r<=r) return tree[u].R[c];int mid=tree[u].l+tree[u].r>>1;if(r<=mid)return queryR(u<<1,l,r,c);else if(l>mid) return queryR(u<<1|1,l,r,c);else return queryR(u<<1,l,r,queryR(u<<1|1,l,r,c));} }T[33]; //============================================================== void dfs1(int u) {dep[u]=dep[fa[u]]+1;sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa[u]) continue;fa[v]=u;dfs1(v);sz[u]+=sz[v];if(sz[son[u]]<sz[v]) son[u]=v;} }void dfs2(int u,int t) {dfn[u]=++timestamp;id[timestamp]=u;top[u]=t;if(son[u]) dfs2(son[u],t);for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa[u]||v==son[u]) continue;dfs2(v,v);} } //============================================================== void update(int u,u32 x) {for(int k=0;k<bit;k++)T[k].modify(1,dfn[u],x>>k&1); } u32 ask(int u,int v) {u32 ans=0;vector<pii> ql,qr;while(top[u]!=top[v]){if(dep[top[u]]>=dep[top[v]])// debug 1h{qr.push_back({dfn[top[u]],dfn[u]});u=fa[top[u]];}else{ql.push_back({dfn[top[v]],dfn[v]});v=fa[top[v]];}}if(dep[u]>=dep[v]) qr.push_back({dfn[v],dfn[u]});elseql.push_back({dfn[u],dfn[v]});reverse(ql.begin(),ql.end()); for(pii t:qr){int l=t.first,r=t.second;for(int k=0;k<bit;k++)ans=ans-(ans&(1<<k))+(T[k].queryR(1,l,r,ans>>k&1)<<k);}for(pii t:ql){int l=t.first,r=t.second;for(int k=0;k<bit;k++)ans=ans-(ans&(1<<k))+(T[k].queryL(1,l,r,ans>>k&1)<<k);}return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);memset(h,-1,sizeof h);cin>>n>>m>>bit;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<n;i++){int u,v;cin>>u>>v;add(u,v),add(v,u);}dfs1(1);dfs2(1,1);for(int k=0;k<bit;k++)T[k].build(1,1,n,k);while(m--){char op[10];u32 a,b;cin>>op>>a>>b;if(*op=='R')update(a,b);elsecout<<ask(a,b)<<'\n';}return 0; }

終于補完了區間NAND的板子

要加油哦~

總結

以上是生活随笔為你收集整理的bzoj 2908. 又是nand（树链剖分+区间NAND+单点修改）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。