P1956 题解
神眷之樱花
·
·
题解
题意
找出满足子段和在膜 p 意义下大于等于 k 的最小子段和。
题解
根据膜法的性质，我们在膜 p 意义下，进行前缀和操作是可以的。那么我们就优化了找子段和这一步骤。
那么现在剩下的问题就是找哪一段子段和。
因为前缀和都膜了 $p$，所以所有的前缀和都是在 $0$ ~ $p - 1$ 内的。
那么对于右端点 $i$， 当子段和大于等于 $k$ 的时候，满足条件的左端点 $j$， 满足如下性质。
$$sum[i] - sum[j] \geq k(sum[i]> sum[j])$$
$$sum[i] - sum[j] + p \geq k(sum[i]\leq sum[j])$$
稍作变形之后，就得到了如下柿子：
$$sum[j] \leq sum[i] - k(sum[i]> sum[j])$$
$$sum[j] \leq sum[i] + mod - k(sum[i]\leq sum[j])$$
我们得到了满足条件的 $j$ 的柿子，那么我们为了答案最优，我们就要找到其中最大的 $sum[j]$。
所以引用数据结构来优化。
因为原数组不是单调的，普通的二分查找肯定是不行的。
不难发现平衡树是满足我们的需要的，但是懒得手打，于是可以用 set。
因为 set 只有大于等于和大于，所以可以把上柿同时取反，然后枚举 $i$， 查找 $j$，就行了。
# 代码
```cpp
#include<cstdio>
#include<cctype>
#include<set>
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
LL a[N], sum[N], mod, k, n, ans = 1e18, x1, x2;
set < LL > s;
inline LL read() {
LL x = 0; int f = 1, c = getchar();
for(; !isdigit(c); c = getchar())
if(c == '-')
f = -1;
for(; isdigit(c); c = getchar())
x = x * 10 + c - 48;
return x * f;
}
int main() {
n = read(), k = read(), mod = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
if(a[i] >= mod) a[i] %= mod;
}
for(int i = 1; i <= n; i++) {
sum[i] = (1ull * sum[i - 1] + a[i]) % mod;
s.insert(-sum[i]);
}
for(int i = 1; i <= n; i++) {
x1 = *s.lower_bound(k - sum[i]);
x2 = *s.lower_bound(k - sum[i] - mod);
x1 = (sum[i] + x1) % mod;
x2 = (sum[i] + x2) % mod;
if(x1 < 0) x1 += mod;
if(x2 < 0) x2 += mod;
if(x1 >= k) ans = min(ans, x1);
if(x2 >= k) ans = min(ans, x2);
}
printf("%lld\n", ans);
return 0;
}
```