题解 P5640 【【CSGRound2】逐梦者的初心】
Nemlit
2019-11-10 00:52:36
$Updata:$本篇题解现在已经不能通过，就当成是一个常熟优秀的暴力吧，仅供参考
发现我们需要往前/往后插入元素，所以我们可以先预处理出整个T数组，然后记录当前T的左右端点，这样就不需要用什么数据结构来维护了
发现题意其实就是要你求出有多少个L，满足S的前L个数和T的后L个数互不相等
考虑加入每一个数的贡献：
$Case1:\ $往前面插入元素
发现往T数组前面插入元素对我们已经满足条件的L不会产生影响，暴力扫一遍，看是不是整个T与S的前缀互不相等，在存入答案即可
$Case2:\ $往后面插入元素：
首先，如果$S[1]=T[r]$那么则说明$L=1$的时候满足，我们需要加入答案
对于插入前我们已经满足L，我们暴力扫一遍，如果$T[r]=S[r-i+1]$了，则说明这个L已经不合法，删掉即可
于是我们现在需要维护一个东西，支持快速插入，删除，遍历，我这里使用的链表
然后存在一个坑点，最好先把链头设成虚拟节点，否则的话如果删掉链头需要更新（我这里采用的是后者）
~~代码其实挺好写的~~
## $Code:$
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i <= i##Limit ; ++ i)
#define maxn 1000006
int n, m, a[maxn], Ans, nxt[maxn], pre[maxn], opt[maxn], w[maxn], b[maxn], x, l, r, t;
il void del(int x) {
nxt[pre[x]] = nxt[x], pre[nxt[x]] = pre[x];
}
il void solve2() {
for(re int i = t; i; i = nxt[i]) {
if(b[r] == a[r - i + 1]) {
del(i), -- Ans;
if(t == i) t = nxt[i];
}
}
if(b[r] != a[1]) pre[t] = r, nxt[r] = t, t = r, ++ Ans;
}
il void solve() {
rep(i, l, r) if(a[i - l + 1] == b[i]) return;
pre[t] = l, nxt[l] = t, t = l, ++ Ans;
}
signed main() {
n = read(), m = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, m) opt[i] = read(), w[i] = read(), x += opt[i];
l = x + 1, r = x;
rep(i, 1, m) {
if(opt[i] == 1) b[-- l] = w[i];
else b[++ r] = w[i];
}
l = x + 1, r = x;
rep(i, 1, m) {
if(i == 1) {opt[i] == 1 ? -- l : ++ r; solve();}
else if(opt[i] == 1) -- l, solve();
else ++ r, solve2();
printf("%d\n", Ans);
}
return 0;
}
```