2020牛客NOIP赛前集训营-提高组（第一场） T2 牛牛的猜球游戏

· · 题解

题目链接： https://ac.nowcoder.com/acm/contest/7605/B

通过记录：

题目链接2：T277380 牛牛的猜球游戏（被我们搬到洛谷力）： https://www.luogu.com.cn/problem/T277380）

题目描述

  有十个数0,1,2,3,4,5,6,7，8,9依次排列为初始序列，告诉你一个长度为 n 的操作表，每次操作为交换处于 a、b 两个位置的数。接下来有m 个询问，对于每一个询问有两个数 l,r ，请回答从初始序列，直接从操作表单的第 l 操作一直执行到 r次操作，并输出此时最终序列。

算法思路

  好怪好怪，我直接暴力枚举薄纱捏。

  啊啊啊， n、m 怎么都是1e5级别的啊。线性都过不了咩？

  诶，那么不就很明显了，因为你始终要处理 m 次询问，那么算法时间复杂度的理论下限都是1e5，所以处理l~r的事情要么O（1）过，要么O(log（r-l）) O（sqrt(r-l） 选吧！！！

  是的，你没想错，这还真的有O（1）的算法，但是log级、根号级的也能过。来康康同机房大佬们的乱搞捏：

  分块做法 来源if-OF。  回滚莫队 来源：Gmt丶FFF 。

  然后我这个蒟蒻，考完之后跑去听评讲，就去调了标准bug了。搞了半天，发现这题想清楚后居然如此简单。

  来想一想一个简单的事情，如果我做了好几次操作，但是如果我知道他操作的最后序列，那我就可以直接调过去。

  啊这不是SB吗？我要知道他的最终序列我还写个啥啊。但事实上，你知道你在读入操作表的时候，是可以得到从初始状态一直操作到现在的序列滴。

  所以我们记下一个“前缀序列”,那么就可以解决所有由1开始的问题。

  但是这还不够！（这不显然吗）我们要想想这个换的本质，实际上原题中也提示到了“换的是杯子，而不是球”！是的，我把里面的球不要说是1,2,3,4,5，而是A,B,C,D,E，这个事情就好理解了。那我们这个“序列”；里存的这个值有什么意义呢？是的，就是初始序列的杯子序号。

  也就是说，我们初始序列比如是ETYMK，而前缀序列是45231，那么它所表达的答案就是MKTYE，诶，是不是好理解了一点。

  那也就是说我们理解到了，前缀序列并不只是记录当前状态，还能是一种可用于转移的东西，等价于“一次操作”。（这里直接看代码也还不错）

  诶？我们把得到的序列可以视为一种操作诶，那我们是不是只要两个状态：原始序列+运算序列，就可以把询问的答案干出来了捏？

  是的捏！我们容易想到，把l-1号的序列或r号的序列作为初始序列，在从蝙蝠侠妈妈那里搞到一手运算序列就算出来了。

  啊对啊，这个运算序列不能去阴间找，得算出来（但是蝙蝠侠的妈妈就没那么幸运了） 。我们一想，奥，另一个就是啊。但又不完全是。因为，是减法！！！

  啊对，我们现在考虑的不能再是“执行操作表”的运算了，应该用“还原”。这就像求一个数列 i~j 的和，那就是 sum[j]-sum[i-1] 。是个恶心的减法。

  要求一个还原序列，其实也还好，我们只会算加法，所以要做的事在记录 sum[i] 时同时记录一个 -sum[j] 。我们还原的思路，就是考虑把一个序列还原回0，也就是0,1,2,3,4,5,6,7,8,9的操作序列。

  如果你已经想清楚了刚才“操作”的本质，你也应该发现了，我们在得到“操作前缀序列”（第i位的数为j意味着将原始序列的第j位放入i位）后，只要把本质逆过来再，就是把第刚才你5位在的那个数记回5这种就好。（没懂可以看看代码，挺简洁的）

  做到这一步，题目的思路就已经清晰下来了：

  首先在读入操作表单时，处理出前缀序列，并根据这个前缀序列得到反向序列（即负前缀序列）。

  然后读入询问时，对于每一个询问，直接用 前缀序列r + 负的前缀序列（l-1） 计算答案序列，输出即可。

  （啊好吧不是O（1）是O（10），但这重要吗？（有点重要））

特殊处理

  别把自己搅糊涂了哟。

代码实现

#include<bits/stdc++.h>
using namespace std;

#define int long long//管他用不用，开就完事了、、、好像真的不用开

int n,m;
int xl[100050][10];//前缀序列
int fxxl[100050][10];//反向序列捏

inline int rd()//读入优化真的不是人手一只吗？
{
    int a=0,f=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) a=(a<<1)+(a<<3)+c-'0';
    return a*f;
}

signed main()
{
    n=rd(),m=rd();

    for(int i=0;i<10;i++)
        xl[0][i]=i,fxxl[0][i]=i;
        //是的捏，0号初始序列就是0,1,2,3,4,5,6,7,8,9

    for(int i=1;i<=n;i++)
    {
        int a=rd(),b=rd();
        for(int j=0;j<10;j++)
            if(j==a) xl[i][j]=xl[i-1][b];//录入，得到前缀序列
            else if(j==b) xl[i][j]=xl[i-1][a];
            else xl[i][j]=xl[i-1][j];

        for(int j=0;j<10;j++)
            fxxl[i][xl[i][j]]=j;
            //得到反向序列，如果上面没懂得，看代码实现可能会更好理解
    }

    for(int i=1;i<=m;i++)
    {
        int l=rd(),r=rd();

        for(int j=0;j<10;j++)
            putchar(fxxl[l-1][xl[r][j]]+'0'),putchar(' ');
            //对l-1的反向序列和r的正向序列相加
        puts("");//换行
    }

    return 0;

}