877-E 题目大意
给定一颗\(n\)个节点的树,根为\(1\),点带权,权值要么为0,要么为1。
\(q\)次询问,两种类型:
- \(get \space x\):询问\(x\)的子树中有多少个\(1\)。
- \(pow \space x\):将\(x\)子树中所有的值取反。
Solution
dfs序+线段树模板题,把子树上的操作转化为区间上的操作。
时间复杂度:\(O(nlogn)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct node{
int l,r;
int sum,tag;
}tr[N<<2];
void pushup(int u){
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
if(tr[u].tag){
tr[u<<1].tag^=1;
tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
tr[u<<1|1].tag^=1;
tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
tr[u].tag=0;
}
}
void build(int u,int l,int r){
tr[u]={l,r,0,0};
if(l==r) return;
int m=(l+r)>>1;
build(u<<1,l,m);
build(u<<1|1,m+1,r);
}
void modify(int u,int l,int r){
if(l<=tr[u].l&&tr[u].r<=r){
tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum;
tr[u].tag^=1;
return;
}
pushdown(u);
int m=(tr[u].l+tr[u].r)>>1;
if(l<=m) modify(u<<1,l,r);
if(r>m) modify(u<<1|1,l,r);
pushup(u);
}
int query(int u,int l,int r){
if(l<=tr[u].l&&tr[u].r<=r){
return tr[u].sum;
}
pushdown(u);
int m=(tr[u].l+tr[u].r)>>1;
int res=0;
if(l<=m) res+=query(u<<1,l,r);
if(r>m) res+=query(u<<1|1,l,r);
return res;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector<vector<int>> e(n);
vector<int> L(n),R(n);
int dfn=0;
for(int i=1;i<n;i++){
int p;
cin>>p;
p--;
e[p].push_back(i);
}
function<void(int)> dfs=[&](int x){
L[x]=++dfn;
for(auto y:e[x]){
dfs(y);
}
R[x]=dfn;
};
dfs(0);
build(1,1,n);
for(int i=0;i<n;i++){
int w;
cin>>w;
if(w) modify(1,L[i],L[i]);
}
int q;
cin>>q;
while(q--){
string op;
int x;
cin>>op>>x;
x--;
if(op=="get"){
cout<<query(1,L[x],R[x])<<'\n';
}else{
modify(1,L[x],R[x]);
}
}
return 0;
}
标签:int,877,CF,dfs,--,dfn,op
From: https://www.cnblogs.com/fengxue-K/p/18173312