题目链接：https://qoj.ac/contest/531/problem/875

题目大意： $n$ 个格子，有 $k$ 条食人鱼，每个格子只有至多一条食人鱼，每秒你可以把手指放到一个没有食人鱼的格子里，然后左右两边离你手指最近的食人鱼会朝你游动一格，要求移动后和你手指不在同一格里面，问最少需要多少秒才能变成目标状态。

做法

相当于把 $n$ 个格子切成 $k+1$ 份，每次操作可以将一个区间 $-2$ ，两边区间 $+1$ ，要求操作后的区间长度 $\ge 2$。（也就是差分，但需要注意的是两边的区间略有区别）

可以发现，根据目标状态可以列出 $k$ 个方程，设 $f_i$ 表示操作区间 $i$ 多少次。

那么有：$f_{i+1}-f_{i}=d_{i}-p_i$ ，可以把所有的 $f$ 用 $f_1$ 表示，显然所有 $f$ 都是非负的。

找到最小的 $f_1$ 使得所有 $f$ 非空，不妨猜测此时的 $f$ 的和就是答案。

这样就只需要验证是否可行就行了，显然 $f$ 的和是 $O(nk^2)$ 的（ $f_i$ 是 $O(nk)$ 的），直接验证就行了，时间复杂度：$O(nk^2)$ 。（题解做法）

什么叫直接验证呢？就是注意到一个区间如果能操作，那么不操作他他一直都处于能操作的状态，所以先后顺序无所谓，直接操作就行了，或者更准确的说，如果不操作一个区间，随着别的区间的操作，这个区间的可操作性是单调不降的，所以以任意顺序操作可操作的区间就是对的。

但是有没有更加快速的搞法呢？（毕竟正常人哪会想到，$n,k,1000$ 最终复杂度是 $O(nk^2)$ 的）

有，我们可以对一个前缀先操作到不能操作位置，然后找到最长的还需要操作的后缀，观察其每个区间的长度，一定是每个区间的长度 $\le 2$ （特殊的，对于第一个区间，我们给其 $+1$ ），然后可以发现，每次前缀外输送进来一个 $1$ ，会引发后缀一串连续的 $2$ 各操作一次（即操作一段连续的区间）。具体可以自己手模一下这个过程，就知道了。

因此，我们从左到右维护前缀，采用增量法的方式进行操作，这样给前缀输送 $1$ 的次数是多少次呢？注意到如果 $i≠k+1$ ，每次操作 $i$ ，不仅像 $i-1$ 这个前缀输送 $1$ ，也会像后输送 $1$ ，所以至多 $n$ 次，即 $nk$ 次，当 $i=k+1$ 时，其的操作次数是 $O(nk)$ 的，所以也至多输送 $O(nk)$ 次，综上，输送 $1$ 的次数是 $O(nk)$ 次的，

发现往前缀输送 $1$ 所引起的变化的这个过程是可以线段树维护的，于是就做完了，时间复杂度：$O(nk\log{k})$ 。

注：可以注意到，在同一个前缀下，不断给这个前缀的最后一个位置添加 $1$ ，后缀最长的连续的 $2$ 的长度，在没有位置操作次数达到的情况下，至多减少 $1$ ，而操作次数到的时候会把这个位置 $ban$ 掉，但至多 ban $k+1$ 次，而且，前缀变化也至多 $k+1$ 次，所以综上，后缀最长的连续的 $2$ 的长度至多变化 $O(nk)$ ，所以可以直接维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3 + 5;
const int inf = 1e9;
// struct node{
//     int lc, rc;
// }
int n, m;
int a[N], b[N], c[N];
struct Tree{
    int lc, rc;
    int val, lazy;
}tr[N * 2]; int cnt;
void pushlazy(int x, int k){
    tr[x].val += k;
    tr[x].lazy += k;
}
void pushdown(int x){
    if(tr[x].lazy){
        pushlazy(tr[x].lc, tr[x].lazy);
        pushlazy(tr[x].rc, tr[x].lazy);
        tr[x].lazy = 0;
    }
}
void update(int x){tr[x].val = min(tr[tr[x].lc].val, tr[tr[x].rc].val);}
int bt(int l, int r){
    int x = ++cnt;
    tr[x].val = inf;
    if(l < r){
        int mid = (l + r) >> 1;
        tr[x].lc = bt(l, mid);
        tr[x].rc = bt(mid + 1, r);
    }
    return x;
}
int findpos(int x, int l, int r){
    if(tr[x].val > 0) return 0;
    if(l == r) return l;
    pushdown(x);
    int mid = (l + r) >> 1;
    int ans = findpos(tr[x].rc, mid + 1, r);
    if(!ans) ans = findpos(tr[x].lc, l, mid);
    return ans;
}
void change(int x, int l, int r, int ll, int rr, int k, int type){
    if(r < ll || l > rr || ll > rr) return ;
    if(l >= ll && r <= rr){
        if(type == 0) pushlazy(x, k);
        else tr[x].val = k, tr[x].lazy = 0;
        return ;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    change(tr[x].lc, l, mid, ll, rr, k, type);
    change(tr[x].rc, mid + 1, r, ll, rr, k, type);
    update(x);
}
int now;
void change(int x, int s){
    a[x] = s;
    if(s != 2) now = max(x + 1, now);
}
void maintain(int f){
    while(now <= f && a[now] != 2) now++;
    while(now > 1 && a[now - 1] == 2) now--;
}
void oper(int x){
    if(x == 1) a[x] --, a[x + 1] ++;
    else if(x == m) a[x] --;
    else a[x] -= 2, a[x + 1] ++;
}
bool solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    int base = 0;
    for(int i = 1; i <= m; i++){
        c[i + 1] = c[i] + b[i] - a[i];
        base = min(base, c[i + 1]);
    }
    //r[i] - l[i] = b[i] - a[i]
    int ans = 0;
    for(int i = 1; i <= m + 1; i++) c[i] -= base, ans += c[i];
    m++;
    bt(1, m);

    a[m] = n + 1;
    for(int i = m; i >= 1; i--) a[i] = a[i] - a[i - 1] - 1;
    a[1]++; a[m]++;

    now = 1;
    for(int i = 1; i <= m; i++){
        while(c[i] && a[i] >= 3){
            if(now <= i - 1) a[i]++;
            change(1, 1, m, now, i - 1, -1, 0);
            if(now != 1){
                int pre = now;
                if(pre != i) change(pre, 1);
                change(pre - 1, a[pre - 1] == -1 ? -1 : a[pre - 1] + 1);
                maintain(i - 1);
            }
            while(tr[1].val == 0){
                int pos = findpos(1, 1, m);
                change(1, 1, m, pos, pos, inf, 1);
                change(pos, -1);
                // maintain(i - 1);
            }
            c[i]--;
            oper(i);
        }
        if(!c[i]) change(i, -1);
        else{
            assert(a[i] <= 2);
            change(i, a[i]);
            change(1, 1, m, i, i, c[i], 1);
        }
        // maintain(i);
    }
    if(tr[1].val <= n * n) return 0;
    else{
        cout << ans << "\n";
        return 1;
    }
}
int main(){
    if(!solve()) cout << "impossible\n";
    return 0;
}

证明

假设现在有一个合法方案：$g_1,g_2,…,g_{k+1}(g_i>0)$ ，现在证明 $g_1-1,g_2-1,…,g_{k+1}-1$ 也是合法的。

反证法，假设不行，我们先一直操作到不能操作为止。

这样，需要操作但是不能操作的区间又连续的构成一些区间，我们把其中一个区间拉出来。

显然，在合法方案 $g_{1},g_{2},…,g_{k+1}$ 下按照同样的顺序操作到这一步，这个区间也没办法全部操作两次及以上。（讨论一下就行了，至多一次）

所以矛盾，证毕。

还能更快吗？

其实是可以 $O(nk)$ 的。

注意到线段树维护的次数是一个后缀减，后缀查是否 $<0$ ，而这我们可以维护一个严格递增的单调栈（即维护目前所有的后缀最小值），栈用链表维护，两个元素之间维护差值，同时维护链头的值，每次后缀减相当于在链表的某个位置减，但是代码前的注释可以知道，后缀连续 $2$ 的长度变化为 $O(nk)$ ，即后缀减长度变化至多 $O(nk)$ ，所以可以直接暴力在链表上跳。

但是这样我们并没有实际性的维护操作次数，最后怎么验证合法呢？

两个方法：

  1. 每次把区间减在外面差分操作一下，最后前缀和算一下是否都等于 $0$ 。
  2. 至于算操作次数是否对上了，因为我们不会让一个位置的实际操作次数 $>$ 需要的操作次数。

这样，就能在 $O(nk)$ 的时间解决此题。

因为代码太难写了，所以没有代码。摆了