国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 【SDOI2011】【BZOJ2243】【树链剖分】染色

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

来源:程序员人生   发布时间:2015-04-08 08:41:50 阅读次数:2208次

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

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

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生