CF793G Oleg and chess

发表于 | 阅读数

有一个 $n×n$ 的矩阵，每行每列至多能放一个棋子，另外有 $q$个矩形的区域不能放棋子（这些矩形区域互不相交），问最多能放多少个棋子。$n,q≤10^4$

朴素来想：

对于每行连接所可以控制的列，跑个最大流。但是点明显很多，那么对于一个区间可以用线段树维护。

  • 如果出现$0101010101$，只需要去掉每个叶子节点往上的那条边。
  • 维护一个区间，可以用lazy表示是存在。（这里可以不用下方标记）

类似扫描线的方法，对每条边更新，类似可持续化线段树的方法更新每次所连的边。

  • 对于每次更新都需要更新节点，（即新增节点，一路上都需要，但是左右节点是可以继承原先的状态的）我们发现每次头节点都要更新。
  • 根据头节点是否全部没有效果，再连接新增的节点。
  • 记住要初始化！
  • 不需要$poshdown$.

边的多少和点的多少显然$n=m=(n+q)\log n$

代码 
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
#define INF 0x3f3f3f3f
const int N = 5e3 + 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;
}
struct Edge
{
    int to, w, nxt;
    Edge() {}
    Edge(int v, int c, int t) : to(v), w(c), nxt(t) {}
};
const int EN = 2e6 + 10;
const int EM = 2e6 + 10;
struct Dinic
{

    Edge e[EM << 1];
    int head[EN], scnt, d[EN], cur[EN];
    pii pre[EN];
    Dinic() { scnt = 1; }
    void addEdge(int u, int v, int w)
    {
        e[++scnt] = Edge(v, w, head[u]);
        head[u] = scnt;
        e[++scnt] = Edge(u, 0, head[v]);
        head[v] = scnt;
    }
    bool bfs(int s, int t)
    {
        queue<int> q;
        memset(d, 0, sizeof(d));
        q.push(s);
        d[s] = 1;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = head[x]; i; i = e[i].nxt)
            {
                int to = e[i].to;
                if (!d[to] && e[i].w)
                {
                    d[to] = d[x] + 1;
                    q.push(to);
                    if (to == t)
                        return true;
                }
            }
        }
        return false;
    }
    int dfs(int x, int t, int flow)
    {
        if (x == t)
            return flow;
        int res = 0;
        for (int i = cur[x]; i; i = e[i].nxt)
        {
            cur[x] = i;
            int to = e[i].to;
            if (d[to] == d[x] + 1 && e[i].w)
            {
                int dis = dfs(to, t, min(flow, e[i].w));
                if (dis)
                {
                    e[i].w -= dis;
                    e[i ^ 1].w += dis;
                    flow -= dis;
                    res += dis;
                    if (!flow)
                        return res;
                }
            }
        }
        return res;
    }
    int Maxflow(int s, int t)
    {
        int ans = 0;
        while (bfs(s, t))
        {
            memcpy(cur, head, sizeof(head));
            ans += dfs(s, t, INF);
        }
        return ans;
    }
    void oput(int x, int k)
    {
        printf("%d ", x);
        for (int i = head[x]; i; i = e[i].nxt)
            if (e[i].w == 0 && e[i].to > k && e[i].to <= 2 * k)
                oput(e[i].to - k, k);
    }
} dc;
int cnt = 0;
int id[N];
int s, t;
struct Segment
{
    int lazy[N];
    void up(int pos)
    {
        id[pos] = ++cnt;
        if (!lazy[pos << 1])
            dc.addEdge(id[pos], id[pos << 1], INF);
        if (!lazy[pos << 1 | 1])
            dc.addEdge(id[pos], id[pos << 1 | 1], INF);
    }
    void build(int pos, int l, int r)
    {
        //id[pos] = ++cnt;
        if (l == r)
        {
            id[pos] = ++cnt;
            dc.addEdge(s, l, 1);
            dc.addEdge(id[pos], t, 1);
            return;
        }
        int mid = (l + r) >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
        up(pos);
        // dc.addEdge(id[pos], id[pos << 1], INF);
        // dc.addEdge(id[pos], id[pos << 1 | 1], INF);
    }
    void update(int ql, int qr, int pos, int l, int r, int w)
    {
        if (ql <= l && r <= qr)
        {
            lazy[pos] += w;
            return;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid)
            update(ql, qr, pos << 1, l, mid, w);
        if (qr > mid)
            update(ql, qr, pos << 1 | 1, mid + 1, r, w);
        up(pos);
    }
} T;
struct node
{
    int x, y, op;
};
vector<node> g[N];
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= m; i++)
    {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        g[x1].push_back((node){y1, y2, 1});
        g[x2 + 1].push_back((node){y1, y2, -1});
    }
    cnt = n;
    s = ++cnt, t = ++cnt;
    T.build(1, 1, n);
    for (int i = 1; i <= n; i++)
    {
        for (node now : g[i])
        {

            T.update(now.x, now.y, 1, 1, n, now.op);
        }
        if (T.lazy[1] == 0)
            dc.addEdge(i, id[1], 1);
    }
    printf("%d\n", dc.Maxflow(s, t));
}