题解 P4627 【[SHOI2010]滚动的正四面体】

Seauy · 2020-07-06 16:44:47 · 题解

一看任务跟输入就可以认定是个数据结构题

再看一眼数据范围，就可以猜到大概要用线段树维护

那么接下来我们就得分析题目来确定线段树要维护什么、怎么维护了

首先我们要确定一个四面体，我们能用哪些信息来描述它

最重要的信息就应该是 A 面的位置了

我们要记录四面体向前的方向吗？实际上是不需要的，我们可以认为一个四面体翻转完了之后，立即又把改变了方向的“向前方向”对准了朝北的方法，这么做是不会影响答案的

四面体有四个面，三维的不好考虑，我们把它“降维打击”

箭头方向就是“向前方向”

中间的三角形为三面体与地面接触的一面

A 可以放置在四个面的其中任意一个，那么四面体就有四种状态

下面的红字是对于每个状态的编号

通过观察发现，对于每个状态进行 L R B 操作会得到如下表格

[ 过程比较繁琐，有兴趣可以自己推导 ]

这是进行一次翻转操作获得的最终状态的表格

不用找规律，因为找到了也没啥用没有交换律

对于没有交换律的运算，可以用线段树处理出每个状态经过时间 [L,R] 所有操作获得的结果，也就是获得 f_{L,R}(x) ，这个函数是符合结合律的，也就是说可以合并 [L,mid],[mid+1,R] 从而得到 [L,R] 的结果

也就是满足如下公式

状态处理好了，那 A 字面朝下的次数怎么统计呢？

用函数 sum_{L,R}(x) 表示状态 x 经过 [L,R] 所有操作时 A 字面朝下的次数，也就是得到状态 0 的次数

同样满足结合律，用线段树维护

那么最终，我们只要先算出 beg=f_{1,L}(0) 再代入得出 sum_{L,R}(beg) 就行了

上代码

#include<bits/stdc++.h>
#define mid ((L+R)>>1)
#define Lson (now<<1)
#define Rson (now<<1|1)
using namespace std;

const int MAXN=6e4;
const int MAXM=15e4;

struct SegTree
{
    int f[4];
    int sum[4];
    void Clean()
    {
        for(int i=0;i<4;i++) f[i]=i;
        sum[0]=1;
        for(int i=1;i<4;i++) sum[i]=0;
    }
}node[(MAXN<<2)+5];

int n,m;
int A[MAXN+5];
int mapn[4][3];

int Code(char x)
{
    if(x=='L') return 0;
    if(x=='R') return 1;
    return 2;
}

SegTree PushUp(SegTree a,int x,SegTree b)
{
    SegTree cnt;cnt.Clean();
    for(int i=0;i<4;i++)
    {
        cnt.f[i]=b.f[mapn[a.f[i]][A[x]]];
        cnt.sum[i]=a.sum[i]+b.sum[mapn[a.f[i]][A[x]]];
    }
    return cnt;
}

void Build(int now,int L,int R)
{
    if(L==R)
    {
        node[now].Clean();
        return;
    }
    Build(Lson,L    ,mid);
    Build(Rson,mid+1,R  );
    node[now]=PushUp(node[Lson],mid,node[Rson]);
}

void Change(int now,int L,int R,int x)
{
    if(L==R) return;
    if(x<=mid) Change(Lson,L,mid,x);
    else Change(Rson,mid+1,R,x);
    node[now]=PushUp(node[Lson],mid,node[Rson]);
}

void Assis(int x,int v)
{
    A[x]=v;
    Change(1,1,n+1,x);
}

SegTree Ask(int now,int L,int R,int QL,int QR)
{
    if(QL<=L && R<=QR) return node[now];
    if(QL<=mid && mid<QR) return PushUp(Ask(Lson,L,mid,QL,mid),mid,Ask(Rson,mid+1,R,mid+1,QR));
    if(QR<=mid) return Ask(Lson,L,mid,QL,QR);
    return Ask(Rson,mid+1,R,QL,QR);
}

int main()
{
    mapn[0][0]=mapn[0][1]=mapn[0][2]=3;
    mapn[1][1]=mapn[2][2]=mapn[3][0]=1;
    mapn[1][2]=mapn[2][0]=mapn[3][1]=2;
    scanf("%d",&n);
    char c;
    for(int i=1;i<=n;i++)
    {
        cin>>c;
        A[i]=Code(c);
    }
    Build(1,1,n+1);
    scanf("%d",&m);
    bool t;
    for(int L,R,beg;m--;)
    {
        cin>>t;
        if(t)
        {
            scanf("%d %d",&L,&R);
            beg=Ask(1,1,n+1,1,L).f[0];
            printf("%d\n",Ask(1,1,n+1,L,R).sum[beg]);
        }
        else
        {
            scanf("%d",&L);
            cin>>c;
            Assis(L,Code(c));
        }
    }
    return 0;
}