初探树链剖分2-SDOI2011染色

SDOI2011染色

这多标记线段树真的是调试老费劲了:|

感觉最好的方式还是直接写对 .

题目大意和思路分析

题目链接  

题意直接看题吧,不是很长,而且是中文的.

树链剖分之后需要用一个多标记线段树解决.

难点一

这个线段树 需要可以区间修改,同时查询区间中有多少段颜色.

为了达成这个目标,需要 维护如下信息:

区间颜色的段数(num),

区间最左边的颜色(lc),

区间最右边的颜色(rc).

区间是否被覆盖的标记(mark).

还好这几个标记的关系不是非常难以维护,pushup和pushdown函数都比较好写.

难点二

利用LCA的框架,链条之间的颜色可能重复,要想办法减去多余的贡献.

调试心得

涉及到树的数据结构调试,往往非常复杂.

gdb和大力printf 都是可选方案(其实都非常繁琐),个人认为gdb在处理线性程序时更有优势.

一方面可以造一些特殊数据,比如一条链,二叉树等等.

另一方面可以把数据结构模板模块化,在容易问题的地方找bug,比如线段树的pushup和pushdown函数.

函数式编程风的代码

其实就是利用define 压缩线段树部分的代码,感觉写的比较顺手:)

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e5+10;

int n,m;

struct Edge{ int to,nxt; }edge[maxv*2];

int head[maxv],tot=0;
void addedge(int from,int to){ edge[tot].to=to; edge[tot].nxt=head[from]; head[from]=tot++; }
int cnt,f[maxv],d[maxv],sz[maxv],son[maxv],rk[maxv],top[maxv],pos[maxv];

// get sz son f d      dfs1(root,0,1);
int dfs1(int u,int fa,int depth){ // 当前节点、父亲节点、层次深度
	f[u]=fa,d[u]=depth,sz[u]=1;
	int maxson=-1;
	for(int i=head[u];~i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa) continue;
		sz[u]+=dfs1(v,u,depth+1);
		if(sz[v]>maxson){
			maxson=sz[v];
			son[u]=v;
		}
	}
	return sz[u];
}

// get rk top pos   dfs2(root,root)
void dfs2(int u,int t) {// 当前节点,重链顶端
	top[u]=t;
	pos[u]=++cnt; //标记dfs序列
	rk[cnt]=u;   //序号cnt对应节点u
	if(!son[u]) return;
	dfs2(son[u],t);
	/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续, 一个点和它的重儿子处于同一条重链,所以重儿子所在重链的顶端还是t*/
	for(int i=head[u];~i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v!=son[u] && v!=f[u])
			dfs2(v,v);
	}
}

struct Tree{
	int num,mark,lc,rc,l,r;
#define o rt
#define ls o<<1
#define rs o<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
#define lc(x) tree[x].lc
#define rc(x) tree[x].rc
#define num(x) tree[x].num
#define mark(x) tree[x].mark
#define l(x) tree[o].l
#define r(x) tree[o].r
}tree[maxv<<2];

void pushup(int o){
	lc(o)=lc(ls);
	rc(o)=rc(rs);
	num(o)=num(ls)+num(rs);
	if(rc(ls)==lc(rs)) num(o)--;
	return;
}

void pushdown(int o){
	if(mark(o)==0) return;
	num(ls)=num(rs)=1;
	mark(ls)=mark(rs)=mark(o);
	lc(ls)=lc(rs)=mark(o);
	rc(ls)=rc(rs)=mark(o);
	mark(o)=0;
	return;
}

int c[maxv];
void build(int l,int r,int o){
	l(o)=l,r(o)=r,mark(o)=0;
	if(l==r){
		lc(o)=rc(o)=c[rk[l]];
		num(o)=1;
		return;
	}
	int m=(l+r)>>1;
	build(lson);build(rson);
	pushup(o);
}

void update(int ql,int qr,int v,int o){
	if(ql<=l(o) && r(o)<=qr){
		num(o)=1;
		mark(o)=lc(o)=rc(o)=v;
		return;
	}
	pushdown(o);
	int m=(l(o)+r(o))>>1;
	if(ql<=m) update(ql,qr,v,ls);
	if(qr>m) update(ql,qr,v,rs);
	pushup(o);
}

Tree merge(Tree fi,Tree se){
	Tree ans;
	ans.num=fi.num+se.num;
	ans.lc=fi.lc;
	ans.rc=se.rc;
	if(fi.rc==se.lc) ans.num--;
	return ans;
}

Tree query(int ql,int qr,int o){
	if(ql<=l(o) && r(o)<=qr) return tree[o];
	pushdown(o);
	int m=l(o)+r(o)>>1;
	if(qr<=m) return query(ql,qr,ls);
	if(ql>m) return query(ql,qr,rs);
	return merge(query(ql,qr,ls),query(ql,qr,rs));
}

void paint(int x,int y,int c){
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]]) swap(x,y);
		update(pos[top[x]],pos[x],c,1);
		x=f[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	update(pos[x],pos[y],c,1);
	return;
}

int qnum(int x,int y){
	int res=0,ql=0,qr=0; Tree t;
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]]) swap(x,y),swap(ql,qr);
		t=query(pos[top[x]],pos[x],1);
		if(t.rc==ql) --t.num;
		res+=t.num;
		ql=t.lc;
		x=f[top[x]];
	}
	if(d[x]>d[y]) swap(x,y),swap(ql,qr);
	t=query(pos[x],pos[y],1);
	if(ql==t.lc) t.num--;
	if(qr==t.rc) t.num--;
	return t.num+res;
}

int main(){
	scanf("%d%d",&n,&m);
	tot=0;inc(i,1,n) head[i]=-1,scanf("%d",c+i);
	inc(i,1,n-1){
		int u,v;scanf("%d%d",&u,&v);
		addedge(u,v); addedge(v,u);
	}
	cnt=0; int r=1; dfs1(r,0,1); dfs2(r,r); 
	build(1,n,1);
	while(m--){
		char op;int a,b,c;
		scanf(" %c",&op);
		if(op=='C'){
			scanf("%d%d%d",&a,&b,&c);
			paint(a,b,c);
		}else if(op=='Q'){
			scanf("%d%d",&a,&b);
			printf("%d\n",qnum(a,b));
		}
	}
	return 0;
}

普通代码

//https://www.luogu.com.cn/problem/P2486 

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
bool show=false;
// --------------------------------------------------------
// notice : 记得更改maxv的数量
const int maxv=1e5+10;

int n,m;

struct Edge{
	int to,nxt;
}edge[maxv*2];

int head[maxv];
int tot=0;

void addedge(int from,int to){
	edge[tot].to=to;
	edge[tot].nxt=head[from];
	head[from]=tot++;
}

int cnt;

int f[maxv];    //保存结点u的父亲结点
int d[maxv];    //保存结点u的深度值
int sz[maxv]; //保存以u为根的子树节点个数
int son[maxv];  //保存重儿子

int rk[maxv];   //保存当前dfs标号在树中所对应的节点
int top[maxv];  //保存当前结点所在链的顶端节点
int pos[maxv];   //保存树中每个结点剖分以后的新编号(dfs的执行顺序)


// get sz son f d 
//  dfs1(root,0,1);
int dfs1(int u,int fa,int depth) // 当前节点、父亲节点、层次深度
{
	f[u]=fa;
	d[u]=depth;
	sz[u]=1;
	int maxson=-1;
	for(int i=head[u];~i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa) continue;
		sz[u]+=dfs1(v,u,depth+1);
		if(sz[v]>maxson){
			maxson=sz[v];
			son[u]=v;
		}
	}
	return sz[u];
}

// get rk top pos
// dfs2(root,root)
void dfs2(int u,int t) // 当前节点,重链顶端
{
	top[u]=t;
	pos[u]=++cnt; //标记dfs序列
	rk[cnt]=u;   //序号cnt对应节点u
	if(!son[u]) return;
	dfs2(son[u],t);
	/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续, 一个点和它的重儿子处于同一条重链,所以重儿子所在重链的顶端还是t*/
	for(int i=head[u];~i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v!=son[u] && v!=f[u])
			dfs2(v,v);
	}
}


struct Tree{
	int val;
	int num;
	int mark;
	int lc,rc; //区间最左的颜色,区间最右的颜色

	int l,r;
}tree[maxv<<2];


#define o rt
#define ls o<<1
#define rs o<<1|1
#define lson l,m,ls
#define rson m+1,r,rs


void pushup(int o){

	tree[o].lc=tree[ls].lc;
	tree[o].rc=tree[rs].rc;
	tree[o].num=tree[ls].num+tree[rs].num;

	if(tree[ls].rc==tree[rs].lc) 
		tree[o].num--;

}

void pushdown(int o){
	if(tree[o].mark==0) return;


	tree[ls].val=tree[rs].val=tree[o].mark;
	tree[ls].num=tree[rs].num=1;
	tree[ls].mark=tree[rs].mark=tree[o].mark;
	tree[ls].lc=tree[rs].lc=tree[o].mark;
	tree[ls].rc=tree[rs].rc=tree[o].mark;

	tree[o].mark=0;
	return;
}


int c[maxv];

void build(int l,int r,int o){

	tree[o].l=l;
	tree[o].r=r;
	tree[o].mark=0;


	if(l==r){
		tree[o].val=c[rk[l]];
//		cout<<c[rk[l]]<<" ";
		tree[o].num=1;
		tree[o].lc=tree[o].val;
		tree[o].rc=tree[o].val;
		return;
	}
	int m=(l+r)>>1;
	build(lson);build(rson);
	pushup(o);
}


void update(int ql,int qr,int v,int o){

	int l=tree[o].l;
	int r=tree[o].r;

	if(ql<=l&&r<=qr){

		tree[o].val=v;
		tree[o].num=1;
		tree[o].mark=v;
		tree[o].lc=v;
		tree[o].rc=v;
		return;
	}
	pushdown(o);
	int m=(l+r)>>1;
	if(ql<=m) update(ql,qr,v,ls);
	if(qr>m) update(ql,qr,v,rs);
	pushup(o);
}

Tree merge(Tree fi,Tree se){
	Tree ans;
	ans.num=fi.num+se.num;
	ans.lc=fi.lc;
    //notice 调试了这么长时间
    //错误原因是这一行的se写错了,写成了fi
	ans.rc=se.rc;
	if(fi.rc==se.lc) ans.num--;
	return ans;
}


Tree query(int ql,int qr,int o){
	int l=tree[o].l;
	int r=tree[o].r;
	if(ql<=l && r<=qr) 
		return tree[o];
	pushdown(o);
	int m=(l+r)>>1;
	if(qr<=m) return query(ql,qr,ls);
	if(ql>m) return query(ql,qr,rs);
	return merge(query(ql,qr,ls),query(ql,qr,rs));
}

void paint(int x,int y,int c){

	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]]) swap(x,y);
		update(pos[top[x]],pos[x],c,1);
		x=f[top[x]];
	}

	if(d[x]>d[y]) swap(x,y);
	update(pos[x],pos[y],c,1);

	return;
}


int qnum(int x,int y){

	int res=0;
	
	Tree t;

	int ql=0,qr=0;

	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]]) swap(x,y),swap(ql,qr);
	//	cout<<pos[top[x]]<<" "<<pos[x]<<endl;

		t=query(pos[top[x]],pos[x],1);
		if(t.rc==ql) --t.num;
		res+=t.num;
		ql=t.lc;
		x=f[top[x]];

	}
	if(d[x]>d[y]) swap(x,y),swap(ql,qr);

	t=query(pos[x],pos[y],1);

	if(ql==t.lc) t.num--;
	if(qr==t.rc) t.num--;

	return t.num+res;
}


int main(){
	scanf("%d%d",&n,&m);
	head[0]=-1;
	tot=0;
	inc(i,1,n){
		scanf("%d",c+i);
		head[i]=-1;
	}

	inc(i,1,n-1){
		int u=read();
		int v=read();
		addedge(u,v);
		addedge(v,u);
	}


	//---------------------------------------------------
	cnt=0;
	int r=1;
	dfs1(r,0,1);
	dfs2(r,r);
	//---------------------------------------------------

	build(1,n,1);


	while(m--){
		char op;
		int a,b,c;
		scanf(" %c",&op);

		if(op=='C'){
			scanf("%d%d%d",&a,&b,&c);
			paint(a,b,c);

		}else if(op=='Q'){
			scanf("%d%d",&a,&b);
			printf("%d\n",qnum(a,b));
		}
	}



	return 0;
}

调试对拍程序

实际上并不是这么对拍找错误数据调试出来的,而是我自己观察出了问题 :|

shell脚本

cnt=0 

while true; do
	./c > data.in
	./a<data.in> a.out
	./b<data.in> b.out
	diff a.out b.out
	if [ $? -ne 0 ] ;
	then break;
	else 
		echo $cnt
		let cnt=cnt+1

	fi
done

调试的线段树程序

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e5+10;

int n,m;

struct Tree{
	int val;
	int num;
	int mark;
	int lc,rc; //区间最左的颜色,区间最右的颜色

	int l,r;
}tree[maxv<<2];


#define o rt
#define ls o<<1
#define rs o<<1|1
#define lson l,m,ls
#define rson m+1,r,rs


void pushup(int o){

	tree[o].lc=tree[ls].lc;
	tree[o].rc=tree[rs].rc;
	tree[o].num=tree[ls].num+tree[rs].num;

	if(tree[ls].rc==tree[rs].lc) 
		tree[o].num--;

}

void pushdown(int o){
	if(tree[o].mark==0) return;


	tree[ls].val=tree[rs].val=tree[o].mark;
	tree[ls].num=tree[rs].num=1;
	tree[ls].mark=tree[rs].mark=tree[o].mark;
	tree[ls].lc=tree[rs].lc=tree[o].mark;
	tree[ls].rc=tree[rs].rc=tree[o].mark;

	tree[o].mark=0;
	return;
}


int c[maxv];

void build(int l,int r,int o){

	tree[o].l=l;
	tree[o].r=r;
	tree[o].mark=0;


	if(l==r){
		tree[o].val=c[l];
	//	cout<<c[l]<<endl;
		//		cout<<c[rk[l]]<<" ";
		tree[o].num=1;
		tree[o].lc=tree[o].val;
		tree[o].rc=tree[o].val;
		return;
	}
	int m=(l+r)>>1;
	build(lson);build(rson);
	pushup(o);
}


void update(int ql,int qr,int v,int o){

	int l=tree[o].l;
	int r=tree[o].r;

	if(ql<=l&&r<=qr){

		tree[o].val=v;
		tree[o].num=1;
		tree[o].mark=v;
		tree[o].lc=v;
		tree[o].rc=v;
		return;
	}
	pushdown(o);
	int m=(l+r)>>1;
	if(ql<=m) update(ql,qr,v,ls);
	if(qr>m) update(ql,qr,v,rs);
	pushup(o);
}

Tree merge(Tree fi,Tree se){
	Tree ans;
	ans.num=fi.num+se.num;
	ans.lc=fi.lc;
    // bug is here
    // se 写成了 fi
	ans.rc=se.rc;
	if(fi.rc==se.lc) ans.num--;
	return ans;
}


Tree query(int ql,int qr,int o){
	//	cout<<ql<<" "<<qr<<endl;
	int l=tree[o].l;
	int r=tree[o].r;

	if(ql<=l && r<=qr) 
		return tree[o];

	pushdown(o);

	int m=(l+r)>>1;

	if(qr<=m) return query(ql,qr,ls);

	if(ql>m) return query(ql,qr,rs);

	return merge(query(ql,qr,ls),query(ql,qr,rs));
}

void print(){
	inc(i,1,n) {
		Tree t=query(i,i,1);
		cout<<t.val<<" ";
	}
	cout<<endl;

	return;

	inc(i,1,n){
		Tree t=query(i,i,1);
		cout<<t.lc<<" ";
	}
	cout<<endl;
	
	inc(i,1,n){
		Tree t=query(i,i,1);
		cout<<t.rc<<" ";
	}
	cout<<endl;
	

}






int main(){
	scanf("%d",&n);
	inc(i,1,n) scanf("%d",c+i);
	build(1,n,1);

	print();

	scanf("%d",&m);
	while(m--){
		string op;
		int a,b,c;
		cin>>op;
		if(op=="change") {
			cin>>a>>b>>c;
			update(a,b,c,1);
		}
		else {
			cin>>a>> b;
			Tree o=query(a,b,1);
			cout<<o.num<<endl;
		}
		print();
	}
	return 0;
}

对拍程序

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

const int maxv=1e5+10;

int n,m;

int c[maxv];


void update(int ql,int qr,int v){
	for(int i=ql;i<=qr;i++) c[i]=v;
	return ;
}

int query(int ql,int qr,int o){

	int cnt=0;
	for(int i=ql;i<qr;i++)
		if(c[i]!=c[i+1]) cnt++;
	return cnt+1;
}

void print(){
	inc(i,1,n) {
		cout<<c[i]<<" ";
	}
	
	cout<<endl;

}




int main(){
	scanf("%d",&n);
	inc(i,1,n) scanf("%d",c+i);

	print();

	scanf("%d",&m);
	while(m--){
		string op;
		int a,b,c;
		cin>>op;
		if(op=="change") {
			cin>>a>>b>>c;
			update(a,b,c);
		}
		else {
			cin>>a>> b;
			int o=query(a,b,1);
			cout<<o<<endl;
		}
		print();
	}
	return 0;
}

造数据的程序

#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


int main(){
	srand(time(0));

	int n=rand()%100+1;
	cout<<n<<endl;

	inc(i,1,n) {
		int x=rand()%100+1;
		cout<<x<<" ";
	}
	cout<<endl<<endl;
	int m=100;
	cout<<m<<endl;

	while(m--){

		int o=rand()%2;
		if(o==0){
			cout<<"change ";
			int a=rand()%n+1;
			int b=rand()%n+1;
			int c=rand()%n+1;
			if(a>b) swap(a,b);
			cout<<a<<" "<<b<<" "<<c<<endl;
		}
		else 
		{
			cout<<"que ";
			int a=rand()%n+1;
			int b=rand()%n+1;
			if(a>b) swap(a,b);
			cout<<a<<" "<<b<<endl;
		}
	}
}

参考资料

https://blog.csdn.net/qq_43040655/article/details/87286818

https://www.cnblogs.com/mendessy/p/11755588.html


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!