DDOSvoid's Blog

CF 1452E Two Editorials

发表于 分类于
本文字数： 3.5k 阅读时长 ≈ 3 分钟

题目描述

https://codeforces.com/contest/1452/problem/E

Solution

根据区间中点的距离和交的值的性质，我们可以将区间按照区间中点的大小进行排序

这样的话一定有某个分界点，使得左边区间归一个区间，右边区间归一个区间

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 2010
#define cn const node
using namespace std;

int n, m, k;

struct node {
    int x, y;

    node() = default;

    friend bool operator < (cn &u, cn &v) { return u.x + u.y < v.x + v.y; } 
} a[maxn];

int pre[maxn], suf[maxn];

int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + m + 1);
    for (int i = 1; i + k - 1 <= n; ++i) {
        int l = i, r = i + k - 1, sum = 0;
        for (int j = 1; j <= m; ++j) { 
            sum += max(0, min(r, a[j].y) - max(l, a[j].x) + 1);
            pre[j] = max(pre[j], sum);
        }
    }
    for (int i = 1; i + k - 1 <= n; ++i) {
        int l = i, r = i + k - 1, sum = 0;
        for (int j = m; j; --j) { 
            sum += max(0, min(r, a[j].y) - max(l, a[j].x) + 1);
            suf[j] = max(suf[j], sum);
        }
    }
    for (int i = 1; i <= m; ++i) ans = max(ans, pre[i] + suf[i + 1]);
    cout << ans << "\n";
    return 0;
}

如果没有发现这个结论也没关系

我们考虑固定一个区间，移动另一个区间，则对于每个区间，移动的区间与他们的交是先上升后下降的

那么我们就能得到两个端点，在这两个端点，该区间的对于两个区间的贡献交换

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <cctype>
#include <queue>
#define maxn 2010
#define ll long long
#define cn const node
#define cQ const Queue
#define gc getchar
#define pb push_back
using namespace std;

int read() {
    int x = 0, f = 0; char c = gc();
    while (!isdigit(c)) f |= c == '-', c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return f ? -x : x;
}

int n, m, k;

int b[maxn];

struct node {
    int x, y;
} a[maxn];

struct Node {
    int v, id;

    Node() = default;
    Node(int _v, int _id) { v = _v; id = _id; } 
}; vector<Node> A[maxn], B[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int v, add;
} T[maxn * 4];
inline void maintain(int i) { T[i].v = T[lc].v + T[rc].v; }

void build(int i, int l, int r) {
    T[i].v = T[i].add = 0;
    if (l == r) return ; int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
} 

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    T[i].v += (min(R, r) - max(l, L) + 1) * v; 
    if (L <= l && r <= R) return (void) (T[i].add += v);
    int m = l + r >> 1;
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
}

int query(int i, int l, int r, int L, int R, int add) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v + add * (r - l + 1);
    int m = l + r >> 1;
    return query(lc, l, m, L, R, add + T[i].add) + query(rc, m + 1, r, L, R, add + T[i].add);
} 

int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr); 
    
    cin >> n >> m >> k; 
    for (int i = 1; i <= m; ++i) cin >> a[i].x >> a[i].y;
    for (int i = 1; i + k - 1 <= n; ++i) {
        int p = i + k - 1, sum = 0;
        for (int j = 1; j <= n; ++j) A[j].clear(), B[j].clear(); build(1, 1, n);
        for (int j = 1; j <= m; ++j) {
            int l = a[j].x, r = a[j].y, Len = min(r, p) - max(i, l) + 1;
            if (Len <= 0) { update(1, 1, n, l, r, 1); continue ; } 
            A[max(1, Len + l - k)].pb(Node(Len, j));
            B[r - Len + 1].pb(Node(Len, j));
            sum += Len;
        }
        for (int j = 1; j + k - 1 <= n; ++j) {
            for (auto u : A[j]) {
                int v = u.v, id = u.id;
                update(1, 1, n, a[id].x, a[id].y, 1);
                sum -= v;
            }
            for (auto u : B[j]) {
                int v = u.v, id = u.id;
                update(1, 1, n, a[id].x, a[id].y, -1);
                sum += v;
            }
            ans = max(ans, sum + query(1, 1, n, j, j + k - 1, 0));
        }
    } cout << ans << "\n"; 
    return 0; 
}