首页 > 其他分享 >CF-877-E-dfs序+线段树

CF-877-E-dfs序+线段树

时间:2024-05-05 11:22:05浏览次数:27  
标签:int 877 CF dfs -- dfn op

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

相关文章

  • CF-600-E-启发式合并
    600-E题目大意给定一颗\(n\)个节点的树,根为\(1\)。树上的每个节点\(i\)都有一个颜色\(c_i\)。如果一个颜色在以\(x\)为根的子树中出现次数最多,那么称该颜色为主要颜色,显然,一颗树中可以有多个主要颜色。求出对于每个节点为根时,其子树中所有主要颜色的编号和。Solution启发式......
  • CF-797-E-根号分治
    797-E题目大意给定一个长为\(n\)序列\(a\),有\(q\)次询问:给定\(p,k\),你需要反复执行操作\(p=p+a_p+k\),直到\(p>n\)为止,问你要执行多少次操作。Solution考虑两种思路:1、暴力回答询问,每次反复模拟操作,直到\(p>n\)为止,时间复杂度\(O(q·\frac{n}{k})\)。2、预处理出......
  • CF1968E.Cells Arrangement-构造(给个和题解不同的做法)
    link:https://codeforces.com/problemset/problem/1968/E题意:需要构造一个\(n\timesn\)的棋盘,在上面放\(n\)枚棋子,设集合\(\mathcal{H}\)表示两两之间曼哈顿距离构成的集合,要让\(|\mathcal{H}|\)最大。给出放棋子的方案。首先说说题解的做法…考虑把距离为奇数和偶数的......
  • CF940F.Machine Learning-带修莫队、Mex
    给一个序列\(a\),两个操作:1、给\(l,r\),设\(a_l,\dots,a_r\)这些数集中每个数\(v\)的出现次数是\(c_v\),要求\(\mathrm{mex}(c_i)\).2、单点修改\(1\leqn,q\leq10^5\),时限4s这种一眼看过去很难维护的信息,一般就先找找性质。首先注意到关键性质:要求的是出现次数......
  • 题解:CF1926G
    题目传送门思路发现权值为C的点可以选择看做是权值为S或为P的点,所以问题转换为怎么给C点赋值可以使答案最小,考虑树形dp。\(f_{i,0/i,1}\)表示\(i\)点赋值为S或P时最少要删除几条边。但如果当前点权值不为C的话,那显然他的父亲节点应该选择和他权值相同的点才......
  • CF941
    Alink其实,只要有第一次,那么下次随意找一个队列里有的数加\(k-1\)个进去,加上队列里那一个删掉\(k\)个,到最后一次肯定是剩\(k-1\)个。没有第一次,就是\(n\)。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intt;intn,k;inta[105];intmp[105];voidqwq......
  • CF-943(已更B-E)
    CF-943(已更B-E)D赛时没调出来(╬▔皿▔)╯,还有几分钟的时候反而把E过了,本来应该是上大分一场(⊙﹏⊙),等会会补G1这假期要刷题,还要补文化课……后面有空的话更一下之前打的线下赛的题解B双指针……voidsolve(){ intn,m;cin>>n>>m; stringa,b;cin>>a>>b; intnow=0......
  • CF1950 A~G
    前言报了名没打的一场Div.4,我是怎么想到回去做的呢?上课的时候无聊于是随机了一道1700的题,找到了本场比赛的F题,我那时还没发现。过了差不多\(2\sim3\)天去随机了一道1900,又找到了G题,一看G题竟然只有1900,意识到这是Div.4,就想着AK一场Div.4,结果发现F做过了,这......
  • 题解:CF607E Cross Sum
    Problem给定\(N\)条不平行的直线\(y=\frac{k_i}{1000}x+\frac{b_i}{1000}\),\(N\)条直线总共会有\(\frac{N(N-1)}{2}\)个交点(包含在同一个位置的点,即相同位置算不同的点),找出距离原点前\(K\)近的交点的距离和。$2\leN\le5\times10^4$,\(1\leK\le\frac{N(N-1)}{2}\)......
  • Codeforces 1044F DFS
    考虑到存在方案使得以\(u\)为起点还能走出原树的条件。能发现是以\(u\)为根,在原树上新添加的边只会是返祖边而不会有横叉边。这是因为如果有横叉边就肯定会在遍历到一边的点后先通过这条边走到另一边的点,就算上了这条边就不是原树了。那么考虑\((x,y)\),合法的\(u\)需要......