博瑞传播最新消息,不解之缘,至高穿越者
2243: [sdoi2011]染色
time limit: 20 sec memory limit: 512 mb
submit: 5143 solved: 1919
[submit][status][discuss]
description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
input
第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面 行每行描述一个操作：
“c a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。
output
对于每个询问操作，输出一行答案。
数n<=10^5，操作数m<=10^5，所有的颜色c为整数且在[0, 10^9]之间。
题意：
一颗树，节点各有颜色，1.修改区间颜色；２.询问区间的颜色段数；
思路：
１.区间操作－－》线段树；
２.给棵树－－》树剖（ｄｆｓ＊２ 找重链，赋树剖的序）；
3.询问连续区间段数：
用线段树节点维护的信息：
１．ｎｕｍ本段区间个数；
２．ｌ本段左端颜色；
３．ｒ本段右端颜色；
（用于判定区间合并的处理）
if(t[lson].r==t[rson].l) t[id].num--;
＊注意颜色可为0，故＊ｌａｚｙ初始－１，或ｃｏｌ＋＋；
代码：
我要评论
#include
#include
#include
#include
#define lson (id*2)
#define rson (id*2+1)
using namespace std;
int n,m;
struct node{
int l,r,num;
int lazy;
}t[800005];
vector lin[100005];
int xx,yy;
int a[100005],b[100005];
int in[100005],out[100005];
int size[100005];
int dep[100005];
int ans;
int top[100005];
int son[100005];
int fa[100005];
int tot;
void dfs1(int id,int pre)//找重链
{
fa[id]=pre;
size[id]=1;
son[id]=-1;
dep[id]=dep[pre]+1;
int len=lin[id].size();
for(int i=0;ir||r=l&&r<=r)
{
t[id].l=t[id].r=v;
t[id].num=1;
t[id].lazy=v;
return ;
}
int mid=(l+r)>>1;
push_down(id);
add(lson,l,mid,l,r,v);
add(rson,mid+1,r,l,r,v);
push_up(id);
}
void query(int id,int l,int r,int l,int r,int ttt)
{
if(l>r||r=l&&r<=r)
{
if(ttt!=2)
ans+=t[id].num;
if(l==r)
xx=t[id].l;
return ;
}
int mid=(l+r)>>1;
push_down(id);
if(r<=mid) query(lson,l,mid,l,r,ttt);
else if(l>mid)
query(rson,mid+1,r,l,r,ttt);
else
{
if(t[lson].r==t[rson].l) ans--;//区间连接处！
query(lson,l,mid,l,r,ttt);
query(rson,mid+1,r,l,r,ttt);
}
}
void build(int id,int l,int r)
{
if(l==r)
{
t[id].num=1;
t[id].l=t[id].r=b[l];
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
push_up(id);
}
int main()
{
int aa,bb,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]++;
}
for(int i=1;idep[bb]) swap(aa,bb);
add(1,1,tot,in[aa],in[bb],v);
}
if(s[0]=='q')
{
ans=0;
scanf("%d%d",&aa,&bb);
while(top[aa]!=top[bb])
{
if(dep[top[aa]]dep[bb]) swap(aa,bb);
query(1,1,tot,in[aa],in[bb],1);
printf("%d\n",ans);
}
}
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论