倍增 [USACO20FEB] Swapity Swapity Swap S

[USACO20FEB] Swapity Swapity Swap S

显然当我们看到如此大的 \(k\) 时, 我们就应该想到倍增.
我们设 \(f(j,i)\) 为操作 \(2^j\) 时第 \(i\) 个位置所对应的数. 显然我们应该先把 \(j=0\) 时的情况给求出来.

for(int i=1;i<=n;P(i))f[0][i]=i;
for(int l,r,mid;m--;){std::cin>>l>>r;mid=(l+r)>>1;for(int i=l;i<=mid;P(i))std::swap(f[0][i],f[0][r-i+l]);
}

然后就开始上套路了:

for(int j=1;j<=NUMBER2;P(j))for(int i=1;i<=n;P(i))f[j][i]=f[j-1][f[j-1][i]];

然后就是我们喜闻乐见的对 \(k\) 分解

inline int mul(int p,int k){// 在 p 位置上被操作 k 次后所对应的数for(int j=NUMBER2,tem;j>=0;--j){tem=1<<j;if(k>=tem)k-=tem,p=f[j][p];}return p;
}

最后就是我们的总代码:

#include<iostream>
#define P(A) A=-~A
#define NUMBER1 100000
#define NUMBER2 30
int n,m,k,f[NUMBER2+5][NUMBER1+5];
inline int mul(int p,int k){for(int j=NUMBER2,tem;j>=0;--j){tem=1<<j;if(k>=tem)k-=tem,p=f[j][p];}return p;
}
signed main(){std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);std::cout.tie(nullptr);std::cin>>n>>m>>k;for(int i=1;i<=n;P(i))f[0][i]=i;for(int l,r,mid;m--;){std::cin>>l>>r;mid=(l+r)>>1;for(int i=l;i<=mid;P(i))std::swap(f[0][i],f[0][r-i+l]);}for(int j=1;j<=NUMBER2;P(j))for(int i=1;i<=n;P(i))f[j][i]=f[j-1][f[j-1][i]];for(int i=1;i<=n;P(i))std::cout<<mul(i,k)<<'\n';return 0;
}