程序员人生 网站导航

[置顶] 【整合】树链剖分模板(线段树维护)

栏目:php教程时间:2015-04-02 08:12:04

原题是SDOI2011染色
反正链剖都长得差不多不1样的就是线段树根据题自己在查询和修改里改1改就行了
随着黄学长学的倍增记录先人的写法,和网上不太1样求不喷
注释棒棒哒

代码又长跑的也不快我也是醉了 注释代码根据题目不同自己修改 #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)⑴; 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); } } }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐