ICPC2023沈阳K

https://codeforces.com/gym/104869/problem/K

DS题尽量进一步思考，简化维护过程

权值线段树上二分

首先得出一个显然的转化：对于每次操作，求出此次下所有正数从小到大的前缀和的第一次大于所有负数和的绝对值的位置即为答案。

赛时做法

既然要求每次都求a升序下的前缀和，很显然的想到维护ai的权值线段树，然后对这个位置二分答案，时间复杂度 (O(n\log n\log n))。

其实是完全能过的，但是我没有通过思考来简化维护过程：

  • 错误实现

维护到当前这个正数的总数时想当然的把所有正数的 rank 扔到了 multiset 里面，

然后用 std::distance(S.begin(), S.lower_bound(k)) 来表示。

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
for (auto&[x, v] : querires) {
    //当前这个下标上对应的数的权值线段树的值
    //不一定就是单点赋值，而是把修改前的那个点减去一次a[x]， 然后在新的v对应的上面加一次a=v

    if (a[x] <= 0) {negative_abs_sum -= std::abs(a[x]);}
    else {
        int id{discreter.query(a[x])};
        T.modify(id, {-a[x]});
    }
    if (v <= 0) {
        negative_abs_sum += std::abs(v);
    } else {
        int id{discreter.query(v)};
        T.modify(id, {v});
    }
    int k{n + Q};
    {//第一遍k
        int lo{}, hi{n + Q - 1}; while (lo <= hi) {
            int mid{(lo + hi) / 2}; 
            (T.rangeQuery(0, mid + 1).sum > negative_abs_sum) 
            ? hi = mid - 1, k = mid : lo = mid + 1;
        }
    }

    a[x] = v; 

    if (k == n + Q) {
        std::cout << std::size(S) + 1 << "\n";
        continue ;
    }

    i64 pre_sum{T.rangeQuery(0, k).sum};

    int k_take{}, pre_take{(int)(std::distance(S.begin(), S.lower_bound(k)))};


    {//第二遍找k取了多少个
        auto k_sum{T.rangeQuery(k, k + 1).sum};
        auto k_val{discreter.queryInv(k)};
        i64 lo{1}, hi{k_sum / k_val}; while (lo <= hi) {
            i64 mid{(lo + hi) / 2}; 
            (pre_sum + mid * k_val > negative_abs_sum) ? 
            hi = mid - 1, k_take = mid : lo = mid + 1;
        }
    }

    std::cout << k_take + pre_take << "\n";

}

但是牛魔的，set 类容器都是不可随机访问容器啊，求迭代器距离是 (o(n)) 的，牛魔的。

而且一开始写 S.lb(k) - S.begin() 不让过编译其实已经告诉你了，但是我当时居然觉得这是对安全性要求比较严格。。。

知道了这个问题之后，要改就很轻松了。

  • 改进思路

显然正数的个数是可以扔到线段树里一起维护的，然后就结束了。

然后还发现另一个唐氏指出，下面那个找第几个的完全可以推个柿子之后 (O(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
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
struct Info {i64 sum{}, cnt{};};//加一个cnt，维护这个权值上的数量

Info operator + (const Info& a, const Info& b) {return {a.sum + b.sum, a.cnt + b.cnt};}

void solve()
{
    int n, Q; std::cin >> n >> Q; std::vector<int> a(n); for (auto& ai : a) {std::cin >> ai;}
    SegmentTree<Info> T(n + Q);
    std::vector<int> positives; for (auto& ai : a) if (ai > 0) {positives.push_back(ai);}
    std::vector<std::pair<int, int>> querires(Q); for (auto&[x, v] : querires) {
        std::cin >> x >> v; --x; if (v > 0) {positives.push_back(v);} 
    }

    Discreter discreter(positives);

    std::map<int, int> cnt; for (auto& ai : a) if (ai > 0) {cnt[ai] += 1;}
    for (auto&[ai, c] : cnt) {T.modify(discreter.query(ai), {c * ai, c});}

    i64 negative_abs_sum{}; for (auto& ai : a) if (ai <= 0) {negative_abs_sum += -ai;}

    for (auto&[x, v] : querires) {
        if (a[x] <= 0) {negative_abs_sum -= std::abs(a[x]);}
        else {
            int id{discreter.query(a[x])};
            T.modify(id, {-a[x], -1});//很显然
        }
        if (v <= 0) {
            negative_abs_sum += std::abs(v);
        } else {
            int id{discreter.query(v)};
            T.modify(id, {v, 1});//很显然
        }
        int k{n + Q};
        {//第一遍k
            int lo{}, hi{n + Q - 1}; while (lo <= hi) {
                int mid{(lo + hi) / 2}; 
                (T.rangeQuery(0, mid + 1).sum > negative_abs_sum) 
                ? hi = mid - 1, k = mid : lo = mid + 1;
            }
        }

        a[x] = v; 

        if (k == n + Q) {
            std::cout << T.rangeQuery(0, n + Q).cnt + 1 << "\n";
            continue ;
        }

        i64 pre_sum{T.rangeQuery(0, k).sum};

        int k_take{}, pre_take{T.rangeQuery(0, k).cnt};//直接维护出来了 [0, k - 1] 的所有正数个数


        {//第二遍找k取了多少个
            auto k_sum{T.rangeQuery(k, k + 1).sum};
            auto k_val{discreter.queryInv(k)};
            //i64 lo{1}, hi{k_sum / k_val}; while (lo <= hi) {
            //    i64 mid{(lo + hi) / 2}; 
            //    (pre_sum + mid * k_val > negative_abs_sum) ? 
            //    hi = mid - 1, k_take = mid : lo = mid + 1;
            //}
          	k_take = (negative_abs_sum - pre_sum + k_val - 1) / k_val;
        }

        std::cout << k_take + pre_take << "\n";

    }

}

佛了。

权值线段树上二分

https://blog.nowcoder.net/n/90af997f26fe4e9ba18c399139d1607e

  • 板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {
    if (l >= y || r <= x) {
        return -1;
    }
    if (l >= x && r <= y && !pred(info[p])) {
        return -1;
    }
    if (r - l == 1) {
        return l;
    }
    int m = (l + r) / 2;
    int res = findFirst(2 * p, l, m, x, y, pred);
    if (res == -1) {
        res = findFirst(2 * p + 1, m, r, x, y, pred);
    }
    return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {
    return findFirst(1, 0, n, l, r, pred);
}

考虑怎么优化掉二分这个 log，可以在线段树上二分。

  • 先解决一个类似且简单的线段树二分问题：

对于 (a_1…a_n)，求第一个 (a_i > k) 的 (i)，带修

显然维护一个最大值的位置线段树：不优化的做法就是二分右端点，(check) T.rangeQuery(0, mid + 1).mx > k

但我们发现这个问题存在一个性质，先左子树后右子树这个顺序找到的第一个解一定是最早出现的。

于是有了下述思路：

每次查找时从根递归向下查找， 对于当前区间 ([l，r])：

  • 若当前节点为叶子结点， 若结点的值满足 $ > v$ ， 返回下标即可；
  • 若左子树最大值大于 (v)（约束）， 则左子树可能存在解， 递归查找左子树； 若左子树查找到解，则直接返回该解（这是一个重要剪枝，可以大幅优化时间， 显然此时即使右子树存在大于 (v) 的元素，也不可能是第一个出现的了，所以没必要再查，否则，若右子树最大值大于 $ v$（约束）， 递归查找右子树；
1
2
3
4
5
6
7
8
9
10
11
12
struct Info {int mx{-1};};

Info operator+(const Info& a, const Info& b) {return {std::max(a.mx, b.mx)};}

void solve()
{
#define tests
    SegmentTree<Info> T(7); int idx{};
    for (auto& ai : {6, 3, 2, 10, 7, 9, 13}) {T.modify(idx, {ai}); idx += 1;}
    debug(T.findFirst(0, 7, [&](auto& f){return f.mx > 9;}))
    //输出为3，正确
}
  • 找到权值线段树上第一个前缀和（指的是权值线段树上的前缀和，从零开始）大于 k 的权值

这个问题同于上述问题的地方是我们要找的也是第一个位置。

这个问题不同于上述问题的地方是，这个问题要求的是前缀和。前缀和这个信息显然并不属于叶子节点，所以如果这样写：

1
T.findFirst(0, n + Q, [&](auto& f){return f.sum > k;})

是不正确的，这实际上是在找第一个大于 (k) 的叶子节点的权值，也就是单个值而非前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Info {int sum{-1};};

Info operator+(const Info& a, const Info& b) {return {a.sum + b.sum};}

void solve()
{
#define tests
    SegmentTree<Info> T(7); int idx{};
    for (auto& ai : {6, 3, 2, 10, 7, 9, 13}) {T.modify(idx, {ai}); idx += 1;}
    debug(T.findFirst(0, 7, [&](auto& f){return f.sum > 9;}));
    //输出为3，他实际上想说的是 10 > 9
    debug(T.findFirst(0, 7, [&](auto& f){return f.sum > 13;}));
    //输出为-1，因为没有叶子节点上的sum比13大，但我们想输出的是 (6 + 3 + 2 + 10 > 13) -> 3 
}

要怎么维护前缀和呢？我们发现一个权值线段树上一个叶子节点的前缀和肯定是等于遍历到他之前所有叶子节点的和，也就是左子树是一定会贡献到右子树上的。

那么在操作的时候我们每次遍历左子树失败（也就是左子树的总和还不够大），准备遍历右子树时，就把左子树的贡献算上去，这样到叶子节点的时候就是对应的前缀和了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int findFirst(int p, int l, int r, int x, int y, i64 tar) {
    if (l >= y || r <= x) {
        return -1;
    }
    if (l >= x && r <= y && (info[p].sum <= tar)) {
        return -1;
    }
    if (r - l == 1) {
        return l;
    }
    int m = (l + r) / 2;
    int res = findFirst(2 * p, l, m, x, y, tar);
    if (res == -1) {
        res = findFirst(2 * p + 1, m, r, x, y, tar - info[2 * p].sum);//把左边的所有贡献加起来，因为是求前缀和，也就是说接下来只要查找到比 tar 减去左边的贡献后还大的值就行了。
    }
    return res;
}
//第一遍线段树二分，找到第一个大于负数绝对值的前缀和的下标
int k{T.findFirst(0, n + Q, negative_abs_sum)};
if (k == -1) {std::cout << T.rangeQuery(0, n + Q).cnt + 1 << "\n"; continue;}
//第二遍找k取了多少个
auto pre_sum{T.rangeQuery(0, k).sum}, pre_take{T.rangeQuery(0, k).cnt}; int k_val{discreter.queryInv(k)};
i64 k_take{(negative_abs_sum - pre_sum) / k_val + 1};