HYSBZ - 2243染色——树链剖分+线段树建树技巧

2024-05-02 21:32

本文主要是介绍HYSBZ - 2243染色——树链剖分+线段树建树技巧,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目描述】
HYSBZ - 2243染色
在这里插入图片描述
【题目分析】
我一直没有看清楚题,以为求的是路径上出现颜色的种类,然后就写了一个区间染色的线段树进行维护,过样例的时候才发现题读错了,人家要求的是路径上出现的颜色段,所以颜色的种类不重要,重要的是每一段每一段。理所当然,我们应该用线段树维护所在区间有多少段。但是左右区间上传的时候如果边界颜色相同(左节点的右边界和右节点的左边界),那么区间个数应该减一。为此,我们还必须维护每个区间左边界和右边界分别是什么颜色以方便查询和上传。因为题目是区间修改,所以我们还要用lazy标记。(用lazy标记的时候要时时记得标记下传,就是因为单点查询的时候忘记要标记下传wa了一下午)
因为在树上,所以我们不仅仅需要判断线段树区间合并的时候左右端点颜色是否相同,还要判断每条链顶和链顶的父节点的颜色是否相同,如果相同答案减一。(每条链都在向链顶合并)

【AC代码】

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>using namespace std;const int MAXN=100005;	//时刻注意数据范围
vector<int>g[MAXN];
int fa[MAXN],A[MAXN],val[MAXN],color[MAXN],pos[MAXN];
bool check[MAXN];
int siz[MAXN],son[MAXN],h[MAXN],top[MAXN];
int cnt=0,n,m;
int num[MAXN<<2],lazy[MAXN<<2];
int lc[MAXN<<2],rc[MAXN<<2];void dfs1(int u,int f)
{int i,v;siz[u]=1;son[u]=0;fa[u]=f;h[u]=h[f]+1;for(i=0;i<g[u].size();i++){v=g[u][i];if(v!=f){dfs1(v,u);siz[u]+=siz[v];if(siz[son[u]]<siz[v]) son[u]=v;}}
}
void dfs2(int u,int f,int k)
{int i,v;top[u]=k;pos[u]=++cnt;color[cnt]=val[u];if(son[u]) dfs2(son[u],u,k);for(i=0;i<g[u].size();i++){v=g[u][i];if(v!=f&&v!=son[u]) dfs2(v,u,v);}
}void pushup(int k)
{num[k]=num[k<<1]+num[k<<1|1];if(rc[k<<1]==lc[k<<1|1]) num[k]--;	//如果左右区间的连接处颜色相同则答案减一lc[k]=lc[k<<1]; rc[k]=rc[k<<1|1];
}void build(int k,int l,int r)
{if(l==r){num[k]=1;lc[k]=rc[k]=color[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);
}void pushdown(int k)
{if(lazy[k]){lazy[k<<1]=lazy[k<<1|1]=lazy[k];lc[k<<1]=lc[k<<1|1]=lazy[k];rc[k<<1]=rc[k<<1|1]=lazy[k];num[k<<1]=num[k<<1|1]=1;lazy[k]=0;}
}void ColorChange(int k,int l,int r,int L,int R,int v)
{if(l>=L && r<=R){num[k]=1; lazy[k]=v;lc[k]=v; rc[k]=v;return;}int mid=(l+r)>>1;pushdown(k);if(L<=mid) ColorChange(k<<1,l,mid,L,R,v);if(R>mid) ColorChange(k<<1|1,mid+1,r,L,R,v);pushup(k); 
}int QueryInterval(int k,int l,int r,int L,int R)
{if(L<=l && r<=R){return num[k];}int mid=(l+r)/2;pushdown(k);int ret=0;if(R<=mid) return QueryInterval(k<<1,l,mid,L,R);else if(L>mid) return QueryInterval(k<<1|1,mid+1,r,L,R);	//这里必须这样写,因为要考虑是否存在区间合并ret+=QueryInterval(k<<1,l,mid,L,R);ret+=QueryInterval(k<<1|1,mid+1,r,L,R);if(rc[k<<1]==lc[k<<1|1]) ret--;return ret;
}int QueryPointColor(int k,int l,int r,int x)
{if(l==r && l==x){return lc[k];}pushdown(k);	//因为这里忘记了.wocint mid=(l+r)>>1;if(x<=mid) return QueryPointColor(k<<1,l,mid,x);else return QueryPointColor(k<<1|1,mid+1,r,x);
}int Findnum(int u,int v)
{memset(check,0,sizeof(check));int ans=0;while(top[u]!=top[v]){if(h[top[u]]<h[top[v]]) swap(u,v);ans+=QueryInterval(1,1,n,pos[top[u]],pos[u]);//printf("ans=%d\n",ans);//printf("QueryPointColor(1,1,n,pos[%d])=%d\nQueryPointColor(1,1,n,pos[%d])=%d\n",top[u],QueryPointColor(1,1,n,pos[top[u]]),fa[top[u]],QueryPointColor(1,1,n,pos[fa[top[u]]]));if(QueryPointColor(1,1,n,pos[top[u]]) == QueryPointColor(1,1,n,pos[fa[top[u]]]))	//考虑链与链的合并ans--;u=fa[top[u]];}if(h[u]<h[v]) swap(u,v);ans+=QueryInterval(1,1,n,pos[v],pos[u]);//printf("ans=%d\n",ans);return ans;
}void update(int u,int v,int w)
{while(top[u]!=top[v]){if(h[top[u]]<h[top[v]]) swap(u,v);ColorChange(1,1,n,pos[top[u]],pos[u],w);u=fa[top[u]];}if(h[u]<h[v]) swap(u,v);ColorChange(1,1,n,pos[v],pos[u],w);
}int main()
{int a,b,c;char s[10];scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&val[i]);for(int i=1;i<n;i++){scanf("%d%d",&a,&b);g[a].push_back(b);g[b].push_back(a);}dfs1(1,0);dfs2(1,0,1);build(1,1,n);while(m--){scanf("%s",s);if(s[0]=='C'){scanf("%d%d%d",&a,&b,&c);update(a,b,c);}else if(s[0]=='Q') {scanf("%d%d",&a,&b);printf("%d\n",Findnum(a,b));}}return 0;
}

这篇关于HYSBZ - 2243染色——树链剖分+线段树建树技巧的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/955174

相关文章

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

电脑报错cxcore100.dll丢失怎么办? 多种免费修复缺失的cxcore100.dll文件的技巧

《电脑报错cxcore100.dll丢失怎么办?多种免费修复缺失的cxcore100.dll文件的技巧》你是否也遇到过“由于找不到cxcore100.dll,无法继续执行代码,重新安装程序可能会解... 当电脑报错“cxcore100.dll未找到”时,这通常意味着系统无法找到或加载这编程个必要的动态链接库

如何关闭 Mac 触发角功能或设置修饰键? mac电脑防止误触设置技巧

《如何关闭Mac触发角功能或设置修饰键?mac电脑防止误触设置技巧》从Windows换到iOS大半年来,触发角是我觉得值得吹爆的MacBook效率神器,成为一大说服理由,下面我们就来看看mac电... MAC 的「触发角」功能虽然提高了效率,但过于灵敏也让不少用户感到头疼。特别是在关键时刻,一不小心就可能触

前端bug调试的方法技巧及常见错误

《前端bug调试的方法技巧及常见错误》:本文主要介绍编程中常见的报错和Bug,以及调试的重要性,调试的基本流程是通过缩小范围来定位问题,并给出了推测法、删除代码法、console调试和debugg... 目录调试基本流程调试方法排查bug的两大技巧如何看控制台报错前端常见错误取值调用报错资源引入错误解析错误

mysql线上查询之前要性能调优的技巧及示例

《mysql线上查询之前要性能调优的技巧及示例》文章介绍了查询优化的几种方法,包括使用索引、避免不必要的列和行、有效的JOIN策略、子查询和派生表的优化、查询提示和优化器提示等,这些方法可以帮助提高数... 目录避免不必要的列和行使用有效的JOIN策略使用子查询和派生表时要小心使用查询提示和优化器提示其他常

Apache伪静态(Rewrite).htaccess文件详解与配置技巧

《Apache伪静态(Rewrite).htaccess文件详解与配置技巧》Apache伪静态(Rewrite).htaccess是一个纯文本文件,它里面存放着Apache服务器配置相关的指令,主要的... 一、.htAccess的基本作用.htaccess是一个纯文本文件,它里面存放着Apache服务器

Spring中@Lazy注解的使用技巧与实例解析

《Spring中@Lazy注解的使用技巧与实例解析》@Lazy注解在Spring框架中用于延迟Bean的初始化,优化应用启动性能,它不仅适用于@Bean和@Component,还可以用于注入点,通过将... 目录一、@Lazy注解的作用(一)延迟Bean的初始化(二)与@Autowired结合使用二、实例解

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Pandas中多重索引技巧的实现

《Pandas中多重索引技巧的实现》Pandas中的多重索引功能强大,适用于处理多维数据,本文就来介绍一下多重索引技巧,具有一定的参考价值,感兴趣的可以了解一下... 目录1.多重索引概述2.多重索引的基本操作2.1 选择和切片多重索引2.2 交换层级与重设索引3.多重索引的高级操作3.1 多重索引的分组聚