CF1373G Pawns

发表于 | 阅读数

增加点$a_i$，然后一个位置只能挤一个不然，就要往上挤。询问最少要增高多少。

可以看成二分图匹配。

假设$s$

$f[j]$表示$j$以上的$a_j$有几个。

根据$hall$定理,$s-j+1\geq f[j]$.

根据$hall$定理,$s\geq f[j]+j-1$.

$(max(a_i),s]$必然可以。

只需要找$f[i]\in[1,max(a_i)]$的最大值。

然后维护就是$[1,j]$的$f[j]$的区间$+$。

代码 
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

#include <bits/stdc++.h>
#include <set>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;

const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
const int SEN = 1e6 + 10;
struct segmentTree
{
    int lazy[SEN << 2], mx[SEN << 2];
    void addtag(int pos, int l, int r, int w)
    {
        lazy[pos] += w;
        mx[pos] += w;
    }
    void pushdown(int pos, int l, int r)
    {
        if (lazy[pos])
        {
            int w = lazy[pos];
            int mid = (l + r) >> 1;
            addtag(pos << 1, l, mid, w);
            addtag(pos << 1 | 1, mid + 1, r, w);

            lazy[pos] = 0;
        }
    }
    void pushup(int pos)
    {

        mx[pos] = max(mx[pos << 1 | 1], mx[pos << 1]);
    }
    int query(int ql, int qr, int pos, int l, int r)
    {
        if (ql > qr)
            return 0;
        if (ql <= l && r <= qr)
        {
            return mx[pos];
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;
        int ans = 0;
        if (ql <= mid)
            ans = max(ans, query(ql, qr, pos << 1, l, mid));
        if (qr > mid)
            ans = max(ans, query(ql, qr, pos << 1 | 1, mid + 1, r));

        return ans;
    }
    void update(int ql, int qr, int w, int pos, int l, int r)
    {
        if (ql > qr)
            return;
        if (ql <= l && r <= qr)
        {
            addtag(pos, l, r, w);
            return;
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;

        if (ql <= mid)
            update(ql, qr, w, pos << 1, l, mid);
        if (qr > mid)
            update(ql, qr, w, pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }

} t;
multiset<int> s;
map<pii, int> mp;
int main()
{
    int n = read(), k = read(), m = read();
    n *= 2;
    for (int i = 1; i <= n; i++)
        t.update(i, i, i - 1, 1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int x = read(), y = read();
        int o = y + abs(x - k);
        if (mp[mk(x, y)] == 0)
        {
            mp[mk(x, y)] = 1;
            s.insert(o);

            t.update(1, o, 1, 1, 1, n);
        }
        else
        {
            mp[mk(x, y)] = 0;
            s.erase(s.lower_bound(o));
            t.update(1, o, -1, 1, 1, n);
        }
        if (s.size() != 0)
            printf("%d\n", max(0, t.query(1, *s.rbegin(), 1, 1, n) - n / 2));
        else
            puts("0");
    }
}