P6148 [USACO20FEB] Swapity Swapity Swap S
\(n\) 个进行 \(m\) 次操作，每次操作将所给的 \(l\) 到 \(r\) 区间进行翻转。一共会重复 \(k\) 次上述操作。 \(k<=1e9\)。
倍增 \(k\)，设 \(f[i][j]\) 表示总操作重复 \(2^i\) 次后的序列。
预处理时，转移方程为 \(f[i][j]=f[i-1][f[i-1][j]]\)，即从上一次答案两次操作后转移过来。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k;
int f[32][N],ans[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) f[0][i]=i;
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
reverse(f[0]+l,f[0]+r+1);
}
for(int i=1;i<32;i++)
for(int j=1;j<=n;j++) f[i][j]=f[i-1][f[i-1][j]];
for(int i=1;i<=n;i++) ans[i]=i;
int cnt=0;
while(k){
if(k&1) for(int i=1;i<=n;i++) ans[i]=f[cnt][ans[i]];
k>>=1;
cnt++;
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
经典题目。单调队列优化 dp + 倍增。
\(n\) 个点进行 \(m\) 次操作。对于每个点，每次会移动到离自己距离第 \(k\) 远的位置上。\(m\) 次操作后，求原序列各点的现坐标。
\(nxt_i\) 表示距第 \(i\) 个点第 \(k\) 小的位置。该过程用单调队列维护，即让 \(head\) 和 \(tail\) 相差 \(k\)。（因为序列升序）
然后用倍增重复操作。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000010;
int n, k;
ll m;
ll a[N];
int nex[N], tmp[N], ans[N];
int main()
{
scanf("%d%d%lld", &n, &k, &m);
for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
nex[1] = k + 1;
int head = 1, tail = k + 1;
for(int i = 2; i <= n; i ++ )
{
while(tail + 1 <= n && a[i] - a[head] > a[tail + 1] - a[i]) head ++, tail ++;
if(a[i] - a[head] >= a[tail] - a[i]) nex[i] = head;
else nex[i] = tail;
}
for(int i = 1; i <= n; i ++ ) ans[i] = i;
while(m)
{
if(m & 1) for(int i = 1; i <= n; i ++ ) ans[i] = nex[ans[i]];
memcpy(tmp, nex, sizeof(tmp));
for(int i = 1; i <= n; i ++ ) nex[i] = tmp[tmp[i]];
m >>= 1;
}
for(int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0;
}
鸽。
鸽。
鸽。