首页 > 其他分享 >CSP模拟3 <反思>

CSP模拟3 <反思>

时间：2023-07-23 19:44:46浏览次数：63  
标签：ch int tr id fx lca CSP 模拟

t3：不要随便用 map

t4: 代码转移要删全

首先考虑暴力，类似线段树，首先你要先dfs出每个节点子树的左右节点，然后修改查询时要考虑左儿子右边界是否大于查询左边界，右儿子左边界是否小于查询有边界，进行 \(dfs\) \(（46pts）\)

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2*1e5+5;
int tr[N*4][3];
struct asd{
	int l,r,data;
}tree[N*4];
int n,m;
void dfs(int x){
	if(x<=n){
		tree[x].l=tree[x].r=x;
		return;
	}
	dfs(tr[x][0]),dfs(tr[x][1]);
	if(tree[tr[x][0]].l>=tree[tr[x][1]].l){
		swap(tr[x][1],tr[x][0]);
	}
	tree[x].l=tree[tr[x][0]].l;
	tree[x].r=tree[tr[x][1]].r;
}
void change(int p,int l,int r,int d){
	if(tree[p].l>=l && tree[p].r<=r){
		tree[p].data+=(tree[p].r-tree[p].l+1)*d;
		return;
	}
	if(tree[tr[p][0]].r>=l) change(tr[p][0],l,r,d);
	if(tree[tr[p][1]].l<=r) change(tr[p][1],l,r,d);
}
int ask(int p,int l,int r){
	if(tree[p].l>=l && tree[p].r<=r){
		return tree[p].data;
	}
	int ans=0;
	if(tree[tr[p][0]].r>=l) ans+=ask(tr[p][0],l,r);
	if(tree[tr[p][1]].l<=r) ans+=ask(tr[p][1],l,r); 
	return ans;
}
bool flat[N*2];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		tr[n+i][0]=x,tr[n+i][1]=y;
		flat[x]=flat[y]=1;
	}
	int root;
	for(int i=1;i<=n*2-1;i++){
		if(flat[i]==0){
			root=i;
			break;
		}
	}
	dfs(root);
	for(int i=1;i<=m;i++){
		int op;
		scanf("%lld",&op);
		if(op==1){
			int l,r,d;
			scanf("%lld%lld%lld",&l,&r,&d);
			change(root,l,r,d);
		}
		else{
			int l,r;
			scanf("%lld%lld",&l,&r);
			printf("%lld\n",ask(root,l,r));
		}
	}
}
考虑正解：

定义 isa 表示 a 是否是它父亲的左儿子

定义 ffa 表示 a的真祖先中第一个和 a is 值不同的祖先的兄弟节点

连接 a,ffa ，显然仍能得到一颗以原来根为根的树（以后就说现树）。

如何建：

查询两个点 \(l,r\),求出它们 \(lca\) 以此为界限将其一分为二，先只考虑左边。
首先由左节点出发向右上走到头为 \(u\) ,则 \(u\) 为符合的节点
开个栈，每次先将当前点的左儿子与栈顶元素相连，然后将当前点左儿子压入栈，遍历当前点右子树，再将左儿子弹出栈，再遍历左子树，如此得到。可以在 \(dfs\) 时直接开一个变量表示栈顶，省掉栈。

点击查看代码 
void Do(int th,int x){
	if(!ch[th][0]) return;
	add(x,ch[th][0]);
	Do(ch[th][1],ch[th][0]);
	Do(ch[th][0],x);
}

void Do1(int th,int x){
	if(!ch[th][0]) return;
	add(x,ch[th][1]);
	Do1(ch[th][0],ch[th][1]);
	Do1(ch[th][1],x);
}

	Do(root,root);
	Do1(root,root);

先对于节点 \(l\) ，我们找到 \(l\) 在原树上一直向右上跳的最远位置（设其为 \(u\)）

那么从 \(u\) 开始在现树上往上跳，发现一定能跳到 \(lca\) 的右儿子,但是右儿子又不会和左边的操作相关,所以跳的时候判停。
考虑三种情况：
1：\(l\) 和 \(r\) 的 \(u\) 深度均比 \(lca\) 小， 则此时需操作的就是 \(lca\) 这个点
2：\(l\) 的 \(u\) 深度比 \(lca\) 小，则左侧操作的应该为 \(lca\) 的左儿子节点。
3：\(r\) 的 \(u\) 深度比 \(lca\) 小，方法与 2 相同。

因此可以用树剖+线段树维护。

线段树维护节点状态之和，可以打延迟标记。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4*1e5+5;
int n,m,root;
int ch[N*2][3];
struct asd{
	int l,r,data;
}t[N*2];
struct qwe{
	int l,r,data,num,lazy;
}tr[1600010];
int ll[N*2],rr[N*2];
int head[N*2],ver[N*2],nex[N*2],tot=0;
int fa[N*2],size[N*2],son[N*2],top[N*2],d[N*2];
int _fa[N*2],_size[N*2],_son[N*2],_top[N*2],_d[N*2],_id[N*2],_rk[N*2],cnt=0;

void add(int x,int y){
	ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}

void dfs(int x){
	if(x<=n){
		t[x].l=t[x].r=x;
		return;
	}
	dfs(ch[x][0]);
	dfs(ch[x][1]);
	if(t[ch[x][0]].l>=t[ch[x][1]].l){
		swap(ch[x][1],ch[x][0]);
	}
	t[x].l=t[ch[x][0]].l;
	t[x].r=t[ch[x][1]].r;
}

void dfs1(int x){
	if(x<=n) return;
	rr[ch[x][0]]=rr[x],ll[ch[x][0]]=ch[x][0];
	dfs1(ch[x][0]);
	ll[ch[x][1]]=ll[x],rr[ch[x][1]]=ch[x][1];
	dfs1(ch[x][1]);
}

void dfs_y1(int x,int f){
	if(!x) return; 
	d[x]=d[f]+1;
	fa[x]=f;
	size[x]=1;
	dfs_y1(ch[x][0],x); size[x]+=size[ch[x][0]];
	dfs_y1(ch[x][1],x); size[x]+=size[ch[x][1]];
	if(size[ch[x][0]]<size[ch[x][1]]) son[x]=ch[x][1];
	else son[x]=ch[x][0];
}

void dfs_y2(int x,int tp){
	if(!x) return;
	top[x]=tp;
	if(son[x]) dfs_y2(son[x],tp);
	if(ch[x][0]!=son[x]) dfs_y2(ch[x][0],ch[x][0]);
	else dfs_y2(ch[x][1],ch[x][1]);
}

int ask_lca(int x,int y){//原树lca 
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(d[fx]>d[fy]) x=fa[fx],fx=top[x];
		else y=fa[fy],fy=top[y];
	}
	if(d[x]<d[y]) return x;
	else return y;
}

void dfs_x1(int x,int f){
	_d[x]=_d[_fa[x]]+1;
	_size[x]=1;
	for(int i=head[x];i;i=nex[i]){
		int y=ver[i];
		_fa[y]=x; 
		dfs_x1(y,x);
		_size[x]+=_size[y];
		if(_size[_son[x]]<_size[y]){
			_son[x]=y;
		}
	}
}

void dfs_x2(int x,int tp){
	_id[x]=++cnt;
	_rk[cnt]=x;
	_top[x]=tp;
	if(_son[x]) dfs_x2(_son[x],tp);
	for(int i=head[x];i;i=nex[i]){
		int y=ver[i];
		if(y==_fa[x]) continue;
		if(y!=_son[x]){
			dfs_x2(y,y);
		}
	}
}

void Do(int th,int x){
	if(!ch[th][0]) return;
	add(x,ch[th][0]);
	Do(ch[th][1],ch[th][0]);
	Do(ch[th][0],x);
}

void Do1(int th,int x){
	if(!ch[th][0]) return;
	add(x,ch[th][1]);
	Do1(ch[th][0],ch[th][1]);
	Do1(ch[th][1],x);
}

void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		int id=_rk[l];
		tr[p].num=(t[id].r-t[id].l+1);
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tr[p].num=tr[p*2].num+tr[p*2+1].num;
}

void pushdown(int p){
	if(tr[p].lazy){
		tr[p*2].data+=tr[p*2].num*tr[p].lazy;
		tr[p*2].lazy+=tr[p].lazy;
		tr[p*2+1].data+=tr[p*2+1].num*tr[p].lazy;
		tr[p*2+1].lazy+=tr[p].lazy;
		tr[p].lazy=0;
	}
}

void change(int p,int l,int r,int w){
	if(tr[p].l>=l && tr[p].r<=r){
		tr[p].data+=tr[p].num*w;
		tr[p].lazy+=w;
		return;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)/2;
	if(l<=mid) change(p*2,l,r,w);
	if(r>mid) change(p*2+1,l,r,w);
	tr[p].data=tr[p*2].data+tr[p*2+1].data;
	return;
}

int ask(int p,int l,int r){
	if(tr[p].l>=l && tr[p].r<=r){
		return tr[p].data;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)/2;
	int ans=0;
	if(l<=mid) ans+=ask(p*2,l,r);
	if(r>mid) ans+=ask(p*2+1,l,r);
	return ans;
}

void chan(int l,int r,int w){
	int lca=ask_lca(l,r),ans=0;
	l=rr[l],r=ll[r];
	if(d[l]<=d[lca] && d[r]<=d[lca]){
		change(1,_id[lca],_id[lca],w);
		return;
	}	
	
	if(d[l]<=d[lca]){
		l=ch[lca][0];
		change(1,_id[l],_id[l],w);
	}
	else{
		int fx=_top[l];
		while(_d[fx]>_d[ch[lca][1]]){
			change(1,_id[fx],_id[l],w);
			l=_fa[fx],fx=_top[l];
		}
		change(1,_id[ch[lca][1]]+1,_id[l],w);
	}
	if(d[r]<=d[lca]){
		r=ch[lca][1];
		change(1,_id[r],_id[r],w);
	}
	else{
		int fx=_top[r];
		while(_d[fx]>_d[ch[lca][0]]){
		     change(1,_id[fx],_id[r],w);
		     r=_fa[fx],fx=_top[r];
		}
		change(1,_id[ch[lca][0]]+1,_id[r],w);
	}
}

int askk(int l,int r){
	int lca=ask_lca(l,r),ans=0;
	l=rr[l],r=ll[r];
	if(d[l]<=d[lca] && d[r]<=d[lca]){
		ans+=ask(1,_id[lca],_id[lca]);
		return ans;
	}	
	
	if(d[l]<=d[lca]){
		l=ch[lca][0];
		ans+=ask(1,_id[l],_id[l]);
	}
	else{
		int fx=_top[l];
		while(_d[fx]>_d[ch[lca][1]]){
			ans+=ask(1,_id[fx],_id[l]);
			l=_fa[fx],fx=_top[l];
		}
		ans+=ask(1,_id[ch[lca][1]]+1,_id[l]);
	}
	if(d[r]<=d[lca]){
		r=ch[lca][1];
		ans+=ask(1,_id[r],_id[r]);
	}
	else{
		int fx=_top[r];
		while(_d[fx]>_d[ch[lca][0]]){
		     ans+=ask(1,_id[fx],_id[r]);
		     r=_fa[fx],fx=_top[r];
		}
		ans+=ask(1,_id[ch[lca][0]]+1,_id[r]);
	}
	return ans;
}

bool flat[N*2];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		ch[n+i][0]=x,ch[n+i][1]=y;
		flat[x]=flat[y]=1;
	}
	for(int i=1;i<=n*2-1;i++){
		if(flat[i]==0){
			root=i;
			break;
		}
	}
	dfs(root);
	ll[root]=root,rr[root]=root;
	dfs1(root);
	Do(root,root);
	Do1(root,root);
	dfs_y1(root,0);
	dfs_y2(root,root);
	dfs_x1(root,0);
	dfs_x2(root,root);
	build(1,1,cnt);
	for(int i=1;i<=m;i++){
		int op;
		scanf("%lld",&op);
		if(op==1){
			int l,r,d;
			scanf("%lld%lld%lld",&l,&r,&d);
			chan(l,r,d);
		}
		else{
			int l,r;
			scanf("%lld%lld",&l,&r);
			printf("%lld\n",askk(l,r));
		}
	}
}

标签：ch,int,tr,id,fx,lca,CSP,模拟
From： https://www.cnblogs.com/jinjiaqioi/p/17575758.html

相关文章

  • CSP 模拟 3
    今天感觉很热，但是天气转凉的时候我也该退役了吧。今日推歌：透明哀歌-n-buna/Gumiecho-Crusher-P/GumiEnglish歌词Theclockstoppedticking,时钟停止发出嘀嗒声Foreverago.在很久以前HowlonghaveIbeenup?我究竟醒来了多久?Idon'tknow.我不知道Ican't......
  • CSP 模拟 2
    感觉像是noi模拟赛多了个pT1F咋做都行，但是考场上的正确做法被后来优化RE了，痛失60pts其中一种做法是考虑只有\(a_1\oplusb_i\)有可能成为答案，然后验证即可T2S定义dp状态\(f_{i,j,k,0/1/2}\)为用了\(i\)个红球，\(j\)个绿球，\(k\)个红球，并且最后一位是什么球......
  • java 爬虫模拟登陆 拿到cookies
    实现Java爬虫模拟登录获取Cookies概述在这篇文章中，我将教你如何使用Java编程语言实现爬虫模拟登录并获取Cookies。爬虫模拟登录是一种常见的网络爬虫技术，它可以模拟用户登录网站，获取登录后才能访问的资源。流程概览下面是整个模拟登录获取Cookies的流程概览：步骤描述......
  • 模拟飞行开发任务进度
    第一周（截止2023.7.23上午）任务主要进度：跟着做的案例为Stack-O-Bot，有官方的文档以及游戏教学过程，比较适合新手进行学习，根据官方给的教学，大体上复现了他的效果。正在学习蓝图类模型，类似于图形化的编程界面？编程的重点是逻辑的设计，需要考虑好每一个过程的关系以及物理过程(这个在......
  • P7074 [CSP-J2020] 方格取数 题解
    题目：题目描述设有n*m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。输入格式第一行有两个整......
  • Qt(5.8.0)-Cmd模拟(纯手写)
    以下是对上述Qt程序的详细博客，使用Markdown的代码块方式呈现：Qt编程：实现一个简单的命令行窗口Qt是一种跨平台的C++应用程序开发框架，可以用于开发各种类型的应用程序，包括图形界面(GUI)应用程序。本文将介绍如何使用Qt框架实现一个简单的命令行窗口，类似于Windows的运行框，用户可以在......
  • 「赛后总结」20230722 CSP 模拟赛
    「赛后总结」20230722CSP模拟赛点击查看目录目录「赛后总结」20230722CSP模拟赛反思题解T1回文思路代码T2快速排序思路代码T3混乱邪恶思路代码T4校门外歪脖树上的鸽子思路吓死我了我还以为K8He不更博了。为啥前天模拟赛不写啊？打过，没参加。为啥昨天模拟赛不......
  • strlen/strcpy/strcat的模拟实现
    char*my_strcat(char*dest,constchar*src){ assert(dest!=NULL);//字符串要以‘\0’结束，目标空间要足够大，且可修改 assert(src!=NULL); char*ret=dest; //1，找到目的字符串的\0; while(*dest!='\0') { dest++; } //2，追加 while(*dest++=*src++) { ; } returnr......
  • CSP模拟3
    A.回文\(20\)多分的纯暴力搜索，\(A_{i,j}=A_{i-1,j+1}\)可以判完回文直接递推出路径数，共\(42\text{pts}\)。正解\(DP\)。回文可以转化一下思路，两个人分别从\((1,1),(n,m)\)出发，走的路径相同的方案数。设计\(dp[i][j][s][t]\)为第一个人在\((i,j)\)位置，第二个人在......
  • [爬虫]2.2.1 使用Selenium库模拟浏览器操作
    Selenium是一个非常强大的工具，用于自动化Web浏览器的操作。它可以模拟真实用户的行为，如点击按钮，填写表单，滚动页面等。由于Selenium可以直接与浏览器交互，所以它可以处理那些需要JavaScript运行的动态网页。安装Selenium首先，我们需要安装Selenium库。你可以使用pip命令来安装：pip......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99