Yura and Developers | Codeforces 549F

题目链接

给定一个长度为 \(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;
}