2020牛客暑期多校训练营（第六场）J

Description

给定一个长度为 (n) 的排列和 (m) 次操作，每次操作被描述为 ((k,x)) 表示对排列进行 (x) 次 k-约瑟夫变换，求末态排列。

Solution

设上次取出来的数字是第 pos 个（初态为 1），当前还剩下 cnt 个数字，下一个被选处理的数应当是当前剩下的所有数字中的第 (pos-1+k-1)%cnt+1 个。可以在线段树上二分。

最后对所有求出的排列快速幂即可。

（注意一下置换乘法的方向）

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

#define int long long 
const int N = 500005;

#define lc p*2,l,(l+r)/2
#define rc p*2+1,(l+r)/2+1,r
#define mid (l+r)/2

struct segment_tree
{
    int a[4*N];
    void pushup(int p)
    {
        a[p]=a[p*2]+a[p*2+1];
    }
    void build(int p,int l,int r)
    {
        if(l==r) a[p]=1;
        else build(lc), build(rc), pushup(p);
    }
    void modify(int p,int l,int r,int pos,int key)
    {
        if(l==r) a[p]+=key;
        else if(pos<=mid) modify(lc,pos,key), pushup(p);
        else modify(rc,pos,key), pushup(p);
    }
    int bisect(int p,int l,int r,int k)
    {
        if(l==r) return l;
        if(a[p*2]>=k) return bisect(lc,k);
        else return bisect(rc,k-a[p*2]);
    }
} seg;

int jos[N];

void gen(int n,int k)
{
    seg.build(1,1,n);
    int pos=1;
    for(int i=1;i<=n;i++)
    {
        int cnt=n-i+1;
        pos=(pos-1+k-1+cnt)%cnt+1;
        int val=seg.bisect(1,1,n,pos);
        seg.modify(1,1,n,val,-1);
        jos[i]=val;
    }
}

int buf[N];

void mul(int n,int *a,int *b) // a*=b
{
    for(int i=1;i<=n;i++) buf[i]=a[b[i]];
    for(int i=1;i<=n;i++) a[i]=buf[i];
}

void qpow(int n,int k,int *a,int *b)
{
    if(k==0) return;
    if(k&1) mul(n,a,b);
    mul(n,b,b);
    qpow(n,k/2,a,b);
}

int n,m,p[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m;i++)
    {
        int k,x;
        cin>>k>>x;
        gen(n,k);
        qpow(n,x,p,jos);
    }
    for(int i=1;i<=n;i++) cout<<p[i]<<" ";
    cout<<endl;
    return 0;
}