题解 P1188 【PASTE】
囧仙
2020-08-15 16:09:03
## 题目大意
有 $n$ 个数 $1,2,\cdots n$ 。 $m$ 次操作。每次取出 $[A_i,B_i]$ 段,删除后插入第 $C_i$ 个位置后面。输出操作结束后前 $10$ 个数字。
## 题解
观察到题目只要我们输出前 $10$ 个数字,所以其他地方是什么数字不需要在意。
考虑到题目给出的操作形式比较难以处理,我们转换成 $(S_i,T_i,L_i)$ ,表示第 $i$ 个操作将 $[S_i,S_i+L_i)$ 移动到了 $[T_i,T_i+L_i)$ 。
观察到,操作 $(S_i,T_i,L_i)$ 是可逆的,其逆操作为 $(T_i,S_i,L_i)$ 。于是,我们可以将 $m$ 个操作倒过来做,反推出第 $i (i\in[1,10])$ 个地方原先是哪个地方的数字。分类讨论每个逆操作对当前位置 $t$ 的影响。
- 如果逆操作移动的区间包含了当前的 $t$ ,则令 $t\gets t+T_j-S_j$ 。
- 如果逆操作在 $t$ 之前,且这段区间移动后到了 $t$ 的后面,则令 $t\gets t-L_j$ 。
- 如果逆操作在 $t$ 之后,且这段区间移动后到了 $t$ 的前面,则令 $t\gets t+L_j$ 。
最后我们就能反推出 $t$ 原先在哪。由题意可得初始时第 $i$ 个位置放了 $i$ 。
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
typedef long long LL;
const int INF =2147483647;
int qread(){
int w=1,c,ret;
while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret*w;
}
const int MAXN =1e3+3;
int n,m,S[MAXN],T[MAXN],L[MAXN];
int main(){
n=qread(),m=qread(); up(1,m,i){
int a=qread(),b=qread(),c=qread();
L[i]=b-a+1,S[i]=c+1,T[i]=a;
}
up(1,10,i){
int t=i; dn(m,1,j){
if(S[j]<=t&&t<=S[j]+L[j]-1) t+=T[j]-S[j]; else
if(S[j]> t&&T[j]<=t) t+=L[j]; else
if(S[j]< t&&t-L[j]<T[j]) t-=L[j];
}
printf("%d\n",t);
}
return 0;
}
```
复杂度 $\mathcal O(k\times m)$ ,其中 $k$ 为要求我们输出的数字的个数,该题中为 $10$ 。