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。

相关日志