您當前位置：首頁 > php開源 > php教程 > 【SDOI2011】【BZOJ2243】【樹鏈剖分】染色

【SDOI2011】【BZOJ2243】【樹鏈剖分】染色

來源：程序員人生發(fā)布時間：2015-04-08 08:41:50 閱讀次數(shù)：2412次

從2.16開坑學鏈剖，假期頹廢無止境回來以后還要每天測試所以1直拖到現(xiàn)在做完了第1個題
話說是否是直接做QT比較好畢竟看起來友好1些這個題的狀態(tài)實在有些蛋疼
(P.S.我的鏈剖跟黃學長學的所以寫起來和網(wǎng)上的不太1樣看起來會很SXBK)
Description

給定1棵有n個節(jié)點的無根樹和m個操作，操作有2類：
1、將節(jié)點a到節(jié)點b路徑上所有點都染成色彩c；
2、詢問節(jié)點a到節(jié)點b路徑上的色彩段數(shù)量（連續(xù)相同色彩被認為是同1段），如“112221”由3段組成：“11”、“222”和“1”。
請你寫1個程序順次完成這m個操作。
Input

第1行包括2個整數(shù)n和m，分別表示節(jié)點數(shù)和操作數(shù)；
第2行包括n個正整數(shù)表示n個節(jié)點的初始色彩
下面行每行包括兩個整數(shù)x和y，表示x和y之間有1條無向邊。
下面行每行描寫1個操作：
“C a b c”表示這是1個染色操作，把節(jié)點a到節(jié)點b路徑上所有點（包括a和b）都染成色彩c；
“Q a b”表示這是1個詢問操作，詢問節(jié)點a到節(jié)點b（包括a和b）路徑上的色彩段數(shù)量。
Output

對每一個詢問操作，輸出1行答案。
Sample Input

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

Sample Output

HINT

數(shù)N $le$ 10 $^5$ ，操作數(shù)M $le$ 10 $^5$ ，所有的色彩C為整數(shù)且在[0, 10 $^9$ ]之間。

Source

第1輪day1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXINT 0x7fffffff
#define MAXN 100010
#define lchild rt<<1,l,mid
#define rchild rt<<1|1,mid+1,r
#define ln rt<<1
#define rn rt<<1|1
using namespace std;
int n,m;
int top,tp;
int co[MAXN];
int a,b,color;
int deep[MAXN],size[MAXN],chain[MAXN],fa[MAXN][18],num[MAXN];
//deep 深度,size 子樹大小,chain 接的鏈,fa 父親節(jié)點,num 點的編號 
bool vis[MAXN];//節(jié)點是不是已訪問過 
char ch[2];
struct seg
{
    int mark;//染色標記 
    int l,r;//對應左右區(qū)間 
    int data;//色彩段數(shù)量 
    int lc,rc;//區(qū)間左右端點色彩 
}tree[MAXN*4];
struct edge
{
    int to;
    edge *next;
}e[MAXN*2],*prev[MAXN];
void insert(int u,int v)
{
    e[++top].to=v;
    e[top].next=prev[u];
    prev[u]=&e[top];
}
void dfs1(int x)//第1遍DFS處理子樹大小/先人關系/深度 
{
    size[x]=1;
    vis[x]=1;
    for (int i=1;i<=17;i++)
    {
        if (deep[x]<(1<<i)) break;
        fa[x][i]=fa[fa[x][i-1]][i-1];//倍增處理先人 
    }
    for (edge *i=prev[x];i;i=i->next)
    {
        int t=i->to;
        if (vis[t]) continue;
        deep[t]=deep[x]+1;
        fa[t][0]=x;
        dfs1(t);
        size[x]+=size[t];
    }
}
void dfs2(int x,int last)//接鏈上編號.last為之前的鏈 
{
    num[x]=++tp;
    chain[x]=last;//x為當前重子節(jié)點 
    int t=0;
    for (edge *i=prev[x];i;i=i->next)
        if (deep[i->to]>deep[x]&&size[t]<size[i->to])//尋覓重子節(jié)點 
            t=i->to;
    if (!t) return;
    dfs2(t,last);
    for (edge *i=prev[x];i;i=i->next)
        if (deep[i->to]>deep[x]&&i->to!=t)
            dfs2(i->to,i->to);//在輕子節(jié)點上重新接出新的鏈 
}
void push_up(int rt)
{
    tree[rt].lc=tree[ln].lc;tree[rt].rc=tree[rn].rc;
    tree[rt].data=tree[ln].data+tree[rn].data;
    if (tree[ln].rc==tree[rn].lc) tree[rt].data--;//左右區(qū)間相接處
    //色彩相同的話需要把data減1 
}
void push_down(int rt)
{
    if (tree[rt].mark==-MAXINT) return;
    if (tree[rt].l==tree[rt].r) return;
    tree[ln].data=tree[rn].data=1;
    tree[ln].mark=tree[rn].mark=tree[ln].lc=tree[rn].lc=tree[ln].rc=tree[rn].rc=tree[rt].mark;
    tree[rt].mark=-MAXINT;
}
void build(int rt=1,int l=1,int r=n)
{
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].data=1;
    tree[rt].mark=-MAXINT;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(lchild);
    build(rchild);
    //push_up(rt);
}
int lca(int a,int b)//最近公共先人.將鏈提到最近公共先人上 
{
    if (deep[a]<deep[b]) swap(a,b);
    int t=deep[a]-deep[b];
    for (int i=0;i<=17;i++)
        if (t&(1<<i)) a=fa[a][i];
    for (int i=17;i>=0;i--)
        if (fa[a][i]!=fa[b][i]) 
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    if (a==b) return a;
    else return fa[a][0];
}
void modify(int rt,int l,int r,int col)//修改區(qū)間色彩 
{
    push_down(rt);
    int L=tree[rt].l,R=tree[rt].r;
    if (L==l&&R==r)
    {
        tree[rt].data=1;
        tree[rt].lc=tree[rt].rc=col;
        tree[rt].mark=col;
        return;
    }
    int mid=(L+R)>>1;
    if (r<=mid) modify(ln,l,r,col);
    else
    if (l>mid) modify(rn,l,r,col);
    else
    {
        modify(ln,l,mid,col);
        modify(rn,mid+1,r,col);
    }
    push_up(rt);
}
void Modify(int a,int b,int col)//修改兩點間路徑色彩 
{
    while(chain[a]!=chain[b])
    {
        modify(1,num[chain[a]],num[a],col);
        a=fa[chain[a]][0];
    }
    modify(1,num[b],num[a],col);//在把鏈上提以后a在b的左邊
    //(差不多就是這個意思自己懂就行...) 
}
int query(int rt,int l,int r)//查詢區(qū)間色彩段數(shù)目 
{
    push_down(rt);
    int L=tree[rt].l,R=tree[rt].r;
    if (L==l&&R==r) return tree[rt].data;
    int mid=(L+R)>>1;
    if (r<=mid) return query(ln,l,r);
    else
    if (mid<l) return query(rn,l,r);
    else
    {
        if (tree[ln].rc==tree[rn].lc)
            return query(ln,l,mid)+query(rn,mid+1,r)-1;
        else
            return query(ln,l,mid)+query(rn,mid+1,r);
    }
}
int pointcolor(int rt,int x)//查詢某個點的色彩 
{
    push_down(rt);
    int L=tree[rt].l,R=tree[rt].r;
    if (L==R) return tree[rt].lc;
    int mid=(L+R)>>1;
    if (x<=mid) return pointcolor(ln,x);
    else return pointcolor(rn,x);
}
int Query(int a,int b)//查詢兩點間路徑色彩段數(shù)目 
{
    int ret=0;
    while (chain[a]!=chain[b])
    {
        ret+=query(1,num[chain[a]],num[a]);
        if (pointcolor(1,num[chain[a]])==pointcolor(1,num[fa[chain[a]][0]]))
            ret--;
        a=fa[chain[a]][0];
    }
    ret+=query(1,num[b],num[a]);
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&co[i]);
    for (int i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        insert(a,b);insert(b,a);
    }
    dfs1(1);
    dfs2(1,1);
    build();
    for (int i=1;i<=n;i++)
        modify(1,num[i],num[i],co[i]);
    for (int i=1;i<=m;i++)
    {
        scanf("%s",ch);
        if (ch[0]==溫@良@順Q溫@良@順)
        {
            scanf("%d%d",&a,&b);
            int t=lca(a,b);
            printf("%d
",Query(a,t)+Query(b,t)-1);
        }
        else
        {
            scanf("%d%d%d",&a,&b,&color);
            int t=lca(a,b);
            Modify(a,t,color);
            Modify(b,t,color);
        }
    }
}

能把代碼寫的這么沙茶我也真是弱求不噴

生活不易，碼農辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 listview+Fragment特效Demo

下一篇 變量引用（輸入兩個整數(shù)，將它們從小到大輸出）

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

【SDOI2011】【BZOJ2243】【樹鏈剖分】染色