2020牛客NOIP赛前集训营-提高组（第一场） B题 题解

本场全部题解见此

更好的阅读体验

B 牛牛的猜球游戏

题意简述

有一个 的排列，初始为 。

有 次操作，第 次操作可以用两个数 表示，表示交换从前往后第 个数和第 个数。

现有多次询问，每次询问用 表示，询问一个初始排列在依次经过 中每一个交换操作后的排列。

算法标签

前缀和 线段树 置换

算法分析

一次操作的本质可以看做是一个排列到另一个排列的置换，而置换有结合律，因此可以直接上线段树维护，时间复杂度 。

更进一步，置换还具有可减性，因此我们可以直接用前缀和维护置换，时间复杂度 。

代码实现

考场上没想起来置换的可减性，就直接写了线段树，实现难度其实并不是很大。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define LL long long
#define mod 1000000007
#define local
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
template <typename Tp>void read(Tp &x){
    x=0;int fh=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=fh;
}
struct EE{
    int x,y;
}opers[maxn];
int n,m;
#define lson ((x<<1))
#define rson ((x<<1)|1)
#define mid ((l+r)>>1)

int tmp1[10],tmp2[10];

struct node{
    int a[10];
    node operator +(node b)const{//置换的叠加
        node ret;
        for(int j=0;j<10;++j)tmp1[b.a[j]]=j;
        for(int j=0;j<10;++j)tmp2[tmp1[j]]=a[j];
        for(int j=0;j<10;++j)ret.a[j]=tmp2[j];
        return ret;
    }
}st[maxn<<2];
void build(int x,int l,int r){
    if(l==r){
        for(int i=0;i<10;++i)st[x].a[i]=i;//将操作转化为置换
        swap(st[x].a[opers[l].x],st[x].a[opers[l].y]);
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    st[x]=st[lson]+st[rson];
}
node query(int x,int l,int r,int L,int R){
    if(l>=L&&r<=R)return st[x];
    if(R<=mid)return query(lson,l,mid,L,R);
    if(L>mid)return query(rson,mid+1,r,L,R);
    return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
signed main(){
    read(n);read(m);
    for(int i=1;i<=n;++i){
        read(opers[i].x);read(opers[i].y);
    }
    build(1,1,n);
    for(int i=1,l,r;i<=m;++i){
        read(l);read(r);
        node ans=query(1,1,n,l,r);
        for(int j=0;j<10;++j)printf("%d%c",ans.a[j]," \n"[j==9]);
    }
    return 0;
}