【SDOI2011】【BZOJ2243】【树链剖分】染色

从2.16开坑学链剖,假期颓废无止境回来以后还要每天测试所以1直拖到现在做完了第1个题
话说是否是直接做QT比较好毕竟看起来友好1些这个题的状态实在有些蛋疼
(P.S.我的链剖跟黄学长学的所以写起来和网上的不太1样看起来会很SXBK)
Description

给定1棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成色彩c;
2、询问节点a到节点b路径上的色彩段数量(连续相同色彩被认为是同1段),如“112221”由3段组成:“11”、“222”和“1”。
请你写1个程序顺次完成这m个操作。
Input

第1行包括2个整数n和m,分别表示节点数和操作数;
第2行包括n个正整数表示n个节点的初始色彩
下面 行每行包括两个整数x和y,表示x和y之间有1条无向边。
下面 行每行描写1个操作:
“C a b c”表示这是1个染色操作,把节点a到节点b路径上所有点(包括a和b)都染成色彩c;
“Q a b”表示这是1个询问操作,询问节点a到节点b(包括a和b)路径上的色彩段数量。
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

3

1

2

HINT

数N105,操作数M105,所有的色彩C为整数且在[0, 109]之间。

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 父亲节点,num 点的编号
bool vis[MAXN];//节点是不是已访问过
char ch[2];
struct seg
{
int mark;//染色标记
int l,r;//对应左右区间
int data;//色彩段数量
int lc,rc;//区间左右端点色彩
}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为当前重子节点
int t=0;
for (edge *i=prev[x];i;i=i->next)
if (deep[i->to]>deep[x]&&size[t]<size[i->to])//寻觅重子节点
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);//在轻子节点上重新接出新的链
}
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--;//左右区间相接处
//色彩相同的话需要把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)//修改区间色彩
{
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)//查询区间色彩段数目
{
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)//查询两点间路径色彩段数目
{
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);
}
}
}

能把代码写的这么沙茶我也真是弱求不喷

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【SDOI2011】【BZOJ2243】【树链剖分】染色

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡