「CF2173F」Isla's Memory Thresholds

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

Description

Link：CF2173F

给出一个长度为 nn 的非递增序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n（满足 a1≥a2≥⋯≥ana_1 \geq a_2 \geq \cdots \geq a_n）。

有 QQ 次查询，每次查询给出 l,r,xl, r, x，你会依次遍历 al,al+1,⋯ ,ara_l, a_{l + 1}, \cdots, a_r，你有一个计数器 ss（初始 s=0s = 0），每次将当前遍历到的数累加进 ss，若任意时刻 s≥xs \geq x，你就会将 ss 清零。你需要求出遍历结束时，将 ss 清零的次数以及最后 ss 的值。

数据范围：1≤n,Q≤1.5×1051 \leq n, Q \leq 1.5 \times 10^5，1≤ai,x≤1091 \leq a_i, x \leq 10^9，1≤l≤r≤n1 \leq l \leq r \leq n。

时空限制：66s / 10241024MiB。

Solution

算法一

在询问过程中，记 ss 从零到超出阈值 xx 的区间为 “整段”。由于序列 aa 非递增，那么询问过程中，依次经过的整段长度必定是非递减的。

考虑根号分治。记阈值 BB：

  • 对于长度 ≤B\leq B 的整段。这样的长度仅有 O(B)\mathcal{O}(B) 个，对于相同长度的整段我们放在一起处理，可以二分找到允许当前长度跳跃的最远右端点，然后一次性跳完当前长度的整段即可。
  • 对于长度 >B>B 的整段。至多只需要跳 O(nB)\mathcal{O}(\frac{n}{B}) 次，于是二分找到当前整段的右端点，暴力跳整段即可。

取 B=nB = \sqrt{n}，时间复杂度 O(nnlog⁡n)\mathcal{O}(n \sqrt{n} \log n)。

算法二

进一步，发现长度 ≤B\leq B 的整段的跳跃可以预处理。

具体地，离线将所有询问的阈值 xx 记录下来。

需要预处理出 f[len][t] 表示：当阈值为询问的第 tt 小的阈值时，最后一个长度为 len\mathrm{len} 且总和超过阈值的区间右端点（实际上这就是允许长度为 len\mathrm{len} 跳跃的最远右端点）。

对于所有长度为 len\mathrm{len} 的区间来说，位置越靠前总和越大。所以我们直接从右往左依次扫描所有长度为 len\mathrm{len} 的区间，记当前总和已经超过第 tt 小的阈值。每次向左扩展时，就不断地判断当前总和是否超过第 t+1t + 1 小的阈值即可。

取 B=nlog⁡nB = \sqrt{n \log n}，时间复杂度 O(nnlog⁡n)\mathcal{O}(n \sqrt{n \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
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

#define debug(a) std::cout << #a << "=" << (a) << ' '

template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

const int N = 150100, MaxQ = 150100;
const int B = 520;

int n, Q;
int a[N];

i64 pre[N];

int amo, mapval[N]; // amo: amount
int turn(int x) {
    return std::lower_bound(mapval + 1, mapval + 1 + amo, x) - mapval;
}

std::tuple<int, int, int> qry[MaxQ];

void work() {
    std::cin >> n >> Q;

    for (int i = 1; i <= n; i ++) {
        std::cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    amo = 0;
    for (int i = 1; i <= Q; i ++) {
        int l, r, v;
        std::cin >> l >> r >> v;

        mapval[++ amo] = v;
        qry[i] = {l, r, v};
    }

    std::sort(mapval + 1, mapval + 1 + amo);
    amo = std::unique(mapval + 1, mapval + 1 + amo) - mapval - 1;

    std::vector< std::vector<int> > f(B + 1, std::vector<int>(amo + 1, 0));
    for (int len = 1; len <= B; len ++) {
        for (int x = n, t = 0; x >= len; x --) {
            i64 sum = pre[x] - pre[x - len];
            while (t < amo && sum >= mapval[t + 1]) {
                t ++;
                f[len][t] = x;
            }
        }
    }

    for (int qid = 1; qid <= Q; qid ++) {
        auto [l, r, v] = qry[qid];
        int id = turn(v);

        int p = l, res = 0;
        for (int len = 1; len <= B; len ++) {
            int rpos = f[len][id];
            if (rpos >= p) {
                int step = (std::min(r, rpos) - p + 1) / len;
                p += step * len;
                res += step;
            }
        }

        while (pre[r] - pre[p - 1] >= v) {
            int l1 = p, r1 = r;
            while (l1 < r1) {
                int mid = (l1 + r1) >> 1;
                if (pre[mid] - pre[p - 1] >= v) {
                    r1 = mid;
                } else {
                    l1 = mid + 1;
                }
            }

            p = l1 + 1;
            res ++;
        }

        std::cout << res << ' ' << (pre[r] - pre[p - 1]) << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int T;
    std::cin >> T;
    
    while (T --) {
        work();
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/