【题解】HackerRank-Array and Queries

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/array-and-queries-1/problem

题意

给一个集合，支持修改一个集合内的数，每次修改后询问这个集合最少能分解成几个满足元素是一段连续的数字的集合。

题解

  • 考虑没有修改的问题，只要贪心地一次一次拿掉尽可能长的一段数字。
  • 权值线段树上维护（设结点是 [L, R]）：
    • 完全覆盖 [L, R] 的条数
    • 覆盖 L 的条数
    • 覆盖 R 的条数
    • 其他情况
  • 支持信息合并，只要贪心考虑即可。
  • 需要离散化，要把每个数相邻的两个数也离散化进去。

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 3E5 * 6 * 4 + 100;
const LL MOD = 1E9 + 7;
vector<int> t;

int L[N], R[N], all[N], other[N];
#define lson o * 2, l, (l + r) / 2
#define rson o * 2 + 1, (l + r) / 2 + 1, r
void up(int o) {
    int lc = o * 2, rc = lc + 1;
    int la = all[lc], ra = all[rc];
    other[o] = other[lc] + other[rc];
    all[o] = min(la, ra);
    L[o] = la - all[o]; R[o] = ra - all[o];
    int tl = L[rc] - min(L[rc], L[o]), tr = R[lc] - min(R[lc], R[o]);
    other[o] += tl + tr - min(tl, tr);
    L[o] += L[lc]; R[o] += R[rc];
}
void ins(int p, int v, int o = 1, int l = 0, int r = t.size()) {
    if (p > r || l > p) return;
    if (l == r) { all[o] += v; return; }
    else { ins(p, v, lson); ins(p, v, rson); up(o); }
}

int v[N], p[N], x[N];
void add(int x) { t.push_back(x); t.push_back(x - 1); t.push_back(x + 1); }
int id(int x) { return lower_bound(t.begin(), t.end(), x) - t.begin(); }
int main() {
    int n; cin >> n;
    FOR (i, 1, n + 1) { scanf("%d", &v[i]); add(v[i]); }
    int Qn; cin >> Qn;
    FOR (i, 0, Qn) {
        scanf("%d%d", &p[i], &x[i]);
        add(x[i]);
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    FOR (i, 1, n + 1) ins(id(v[i]), 1);
    dbg(L[1], R[1], all[1], other[1]);
    LL Ans = 0;
    FOR (i, 0, Qn) {
        ins(id(v[p[i]]), -1); ins(id(v[p[i]] = x[i]), 1);
        int ans = L[1] + R[1] + all[1] + other[1];
        Ans = (Ans + ans * 1LL * (i + 1)) % MOD;
        dbg(ans);
    }
    cout << Ans << endl;
}