Beyond the Void
BYVoid
NOI 2007 項鍊工廠
本文正體字版由OpenCC轉換

這個題要用線段樹寫,首先要滿足的就是元素不能大規模移動。而題中的兩種操作rotate和flip實際上是可以設一個偏移量來解決的。設flip爲當前反轉狀態,offset爲向右偏移量。對於R k命令,如果flip爲false,使offset增加k,如果flip爲true,使offset減少k。今後讀入的位置i則應轉化爲絕對位置,如果flip爲true,令i=N-i+2,然後再另i減去offset,超出範圍後要增加或減少N的若干倍使1<=i<=N,得出i的絕對位置。

然後的問題就可以用一棵線段樹來解決了,線段樹上節點需要維護左邊界顏色lc,右邊界顏色rc,區間內顏色塊數目cs,以及一個下傳的標記same,表示該區間完全被染成了一個顏色。在區間查找或修改的時候,每經過一個節點要先標記下傳,返回的時候還要自底向上計算lc,rc,cs。需要注意的是,自底向上計算的時候不要忘了,標記下傳子節點。

由於整個項鍊是一個環,所以在執行C操作時,要判斷最左邊節點和最右邊界點顏色是否相同,如果相同輸出結果要爲root.cs-1。另外,如果整個項鍊就是一個顏色,不能再減1了。

/* 
 * Problem: NOI2007 necklace
 * Author: Guo Jiabao
 * Time: 2009.6.5 16:30
 * State: Solved
 * Memo: 線段樹 標記下傳 上傳計算
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=500001;
struct SegmentTree
{
	struct Sgt_Node
	{
		Sgt_Node *left,*right;
		int a,b,lc,rc,cs,same;
	}SS[MAXN*2],*root;
	int SC;
	Sgt_Node * NewNode(int a,int b)
	{
		SS[++SC].same=0; SS[SC].a=a; SS[SC].b=b;
		SS[SC].lc=SS[SC].rc=0; SS[SC].cs=1;
		SS[SC].left = SS[SC].right = 0;
		return SS+SC;
	}
	void build(Sgt_Node *&x,int a,int b)
	{
		x=NewNode(a,b);
		if (a<b)
		{
			int m=(a+b) >> 1;
			build(x->left,a,m);
			build(x->right,m+1,b);
		}
	}
	void pushdown(Sgt_Node *x)
	{
		if (x->same)
		{
			x->lc = x->rc = x->same;
			x->cs = 1;
			if (x->a!=x->b)
				x->left->same = x->right->same = x->same;
			x->same=0;
		}
	}
	void update(Sgt_Node *x)
	{
		if (x->a!=x->b)
		{
			pushdown(x->left);
			pushdown(x->right);
			x->cs = x->left->cs + x->right->cs;
			if (x->left->rc == x->right->lc)
				x->cs --;
			x->lc = x->left->lc;
			x->rc = x->right->rc;
		}
	}
	int getcolor(Sgt_Node *x,int p)
	{
		pushdown(x);
		int m=(x->a + x->b) >> 1;
		if (x->a==x->b)
			return x->lc;
		else if (p<=m)
			return getcolor(x->left,p);
		else
			return getcolor(x->right,p);
	}
	void paint(Sgt_Node *x,int a,int b,int c)
	{
		int m=(x->a + x->b) >> 1;
		pushdown(x);
		if (x->a ==a && x->b==b)
		{
			x->same=c;
			pushdown(x);
		}
		else
		{
			if (b<=m)
				paint(x->left,a,b,c);
			else if (a>=m+1)
				paint(x->right,a,b,c);
			else
			{
				paint(x->left,a,m,c);
				paint(x->right,m+1,b,c);
			}
			update(x);
		}
	}
	int getcount(Sgt_Node *x,int a,int b)
	{
		int m=(x->a + x->b) >> 1,rs=0;
		pushdown(x);
		if (x->a ==a && x->b==b)
			return x->cs;
		else
		{
			if (b<=m)
				rs = getcount(x->left,a,b);
			else if (a>=m+1)
				rs = getcount(x->right,a,b);
			else
			{
				rs =  getcount(x->left,a,m);
				rs += getcount(x->right,m+1,b);
				if (x->left->rc == x->right->lc)
					rs--;
			}
		}
		update(x);
		return rs;
	}
}Segment;
int N,Q,C,offset;
bool flip;
inline void translate(int &a)
{
	if (flip)
		a=N-a+2;
	a-=offset;
	while (a<1) a+=N;
	while (a>N) a-=N;
}
int main()
{
	int i,k,c,a,b;
	char Cmd[5];
	freopen("necklace.in","r",stdin);
	freopen("necklace.out","w",stdout);
	scanf("%d%d",&N,&C);
	Segment.build(Segment.root,1,N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&c);
		Segment.paint(Segment.root,i,i,c);
	}
	scanf("%d",&Q);
	for (i=1;i<=Q;i++)
	{
		scanf("%s",Cmd);
		switch (Cmd[0])
		{
			case 'R':
				scanf("%d",&k);
				if (!flip)
					offset +=k ;
				else
					offset -=k ;
				while (offset<1) offset+=N;
				while (offset>N) offset-=N;
				break;
			case 'F':
				flip = !flip;
				break;
			case 'S':
				scanf("%d%d",&a,&b);translate(a);translate(b);
				c=Segment.getcolor(Segment.root,a);
				k=Segment.getcolor(Segment.root,b);
				Segment.paint(Segment.root,a,a,k);
				Segment.paint(Segment.root,b,b,c);
				break;
			case 'P':
				scanf("%d%d%d",&a,&b,&c);translate(a);translate(b);
				if (flip){k=a;a=b;b=k;}
				if (a<=b)
					Segment.paint(Segment.root,a,b,c);
				else
				{
					Segment.paint(Segment.root,a,N,c);
					Segment.paint(Segment.root,1,b,c);
				}
				break;
			case 'C':
				if (Cmd[1]=='S')
				{
					scanf("%d%d",&a,&b);
					translate(a);translate(b);
					if (flip){k=a;a=b;b=k;}
					if (a<=b)
						c=Segment.getcount(Segment.root,a,b);
					else
					{
						c=Segment.getcount(Segment.root,a,N);
						c+=Segment.getcount(Segment.root,1,b);
						if (Segment.root->lc == Segment.root->rc)
							c--;
					}
				}
				else
				{
					c=Segment.root->cs;
					if (c>1 && Segment.root->lc == Segment.root->rc)
						c--;
				}
				printf("%dn",c);
				break;
		}
	}
	return 0;
}
<h2><span class="mw-headline">項鍊工廠 </span></h2>

【問題描述】

T公司是一家專門生產彩色珠子項鍊的公司,其生產的項鍊設計新穎、款式多樣、價格適中,廣受青年人的喜愛。最近T公司打算推出一款項鍊自助生產系統,使用該系統顧客可以自行設計心目中的美麗項鍊。

該項鍊自助生產系統包括硬件系統與軟件系統,軟件系統與用戶進行交互並控制硬件系統,硬件系統接受軟件系統的命令生產指定的項鍊。該系統的硬件系統已經完成,而軟件系統尚未開發,T公司的人找到了正在參加全國信息學競賽的你,你能幫助T公司編寫一個軟件模擬系統嗎?

一條項鍊包含N個珠子,每個珠子的顏色是1, 2, …, c中的一種。項鍊被固定在一個平板上,平板的某個位置被標記位置1,按順時針方向其他位置被記爲2,3,…,N。

<a class="image" title="Image:Necklace2007.jpg" href="http://www.ruvtex.cn/wiki/Image:Necklace2007.jpg"><img src="http://www.ruvtex.cn/mw/images/7/77/Necklace2007.jpg" alt="Image:Necklace2007.jpg" width="429" height="447" /></a>

你將要編寫的軟件系統應支持如下命令:

<table border="1">
<tbody>
<tr>
<td width="155">命令</td>
<td width="144">參數限制</td>
<td width="326">內容</td>
</tr>
<tr>
<td>R k</td>
<td>0&lt;k&lt;N</td>
<td>意爲Rotate k。將項鍊在平板上順時針旋轉k個位置, 即原來處於位置1的珠子將轉至位置k+1,處於位置2的珠子將轉至位置k+2,依次類推。</td>
</tr>
<tr>
<td>F</td>
<td></td>
<td>意爲Flip。將平板沿着給定的對稱軸翻轉,原來處於位置1的珠子不動,位置2上的珠子與位置N上的珠子互換,位置3上的珠子與位置N-1上的珠子互換,依次類推。</td>
</tr>
<tr>
<td>S i j</td>
<td>1≤i , j≤N</td>
<td>意爲Swap i , j。將位置i上的珠子與位置j上的珠子互換。</td>
</tr>
<tr>
<td>P i j x</td>
<td>1≤i , j≤N, x≤c</td>
<td>意爲Paint i , j , x。將位置i沿順時針方向到位置j的一段染爲顏色x。</td>
</tr>
<tr>
<td>C</td>
<td></td>
<td>意爲Count。查詢當前的項鍊由多少個“部分”組成,我們稱項鍊中顏色相同的一段爲一個“部分”</td>
</tr>
<tr>
<td>CS i j</td>
<td>1≤i , j≤N</td>
<td>意爲CountSegment i , j。查詢從位置i沿順時針方向到位置j的一段中有多少個部分組成。</td>
</tr>
</tbody></table>

【輸入文件】

輸入文件第一行包含兩個整數N, c,分別表示項鍊包含的珠子數目以及顏色數目。第二行包含N個整數,x1, x2…, xn,表示從位置1到位置N的珠子的顏色,1 ≤xi ≤c。第三行包含一個整數Q,表示命令數目。接下來的Q行每行一條命令,如上文所述。

【輸出文件】

對於每一個C和CS命令,應輸出一個整數代表相應的答案。

【輸入樣例】
<pre>5 3
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1</pre>
【輸出樣例】
<pre>4
1</pre>
【評分方法】

本題沒有部分分,你的程序的輸出只有和標準答案完全一致才能獲得滿分, 否則不得分。

【數據規模和約定】
  • 對於60%的數據,N ≤1 000,Q ≤1 000;
  • 對於100%的數據,N ≤500 000,Q ≤500 000,c ≤1 000。

上次修改時間 2017-05-22

相關日誌