Yura and Developers | Codeforces 549F

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

题目链接

给定一个长度为 \(n\) 的序列和数 \(k\)，求有多少长度大于 \(1\) 的区间满足和减最大值是 \(k\) 的倍数。

\(n \le 3 \cdot 10^5,k \le 10^6,a_i \le 10^9\)

先求出前缀和数组 \(pre\)。

则条件可以写成 \(pre_r \equiv pre_{l-1} + \max \pmod k\)。

把 \(i\) 插入 \(\text{vector}[pre_i \bmod k]\)，通过二分可以快速查询区间中有多少前缀和模 \(k\) 余 \(x\)。

求出整个序列的最大值的位置为 \(x\)。

然后枚举 \(x\) 左边的前缀和，查询 \(x\) 右边有多少个前缀和与之配对。

因为 \(x\) 的位置不确定，所以这样是 \(O(n^2\log n)\)。

但如果每次枚举左右中较短的一段，则复杂度可降为 \(O(n \log^2 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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n, K, a[N], L[N], R[N], su[N];
vector <int> v[1000000];
int main() {
    cin >> n >> K;
    rep(i, 1, n) scanf("%d", &a[i]);
    v[0].pb(0);
    rep(i, 1, n) su[i] = (su[i - 1] + a[i]) % K, v[su[i]].pb(i);
    rep(i, 1, n) for(int& j = L[i] = i - 1; j && a[j] <= a[i]; j = L[j]);
    per(i, n, 1) for(int& j = R[i] = i + 1; j <= n && a[j] < a[i]; j = R[j]);
    long long as = 0;
    rep(i, 1, n) if(i - L[i] < R[i] - i) For(j, L[i], i) {
        int t = (su[j] + a[i]) % K;
        #define lb lower_bound
        #define all v[t].begin(), v[t].end()
        as += lb(all, R[i]) - lb(all, i);
    } else For(j, i, R[i]) {
        int t = ((su[j] - a[i]) % K + K) % K;
        as += lb(all, i) - lb(all, L[i]);
    }
    cout << as - n;    
    return 0;
}