NOI 2007 項鍊工廠

這個題要用線段樹寫,首先要滿足的就是元素不能大規模移動。而題中的兩種操作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。

相關日誌