查看题目 Show Problem

题目:美丽的中国结

问题编号:60

题目描述

题目背景
kitty刚刚高三毕业.看到同学们都回家的回家,旅游的旅游,她的心里有些落寞.英俊潇洒风流倜傥迷倒万千KL却仅对kitty感冒的fish看在眼里,急在心里.一天,fish提出和kitty两个人一起外出旅游.kitty犹豫了几天,想好能瞒过家长的理由后（要问是什么……自己猜去）,答应了.fish很高兴地带着kitty去登记了（别想歪,登记旅游团而已……）,日照青岛五日游.
当然啦,他们玩得很高兴.虽然这次旅行是fish先提议的,但kitty因为玩得很畅快（刚高考完嘛）,所以想送给fish一份礼物,一份能让见多识广的fish都无法忘怀的礼物.她从路边 9¾站台的某算命先生那里得知中国结具有增加RP的效果,而这正是fish所需要的,因此她决定动手给fish编一个奇特的中国结.

题目描述
中国结形式多样,fish会喜欢什么样的呢?思考几天后,kitty决定给fish编一个树状的中国结.这个中国结有n个结点（编号1,2,…,n）,这n个结点之间总共恰有n-1条线相连,其中结点1上是树的根.这是一个奇特的中国结,因此它的编织方式也很奇特.在编织过程中的每一步骤,kitty有时需要将一个结点子树里的所有结点i的状态全部取反（如果原来结点i已经打结,则解开i,否则将结点i打结）,有时又需要知道一个结点的子树里有多少已经打结的结点,你能帮助可爱的kitty完成这份礼物吗?

数据规模
对于40% 的数据,1≤n≤10000, 1≤m≤20000
对于100%的数据,1≤n≤100000, 1≤m≤100000

输入格式

输入
第一行有个整数n,表示这个中国结有n个结点
以下n-1行,每行有两个整数u和v(1≤u,v≤n),表示结点u和v间有一条线相连；
再一行有个整数m,表示kitty要进行的步骤数
以下m行,每行可能为:
"C x":表示将结点x的子树中所有结点的状态取反（包括x）
或
"Q x":表示kitty想知道结点x的子树中有多少已经打结的结点（包括x）

输出格式

对于每个“Q x”输出一行整数,表示结点x的子树中有多少已经打结的结点（包括x）

样例输入

5
1 2
1 3
2 4
2 5
5
Q 1
C 1
Q 1
C 2
Q 1

样例输出

0
5
2

zkw线段树在某个区间上取反（xor 1） ，求某个区间的和

zkw线段树的标记永久化在该题中不适用、

所以可以记一般的Lazy标记--

在处理区间时，把这个区间可能用到的点的标记全部下传

处理完区间后update左、右结点，把区间上传（这样就能消除标记上方结点为0对结果的影响)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define MAXm (100000+10)
#define NDEBUG
int n,m,M,t[MAXN*10]={0},l[MAXN],r[MAXN];
bool mark[MAXN*10]={false};
char s[50];
int head[MAXN*2]={0},next[MAXN*2],edge[MAXN*2],size=0;
void addedge(int u,int v)
{
	edge[++size]=v;
	next[size]=head[u];
	head[u]=size;
}
int tim=0;
bool b[MAXN]={0};
void dfs(int u)
{
	b[u]=1;l[u]=++tim;
	int p=head[u];
	while (p)
	{
		if (!b[edge[p]]) dfs(edge[p]);
		p=next[p];
	}
	r[u]=++tim;
}
void pushdown(int x,int p)
{
	if (!x) return;
	pushdown(x>>1,p<<1);
	if (mark[x>>1])
	{
		mark[x]^=1;mark[x^1]^=1;mark[x>>1]=0;
		t[x]=p-t[x];t[x^1]=p-t[x^1];
	}
	x>>=1;

}
void update(int x)
{
	for (x>>=1;x;x>>=1) t[x]=t[x<<1]+t[(x<<1)^1];
}
int main()
{
	#ifndef NDEBUG
	freopen("RQNOJ60.in","r",stdin);
	#endif
	scanf("%d",&n);
	for (int i=1;i<n;i++) {int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);	}
	dfs(1);
	M=1;while (M-2<r[1]+1) M<<=1;
	scanf("%d",&m);
	#ifndef NDEBUG
//	cout<<M;
	for (int i=1;i<=n;i++) cout<<i<<':'<<l[i]<<'-'<<r[i]<<' ';
	cout<<'n';
	#endif
	for (int k=1;k<=m;k++)
	{
		int x;
		scanf("%s%d",s,&x);
		if (s[0]=='Q')
		{
			int ans=0,p1=l[x],p2=r[x];
			p1--;p2++;p1+=M;p2+=M;
			pushdown(p1,1);pushdown(p2,1);
//			cout<<"add: ";
			#ifndef NDEBUG
			cout<<p1<<' '<<p2<<endl;
			#endif
//			cout<<mark[10];
			while (p1^p2^1)
			{
				if (~p1&1) {/*pushdown(p1+1,1);*/ans+=t[p1+1];/*cout<<p1+1<<':'<<t[p1+1]<<' ';*/}
				if (p2&1)  {/*pushdown(p2-1,1);*/ans+=t[p2-1];/*cout<<p2-1<<':'<<t[p2-1]<<' ';*/}
				p1>>=1;p2>>=1;
			}
			cout<<ans/2<<endl;
		}
		else
		{
			int p=1,p1=l[x],p2=r[x];
			p1--;p2++;p1+=M;p2+=M;
			pushdown(p1,1);pushdown(p2,1);
			while (p1^p2^1)
			{
				if (~p1&1) {mark[p1+1]^=1;t[p1+1]=p-t[p1+1];/*cout<<p1+1<<' ';*/}
				if (p2&1) {mark[p2-1]^=1;t[p2-1]=p-t[p2-1];/*cout<<p2-1<<' ';*/}
				p1>>=1;p2>>=1;p<<=1;
			}
/*			for (int i=1;i<=M*2;i++) if (mark[i]) cout<<i<<':'<<t[i]<<' ';
			cout<<endl;*/
//			update(p1);

			update(l[x]-1+M);
/*			for (int i=1;i<=M*2;i++) if (mark[i]) cout<<i<<':'<<t[i]<<' ';
			cout<<endl;
*/			update(r[x]+1+M);

		}
		#ifndef NDEBUG
		for (int i=1;i<=n;i++) if (mark[i]) cout<<i<<' ';
		cout<<endl;
		#endif

	}



	return 0;
} 

Holedox Eating

3
10 8
0 1
0 5
1
0 2
0 0
1
1
1

10 7
0 1
0 5
1
0 2
0 0
1
1

10 8
0 1
0 1
0 5
1
0 2
0 0
1
1

Case 1: 9
Case 2: 4
Case 3: 2

这题是单点修改+区间最值的zkw线段树（a[]表示数量）

这题有几个技巧：

1.线段树多开；

2.'0'点的包含（把所有数字+1，显然不影响Holedox的移动距离）

3.额外信息的记录（为了把这题转换成线段树）

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXT (10+10)
#define MAXN (100000+10)
#define MAXm (100000+10)
#define INF (2139062143)
int n,m,M,T,now,direction,ans;
int t[2][MAXN*10];  //0->max 1->min
int a[MAXN];
void dec(int x)
{
	a[x]--;
	if (a[x]==0)
	{
		x+=M;
		t[0][x]=0;t[1][x]=INF;
		for (x>>=1;x;x>>=1)
		{
			t[0][x]=max(t[0][x<<1],t[0][(x<<1)^1]);
			t[1][x]=min(t[1][x<<1],t[1][(x<<1)^1]);
		}
	}
}
void go_left(int Lans)
{
	ans+=now-Lans;
	now=Lans;direction=-1;
	dec(now);
}
void go_right(int Rans)
{
	ans+=Rans-now;
	now=Rans;direction=1;
	dec(now);
}
int main()
{
	freopen("Holding.in","r",stdin);
	scanf("%d",&T);
	for (int k=1;k<=T;k++)
	{
		memset(t[0],0,sizeof(t[0]));ans=0;
		memset(t[1],127,sizeof(t[1]));
		memset(a,0,sizeof(a));now=1;direction=1; //1->right -1->left
		scanf("%d%d",&n,&m);n+=2;
		M=1;while (M-2<n) M<<=1;
		for (int i=1;i<=m;i++)
		{
			int p1,p2;
			scanf("%d",&p1);
			if (p1==0)
			{
				scanf("%d",&p2);p2+=1;
				a[p2]++;
				if (a[p2]==1)
				{
					p2+=M;t[0][p2]=t[1][p2]=p2-M;
					int p=p2;
					for (p>>=1;p;p>>=1) t[0][p]=max(t[0][p<<1],t[0][(p<<1)^1]);
					for (p2>>=1;p2;p2>>=1) t[1][p2]=min(t[1][p2<<1],t[1][(p2<<1)^1]);
				}
			}
			else
			{
				//(0,now+1)->[1,now]
				int l=M,r=now+1+M,Lans=0,Rans=INF;
				while (l^r^1)
				{
					if (~l&1) Lans=max(Lans,t[0][l+1]);
					if (r&1) Lans=max(Lans,t[0][r-1]);
					l>>=1;r>>=1;
				}
				//(now-1,n)->[now,n-1]
				l=now-1+M;r=n+M;
				while (l^r^1)
				{
					if (~l&1) Rans=min(Rans,t[1][l+1]);
					if (r&1) Rans=min(Rans,t[1][r-1]);
					l>>=1;r>>=1;
				}
				if (Lans==0&&Rans==INF) continue;
				else if (Lans==0) go_right(Rans);
				else if (Rans==INF) go_left(Lans);
				else if (now-Lans<Rans-now) go_left(Lans);
				else if (now-Lans>Rans-now) go_right(Rans);
				else if (now-Lans==0) dec(now);
				else if (direction==1) go_right(Rans);
				else go_left(Lans);




			}
			/*
				for (int j=1;j<=M*2;j++) if (t[0][j]) cout<<j<<":"<<t[0][j]<<' ';
				cout<<endl;
				for (int j=1;j<=M*2;j++) if (t[1][j]<INF) cout<<j<<":"<<t[1][j]<<' ';
				cout<<endl;
			*/




		}
		printf("Case %d: %dn",k,ans);

	}
	return 0;
}

1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1

1
0
0
1

这题是二维的线段树，

先建一棵线段树，再将它的所有结点（包括根）建立一个二叉树（维护这个结点）

异或仅需记录标记某点所对应的区间取反

查找时统计共记了几个标记即可（标记永久化）

Program Matrix;
const
   maxtt=10;
   maxn=1000;
   maxMM=50000;
var
   tt,n,mm,i,j,k,x1,y1,x2,y2,x,y,p1,p2,ans:longint;
   c:char;
   t:array[1..5000,1..5000] of boolean;
   M:longint;

Procedure change_y(x,y1,y2:longint);
var
   i,j:longint;
begin
   dec(y1);inc(y2);
   inc(y1,M);inc(y2,M);
   while ((y1 xor y2 xor 1)>0) do
   begin
      if ((y1 and 1)=0) then t[x,y1+1]:=not(t[x,y1+1]);
      if ((y2 and 1)=1) then t[x,y2-1]:=not(t[x,y2-1]);
      y1:=y1 shr 1;y2:=y2 shr 1;
   end;

end;

Procedure change_x(x1,y1,x2,y2:longint);
var
   i,j:longint;
begin
   dec(x1);inc(x2);
   inc(x1,M);inc(x2,M);
   while ((x1 xor x2 xor 1)>0) do
   begin
      if ((x1 and 1)=0) then change_y(x1+1,y1,y2);
      if ((x2 and 1)=1) then change_y(x2-1,y1,y2);
      x1:=x1 shr 1;x2:=x2 shr 1;
   end;
end;

function find_y(x,y:longint):boolean;
var
   i,j:longint;
begin
   inc(y,M); find_y:=false;
   while (y>0) do
   begin
      if (t[x,y]) then find_y:=not(find_y);
      y:=y shr 1;
   end;

end;
function find_x(x,y:longint):boolean;
var
   i,j:longint;
begin
   inc(x,M); find_x:=false;
   while (x>0) do
   begin
      find_x:=find_x xor find_y(x,y);
      x:=x shr 1;
   end;
end;
begin
   readln(tt);
   while (tt>0) do
   begin
      fillchar(t,sizeof(t),false);
      readln(n,mm);
      M:=1;
      while (M-2<n) do M:=M shl 1;
      for k:=1 to mm do
      begin
         read(c);
         if c='C' then
         begin
            readln(x1,y1,x2,y2);
            change_x(x1,y1,x2,y2);





         end
         else
         begin     //Q
            readln(x1,y1);
            if (find_x(x1,y1)) then writeln('1') else writeln('0');


         end;



      end;
      dec(tt);
      if (tt>0) then writeln;
   end;
end.