欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

Codeforces Round #225 (Div. 1) C 树状数组 || 线段树_html/css_WEB-ITnose

程序员文章站 2023-12-31 10:49:04
...
看到这题很开心啊,有印象跟以前做过的很像,貌似最近就做过一个,以时间戳为区间来建立树状数组,然后一开始我以为题意是,给x点加val,它以下的所有节点都加-val;所以一开始就以 加 和 减 建立了两个树状数组,最后 减去就是答案,写完发现跟案例对不上啊,读了题目也没发现读错了,对于那句话 我理解错了,后来看了 这个:
http://blog.csdn.net/keshuai19940722/article/details/18967661
仔细看看处理部分,我还以为分奇偶性有规律呢,后来才发现读错题目了,原来是x点加val,与它直接相连的子节点加上-val,它的子节点的子节点又加上val,以此类推。。。哈哈。。哭

跟以前那类题目做法相同,对于这棵树,进行dfs,同时记录当前层数距离跟的关系,用奇偶数来表示,然后再以各个节点被dfs的时间戳 来建立区间 让树状数组映射上去,最后奇偶分开,加的在一个树状数组里,减去的在另一个里面,然后 最后求单点值的时候 就是自己这个点 所属的 距离根节点的关系,也就是自己应该加上的值,再减去对应的另一个树状数组里的应该减去的值,然后 一开始 各个节点本身具有的值 并没有加进树状数组里,还得加上原本具有的值,这样就是答案了

然后又用线段树做了一下,也是以时间戳来搞,同时记录这个节点距离根的奇偶性,然后也是建立两颗线段树,一个记录奇数处理,一个记录偶数处理,结果不知哪里写错了,又改了很久,不行又重新写了一下,真是学啥忘啥。。。

树状数组的:

int n;int m;int c[2][200000 * 2 + 55];typedef struct Node {	int l,r,val;	int now;};Node node[200000 + 55];vector G[200000 + 55];int cnt;void init() {	memset(c,0,sizeof(c));	for(int i=0;i>n>>m) {		for(int i=1;i>node[i].val;		int tmp = n - 1;		while(tmp--) {			int u,v;			scanf("%d %d",&u,&v);			G[u].push_back(v);			G[v].push_back(u);		}		return false;	}	return true;}int lowbit(int x) {	return x&(-x);}void add(int i,int val,int *aa) {	while(i  0) {		sum += aa[i];		i -= lowbit(i);	}	return sum;}void dfs(int u,int pre,int tot) {	node[u].l = cnt++;	node[u].now = tot;	for(int i=0;i>type;		if(type == 1) {			int x,y;			cin>>x>>y;			//int tmp = node[x].now;			//int aa = node[x].l;			//int bb = node[x].r;			add(node[x].l,y,c[node[x].now]);			add(node[x].r + 1,-y,c[node[x].now]);		}		else {			int x;			cin>>x;			//int aa = (get_sum(node[x].l,c[node[x].d]) /*- get_sum(node[x].l - 1,c[node[x].d])*/);			//int bb = (get_sum(node[x].l,c[node[x].d^1])/* - get_sum(node[x].l - 1,c[node[x].d^1])*/);			//int cc = 0;			int ans = get_sum(node[x].l,c[node[x].now]) - get_sum(node[x].l,c[node[x].now^1]);			ans += node[x].val;			cout  

线段树的:

const int N = 200000 + 55;int n;int m;int nnum[N + 55];int le[N + 55],ri[N + 55],belong[N + 55];int head[N + 55];typedef struct Node {	int l,r;	ll sum;	int lazy;};Node tree_even[N * 4 + 55],tree_odd[N * 4 + 55];typedef struct NODE {	int fro,to;	int nex;};NODE edge[2 * N + 55];int tot;int cnt;void add(int u,int v) {	edge[tot].fro = u;	edge[tot].to = v;	edge[tot].nex = head[u];	head[u] = tot++;}void dfs(int u,int pre,int d) {	le[u] = ++cnt;	for(int i=head[u];i!=-1;i=edge[i].nex) {		int v = edge[i].to;		if(v == pre)continue;		dfs(v,u,d^1);	}	belong[le[u]] = d;	ri[le[u]] = cnt;}void push_up(int id,Node *tree) {	tree[id].sum = tree[id>1;	build(l,mid,id>1;	if(r  mid)update(l,r,id>1;	ll ret = 0ll;	if(r  mid)ret += query(l,r,id>n>>m) {		for(int i=1;i>nnum[i];		for(int i=1;i>u>>v;			add(u,v);			add(v,u);		}		return false;	}	return true;}void cal() {	dfs(1,-1,1);	build(1,n,1,tree_even);	build(1,n,1,tree_odd);	while(m--) {		int type;		cin>>type;		if(type == 1) {			int x,y;			cin>>x>>y;			int left = le[x];			int right = ri[left];			if(belong[left]&1) update(left,right,1,y,tree_odd);			else update(left,right,1,y,tree_even);		}		else {			int x;			cin>>x;			int left = le[x];			ll ans;			if(belong[left]&1)				ans = query(left,left,1,tree_odd) - query(left,left,1,tree_even);			else				ans = query(left,left,1,tree_even) - query(left,left,1,tree_odd);			ans += nnum[x];			cout

上一篇:

下一篇: