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);
}
}
}
