Codeforces 877E - Danil and a Part-time Job 线段树+dfs序

给一个有根树,1e5个节点,每个节点有权值0/.1,
1e5操作:
1.将一个点的子树上所有点权值取反
2.查询一个点的子树的权值和
 
题解:
先深搜整颗树,用dfs序建立每个点对应的区间,
等于把树拍扁成一个数列,每次操作从就对点变成了对区间
然后就是裸线段树
注意拍扁后的节点标号和原来的树节点标号是不等价的,要映射一下
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=1e6+7;
int casn,n,m,k;
vector<int>g[maxn];
pii seg[maxn];
int vis[maxn];
int a[maxn];
int dfn;
void dfs(int now){
seg[now].fi=++dfn;
vis[dfn]=now;
for(auto i:g[now]) dfs(i);
seg[now].se=dfn;
}
class segtree{
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
public:
struct segnode {
int l,r;int sum,tag;
int mid(){return (r+l)>>1;}
int len(){return r-l+1;}
void update(){sum=len()-sum;tag^=1;}
};
vector<segnode> node;
int cnt;
segtree(int n) {node.resize(n<<2|3);maketree(1,n);}
void pushup(int now){nd.sum=ndl.sum+ndr.sum;}
void pushdown(int now){
if(nd.tag){
ndl.update();
ndr.update();
nd.tag=0;
}
}
void maketree(int s,int t,int now=1){
nd={s,t,0,0};
if(s==t){
nd.sum=a[vis[s]];
return ;
}
maketree(s,nd.mid(),now<<1);
maketree(nd.mid()+1,t,now<<1|1);
pushup(now);
}
void update(int s,int t,int now=1){
if(s>nd.r||t<nd.l) return ;
if(s<=nd.l&&t>=nd.r){nd.update();return ;}
pushdown(now);
update(s,t,now<<1); update(s,t,now<<1|1);
pushup(now);
}
int query(int s,int t,int now=1){
if(s>nd.r||t<nd.l) return 0;
if(s<=nd.l&&t>=nd.r) return nd.sum;
pushdown(now);
return query(s,t,now<<1)+query(s,t,now<<1|1);
}
};
int main() {
IO;
cin>>n;
rep(i,2,n){
int a;cin>>a;
g[a].push_back(i);
}
dfs(1);
rep(i,1,n) cin>>a[i];
segtree tree(n);
cin>>m;
string s;
int x;
while(m--){
cin>>s>>x;
if(s=="get")cout<<tree.query(seg[x].fi,seg[x].se)<<endl;
else tree.update(seg[x].fi,seg[x].se);
}
return 0;
}
上一篇:foreach使用


下一篇:OC中属性及方法