October 2022 Algorithm Solution

Movie Festival Queries

题目链接：https://cses.fi/problemset/task/1664/

题目大意：n 部电影将被放映。你知道每部电影的开始和结束时间。你的任务是处理 q 次查询：如果您在特定时间到达和离开电影节，您最多可以观看多少部电影 ？

如果第一部电影在第二部电影开始之前或恰好在第二部电影开始时结束，您可以观看两部电影。您可以在到达时准确地开始第一部电影，并在最后一部电影结束时准确地离开。

解题思路：倍增，定义 dp[i][j]dp[i][j] ，表示第 i 时间看完 2j2^j 部电影的最短结束时间，那么转移方程就是 dp[i][j]=dp[dp[i][j−1]][j−1]dp[i][j] = dp[dp[i][j - 1]][j - 1]，查询从最高位开始更新答案

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
struct w {
    int start, end;
};
w a[N];
int n, q, dp[M][19];
const int tim = 1e6;
void solve() {
    cin >> n >> q;
    lep(i, 1, n) cin >> a[i].start >> a[i].end;
    sort(a + 1, a + 1 + n, [](const w& A, const w& B) {
        if (A.end == B.end) return A.start < B.start;
        return A.end < B.end;
    });
    lep(i, 0, tim) lep(j, 0, 18) dp[i][j] = 1e6; 
    int k = 1;
    lep(i, 1, tim) {
        while (a[k].start < i) k++;
        if (k > n) break;
        dp[i][0] = a[k].end;
    }
    lep(j, 1, 18) lep(i, 1, tim) dp[i][j] = dp[dp[i][j - 1]][j - 1];
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        rep(i, 18, 0) {
            if (dp[l][i] <= r) {
                ans += (1 << i);
                l = dp[l][i];
            }
        }
        cout << ans << endl;
    }
}

Interesting Sections

题目链接：https://codeforces.com/contest/1609/problem/F

题目大意：给定一个数组 a，定义 [l,r][l,r] 区间的最大值为 x，最小值为 y。求 ∑l=1n∑r=lnpopcount(x)==popcount(y)\sum_{l=1}^{n}\sum_{r=l}^{n} popcount(x)==popcount(y)

解题思路：考虑分而治之，枚举左端点，维护左边区间的后缀 max 和 min，同时维护两个位置 pm 和 pn 表示左边当前位置的后缀 max 和 min 在右边区间仍然是最大值和最小值的最靠右的位置

对于右端点在 [m+1,min(pn,pm)][m+1,min(pn,pm)]，区间最大值和最小值都在左边，直接判断 max 和 min 的位数是否相等即可，相等就加上 min(pn,pm)−mmin(pn,pm)-m

右端点在 [min(pn,pm)+1,max(pn,pm)][min(pn,pm)+1,max(pn,pm)]，区间最大值或者最小值在左边，另一个在右边，我们相当于要统计 [min(pn,pm)+1,max(pn,pm)][min(pn,pm)+1,max(pn,pm)] 内二进制表示 1 的个数为定值的个数，这个东西如果我们预处理前缀和的话复杂度是 O(nlog2⁡n)O(nlog^2⁡n)，但如果我们离线下来做一个差分，这样就能做到 O(nlog⁡n)O(nlog⁡n)

右端点在 [maxpn,pm+1,r][max{pn,pm}+1,r]，可以预处理这段区间的答案，然后求后缀和即可

时间复杂度 O(nlog⁡n)O(nlog⁡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
int n, suf[N], sn[61], sm[61];
ll a[N], ans = 0;
vector<PII> x[N], y[N];
void work(int l, int r) {
    if (l == r) {
        ans++;
        return;
    }
    int mid = (l + r) / 2;
    work(l, mid);
    work(mid + 1, r);
    ll mn = 1e18, mx = 0;
    lep(i, mid + 1, r) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
        suf[i] = __builtin_popcountll(mn) == __builtin_popcountll(mx);
        x[i].clear();
        y[i].clear();
    }
    suf[r + 1] = 0;
    rep(i, r, mid) suf[i] += suf[i + 1];
    int pn = mid, pm = mid, cn, cm;
    mn = 1e18, mx = 0;
    rep(i, mid, l) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
        cn = __builtin_popcountll(mn);
        cm = __builtin_popcountll(mx);
        while (pn < r && a[pn + 1] >= mn) pn++;
        while (pm < r && a[pm + 1] <= mx) pm++;
        if (cn == cm) ans += min(pn, pm) - mid;
        if (pn < pm)
            x[pn].emplace_back(cm, -1), x[pm].emplace_back(cm, 1);
        else if (pn > pm)
            y[pm].emplace_back(cn, -1), y[pn].emplace_back(cn, 1);
        ans += suf[max(pn, pm) + 1];
    }
    mn = 1e18, mx = 0;
    lep(i, 0, 60) sn[i] = sm[i] = 0;
    lep(i, mid + 1, r) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
        sn[__builtin_popcountll(mn)]++;
        sm[__builtin_popcountll(mx)]++;
        for (auto j : x[i]) ans += j.se * sn[j.fi];
        for (auto j : y[i]) ans += j.se * sm[j.fi];
    }
}
void solve() {
    cin >> n;
    lep(i, 1, n) cin >> a[i];
    work(1, n);
    cout << ans << endl;
}

Good Subarrays (Hard Version)

题目链接：https://codeforces.com/contest/1736/problem/C2

题目大意：定义一个长度为 m 的数组 b 是好的，如果对所有 i 来说，第 i 个元素大于或等于 i。换句话说，b 是好的，当且仅当对所有 i 来说 bi≥i(1≤i≤m)b_i\ge i(1\le i\le m)

给定一个数组和多次查询，每次查询将原数组的某个元素更改，然后求出修改后的数组有多少对子数组是好的

解题思路：首先预处理，对于每个数找到后面第一个满足 [i,p][i,p] 这段区间是好的，以及这个位置满足条件后的下一个位置。

假如 a[p]<xa[p]<x ，只需要通过二分找到受影响的区间，预处理出贡献的变化，O(1)O(1) 算出答案

否则依然是通过二分找到受影响的区间，受影响的区间 r 之和减去区间长度乘位置 p ,可以理解为所有右端点本来大于 p 的位置右端点都变成了 p

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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
struct segment {
    int l;
    int r;
    int sum;
    int lazy_inc;
    int lazy_rev;
    int Max;
    int Min;
} tr[N << 2];
void increase(int rt, int v) {
    int l = tr[rt].l, r = tr[rt].r;
    tr[rt].sum += (r - l + 1) * v;
    tr[rt].Max += v;
    tr[rt].Min += v;
    tr[rt].lazy_inc += v;
}
void revise(int rt, int v) {
    int l = tr[rt].l, r = tr[rt].r;
    tr[rt].sum = (r - l + 1) * v;
    tr[rt].Max = v;
    tr[rt].Min = v;
    tr[rt].lazy_rev = v;
    tr[rt].lazy_inc = 0;
}
void pushdown(int rt) {
    if (tr[rt].lazy_rev) {
        revise(rt << 1, tr[rt].lazy_rev);
        revise(rt << 1 | 1, tr[rt].lazy_rev);
        tr[rt].lazy_rev = 0;
    }
    if (tr[rt].lazy_inc) {
        increase(rt << 1, tr[rt].lazy_inc);
        increase(rt << 1 | 1, tr[rt].lazy_inc);
        tr[rt].lazy_inc = 0;
    }
}
void pushup(int n) {
    tr[n].Max = max(tr[n << 1].Max, tr[n << 1 | 1].Max);
    tr[n].Min = min(tr[n << 1].Min, tr[n << 1 | 1].Min);
    tr[n].sum = tr[n << 1].sum + tr[n << 1 | 1].sum;
}
void build(int rt, int l, int r) {  //建树
    tr[rt].l = l;
    tr[rt].r = r;
    tr[rt].lazy_inc = 0;
    tr[rt].lazy_rev = 0;
    if (l == r) {
        tr[rt].Min = tr[rt].Max = tr[rt].sum = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}
void modify(int rt, int l, int r, int v) {  //区间修改
    if (l > tr[rt].r || tr[rt].l > r) return;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        revise(rt, v);
        return;
    }
    pushdown(rt);
    modify(rt << 1, l, r, v);
    modify(rt << 1 | 1, l, r, v);
    pushup(rt);
}
void add(int rt, int l, int r, int v) {  //区间加
    if (l > tr[rt].r || tr[rt].l > r) return;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        increase(rt, v);
        return;
    }
    pushdown(rt);
    add(rt << 1, l, r, v);
    add(rt << 1 | 1, l, r, v);
    pushup(rt);
}
int get_Min(int rt, int l, int r) {  //区间最小值
    if (l > tr[rt].r || tr[rt].l > r) return INF;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        return tr[rt].Min;
    }
    int min1 = INF;
    pushdown(rt);
    min1 = min(min1, get_Min(rt << 1, l, r));
    min1 = min(min1, get_Min(rt << 1 | 1, l, r));
    pushup(rt);
    return min1;
}
int get_Max(int rt, int l, int r) {  //区间最大值
    if (l > tr[rt].r || tr[rt].l > r) return -INF;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        return tr[rt].Max;
    }
    int max1 = -INF;
    pushdown(rt);
    max1 = max(max1, get_Max(rt << 1, l, r));
    max1 = max(max1, get_Max(rt << 1 | 1, l, r));
    pushup(rt);
    return max1;
}
int get_sum(int rt, int l, int r) {  //区间和
    if (l > tr[rt].r || tr[rt].l > r) return 0;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        return tr[rt].sum;
    }
    pushdown(rt);
    int lsum = get_sum(rt << 1, l, r);
    int rsum = get_sum(rt << 1 | 1, l, r);
    pushup(rt);
    return lsum + rsum;
}
int get_first(int rt, int l, int r, int x) {  //区间中第一个小于x的数的下标
    int ls = tr[rt].l, rs = tr[rt].r;
    if (ls > r || rs < l) return -1;
    if (l <= ls && rs <= r) {
        if (tr[rt].Min >= x) return -1;
        while (ls != rs) {
            int mid = ls + (rs - ls) / 2;
            if (tr[rt << 1].Min < x) {
                rt = rt << 1;
                rs = mid;
            } else {
                rt = rt << 1 | 1;
                ls = mid + 1;
            }
        }
        return ls;
    }
    int res = get_first(rt << 1, l, r, x);
    if (res != -1) return res;
    return get_first(rt << 1 | 1, l, r, x);
}
int n, q;
int a[N], t[N], st[N];
vector<PII> s[N];
vector<int> x[N], y[N];
PII c[N];
void solve() {
    cin >> n;
    build(1, 1, n);
    lep(i, 1, n) {
        cin >> a[i];
        add(1, i, i, a[i] - i + N);
    }
    int ans = 0;
    lep(i, 1, n) {
        int id = get_first(1, i, n, 0 + N - i + 1);
        if (id == -1)
            ans += n - i;
        else
            ans += id - 1 - i;
        c[i].fi = id;
        if (id != -1) id = get_first(1, id + 1, n, N - i + 1);
        c[i].se = id;
        if (c[i].se == -1) c[i].se = n + 1;
        if (c[i].fi != -1) {
            s[c[i].fi].push_back({c[i].fi - i + 1, c[i].se - c[i].fi});
            t[i] = c[i].fi;
            st[i] = c[i].fi - i;
        } else {
            t[i] = n + 1;
            st[i] = n + 1 - i;
        }
    }
    ans += n;
    lep(i, 1, n) {
        s[i].push_back({-INF, 0LL});
        s[i].push_back({INF, 0LL});
        sort(s[i].begin(), s[i].end());
        st[i] += st[i - 1];
        int len = s[i].size();
        x[i].push_back(s[i][0].first);
        y[i].push_back(s[i][0].second);
        lep(j, 1, len - 1) {
            s[i][j].second += s[i][j - 1].second;
            x[i].push_back(s[i][j].first);
            y[i].push_back(s[i][j].second);
        }
    }
    cin >> q;
    while (q--) {
        int p, z;
        cin >> p >> z;
        if (z > a[p]) {
            int id = upper_bound(x[p].begin(), x[p].end(), z) - x[p].begin();
            cout << ans + y[p][id - 1] << endl;
        } else if (z == a[p]) {
            cout << ans << endl;
        } else {
            int id = upper_bound(t + 1, t + 1 + p, p) - t;
            int ip = p - z;
            if (ip < id)
                cout << ans << endl;
            else {
                cout << ans - (st[ip] - st[id - 1]) + (p - ip) * (ip - id + 1) +
                            (ip - id + 1) * (ip - id) / 2
                     << endl;
            }
        }
    }
}

Division into Two

题目链接：https://atcoder.jp/contests/agc009/tasks/agc009_c

题目大意：有 n 个数分成两个集合 x，y。要求 x 中任意两个数绝对值之差大于等于 A，y 中任意两个数绝对值之差大于等于 B ，问有多少种方案

解题思路：不妨设 A≤BA\le B

若答案不为零，对于任意 1≤i≤n−21\le i \le n - 2，有 si+2−si≥As_{i+2} - s_i \ge A（相邻三个数必然有两个属于同一个集合）

设 f(i) 代表前 i 个数，第 i 个数在 Y 集合中的答案。（我们可以在数列第 n+1 个位置加上一个 inf，这样答案就为 f(n + 1)）

有：

f(i)=∑si−sj≥b∧(j,i)这段区间可以被全部放在 X 集合中f(i) = \sum_{s_i - s_j \ge b \land (j,i)\text{这段区间可以被全部放在 X 集合中}}

可以用一个变量来维护 f(j) 的和，若某一次 si−si−1<as_i - s_{i-1} < a，则把这个变量置零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll n, a, b;
ll c[N], f[N];
void solve() {
    cin >> n >> a >> b;
    lep(i, 1, n) cin >> c[i];
    if (a > b) swap(a, b);
    lep(i, 1, n - 2) {
        if (c[i + 2] - c[i] < a) {
            cout << 0 << endl;
            return;
        }
    }
    f[0] = 1, c[n + 1] = 4e18, c[0] = -4e18;
    ll res = 0, id = 0;
    lep(i, 1, n+1) {
        for (; c[i] - c[id] >= b; id++) res = (res + f[id]) % mod;
        f[i] = res;
        if (c[i] - c[i - 1] < a) res = 0, id = i - 1;
    }
    cout << f[n+1] << endl;
}