首页 > 其他分享 >刷题记录_2024寒假2/17

刷题记录_2024寒假2/17

时间:2024-02-17 11:23:10浏览次数:29  
标签:17 int top 2024 dep ans now id 刷题

我都AFO了为什么还要我写题目

P多少多少默认洛谷

P3313 旅行

题意略,自己不会看吗

考虑对每个信仰开一个线段树,下标为dfs序,然后就是树剖板子

对于这种开一堆动态开点线段树的题目可以存每个线段树的根节点然后就只需要开一个结构体了

code:

#include<bits/stdc++.h>
#define lc t[now].ls
#define rc t[now].rs
using namespace std;
const int N=1e5+5;
int rt[N];

struct node{
	int ls,rs;
	int mx,sum;
}t[2000005];
int tot=100000;
int n,q,F[N],siz[N];
int son[N];
int W[N],C[N];
int id[N],top[N],dep[N];
vector<int> eg[N];

void dfs1(int now,int fa){
	dep[now]=dep[fa]+1;
	F[now]=fa;
	siz[now]=1;
	for(int i=0;i<eg[now].size();i++){
		int to=eg[now][i];
		if(to==fa) continue;
		dfs1(to,now);
		siz[now]+=siz[to];
		if(siz[to]>siz[son[now]]) son[now]=to;
	}
}
int cnt;
void dfs2(int now,int tp){
	id[now]=++cnt;
	top[now]=tp;
	if(son[now]){
		dfs2(son[now],tp);
	}
	for(int i=0;i<eg[now].size();i++){
		int to=eg[now][i];
		if(to==F[now] or to==son[now]) continue;
		dfs2(to,to);
	}
}

void pushup(int now){
	t[now].sum=t[lc].sum+t[rc].sum;
	t[now].mx=max(t[lc].mx,t[rc].mx);
}

int modi(int now,int l,int r,int X,int k){
	if(!now) now=++tot;
	if(l==r){
		t[now].sum=t[now].mx=k;
		return now;
	}
	int mid=(l+r)>>1;
	if(X<=mid) t[now].ls=(modi(t[now].ls,l,mid,X,k));
	else t[now].rs=(modi(t[now].rs,mid+1,r,X,k));
	pushup(now);
	return now;
}
int qsum(int now,int l,int r,int L,int R){
	if(!now or r<L or l>R) return 0;
	if(L<=l and r<=R){
		return t[now].sum; 
	}
	int mid=(l+r)>>1;
	return qsum(lc,l,mid,L,R)+qsum(rc,mid+1,r,L,R); 
}

int qmax(int now,int l,int r,int L,int R){
	if(!now or r<L or l>R) return 0;
	if(L<=l and r<=R){
		return t[now].mx; 
	}
	int mid=(l+r)>>1;
	return max(qmax(lc,l,mid,L,R),qmax(rc,mid+1,r,L,R)); 
}

int qlisum(int x,int y){
	int RT=rt[C[x]];
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=qsum(RT,1,n,id[top[x]],id[x]);
		x=F[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans+=qsum(RT,1,n,id[x],id[y]);
	return ans;
}

int qlimax(int x,int y){
	int RT=rt[C[x]];
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=max(ans,qmax(RT,1,n,id[top[x]],id[x]));
		x=F[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=max(ans,qmax(RT,1,n,id[x],id[y]));
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=tot;i++) rt[i]=i;
	for(int i=1;i<=n;i++){
		cin>>W[i]>>C[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		eg[u].push_back(v);
		eg[v].push_back(u);
	}
	dfs1(1,1);
	dfs2(1,1);
	for(int i=1;i<=n;i++){
		modi(rt[C[i]],1,n,id[i],W[i]);
	}
	for(int i=1;i<=q;i++){
		string opt;
		int x,y;
		cin>>opt>>x>>y;
		if(opt=="CC"){
			modi(rt[C[x]],1,n,id[x],0);
			modi(rt[(C[x]=y)],1,n,id[x],W[x]);
		}
		else if(opt=="CW"){
			W[x]=y;
			modi(rt[C[x]],1,n,id[x],W[x]);
		}
		else if(opt=="QS"){
			cout<<qlisum(x,y)<<"\n";
		}
		else cout<<qlimax(x,y)<<"\n";
	}
}

本人调了一个h,警戒各位搞清楚编号颜色之类的别写混了

标签:17,int,top,2024,dep,ans,now,id,刷题
From: https://www.cnblogs.com/exut/p/18017730

相关文章

  • 2.17
    久违的更新Vue2跳转传参//跳转传参//通过查询参数传参//to="/路径?参数名=参数值"//接收//$route.query.参数名//通过动态路由传参://首先要设置动态路由//{//  path:'/ssss/:words'//}//然后配置导航链接//to="/路径/参数值"//接收//$route.params.参......
  • 2024-02-17-物联网C语言(2-数组)
    2.数组2.1数组的概念​ 数组是若干个相同类型的变量在内存中的有序存储集合。数组存储一组数据数组里面存储的数据类型必须是相同的数字在内存中会开辟一块连续的空间//定义了一个整型的数组a,a是数组的名字,数组中有10个元素,每个元素的类型都是int类型,而且在内存中连续......
  • 【集训笔记】2024 寒假集训 第一天:最优化问题
    最优化问题二分许多最优化问题可以通过二分来转化为判定性问题。0-1分数规划0-1分数规划思想用于求解分式最优化问题。可以通过对分式二分判定,转化为某一式子大于/小于常数,然后求对应最值即可。动态规划动态规划算法的一大用处就是解决最优化问题。朴素的动态规划效率一般......
  • 0217-0224校赛部分题解
    SMUWinter2024Round#3(Div.2)对于自己比较有价值的题目是D题https://codeforces.com/gym/102897/problem/D?mobile=trueJ题https://codeforces.com/gym/102897/problem/JK题https://codeforces.com/gym/102897/problem/KE题https://codeforces.com/gym/102897/prob......
  • 2024.2.16
    寄算是比较难的树形dp了吧。。。我的跟题解做法不太一样,是维护2个数组\(dp_{0/1,i}\)和\(f_{0/1,i}\)。不太好说,看题解做法吧QAQ。原神#include<bits/stdc++.h>typedeflonglongll;constllSIZE=10000+100;llN,M,a[SIZE];llC;llcnt=1,head[S......
  • 2024-02-16-物联网C语言(数据类型与语句)
    1.第一个C语言程序#include<stdio.h>intmain(){printf("helloworld");return0;}输出结果PSD:\04_Dev\05_C\01数据类型与语句\output>&.\'01_first.exe'helloworld1.1关键字c语言已经定义好的名字,直接拿过来用即可1.1.1数据类型相关的关键字作用:用......
  • 2024/2/16学习进度笔记
    SparkStreaming支持的数据输入源很多,例如:Kafka、Flume、Twitter、ZeroMQ和简单的TCP套接字等等。数据输入后可以用Spark的高度抽象原语如:map、reduce、join、window等进行运算。而结果也能保存在很多地方,如HDFS,数据库等。另外SparkStreaming也能和MLlib(机器学习)以及G......
  • 2024年2月 校内集训
    ......
  • P1706 全排列问题
    全排列问题题目描述按照字典序输出自然数\(1\)到\(n\)所有不重复的排列,即\(n\)的全排列,要求所产生的任一数字序列中不允许出现重复的数字。输入格式一个整数\(n\)。输出格式由\(1\simn\)组成的所有不重复的数字序列,每行一个序列。每个数字保留\(5\)个场宽。......
  • Solution Set【2024.2.16】
    A.寄(post)对于点对贡献问题考虑在最近公共祖先处计算答案,称给定的\(m\)个点为关键点,选择的\(k\)个点为选择点。既然我们已经要求了对于每一对关键点和选择点均在其最近公共祖先处计算答案,那么这也就意味着,存在某些节点,其子树中的关键点/选择点不会与其子树内的选择点/关......