JZOJ 1306. Sum

题目大意

有一个序列 a a a长度为 n n n，要找到一段区间的和模 p p p大于等于 k k k，问这些符合条件的和的最小值。

解题思路

设 s i = ∑ j = 1 i a j m o d    p s_i=\sum_{j=1}^i{a_j}\mod p si​=∑j=1i​aj​modp。

暴力不说了，直接枚举两个端点。

我们发现一个问题，这里要用到模运算，不能用线段树较好的维护。

从 j + 1 j+1 j+1到 i i i的所有数的和是 s i − s j m o d    p s_i-s_j\mod p si​−sj​modp。

上面这个式子，有两种情况。

1. s i ≥ s j s_i\ge s_j si​≥sj​，上面式子变成 s i − s j m o d    p s_i-s_j\mod p si​−sj​modp，要使这个式子大于等于 k k k， s j s_j sj​最大取到 s i − k s_i-k si​−k，原因： s i − s j = s i − ( s i − k ) = k ≥ k s_i-s_j=s_i-(s_i-k)=k\ge k si​−sj​=si​−(si​−k)=k≥k所以取到 s i − k s_i-k si​−k是最大了的。因为这里要使 s i − s j s_i-s_j si​−sj​尽量小，所以 s j s_j sj​要尽量大。所以要找到一个最靠近（小于等于） s j s_j sj​的数。
2. s i < s j s_i<s_j si​<sj​，上面式子变成 s i − s j + p m o d    p s_i-s_j+p\mod p si​−sj​+pmodp，要使它大于等于 k k k， s j s_j sj​最大取到 s i + p − k s_i+p-k si​+p−k，原因同理。

如何维护最靠近的数呢？

其实就是一个数的前驱，用权值线段树或平衡树维护。

总结

以后遇到取模的题目，大多是分类讨论。

code

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=100005,inf=1000000000;
int k,p,a[N],s[N],ans=inf;
struct segmenttree{
	int val,l,r;
}tree[N<<5];
int cnt=1;
void add(int k,int l,int r,int x){
	if (l==r){
		tree[k].val=l;
		return;
	}
	int mid=(l+r)/2;
	if (x<=mid){
		if (tree[k].l==0) tree[k].l=++cnt;
		add(tree[k].l,l,mid,x);
	}
	else{
		if (tree[k].r==0) tree[k].r=++cnt;
		add(tree[k].r,mid+1,r,x);
	}
	tree[k].val=min(tree[tree[k].l].val,tree[tree[k].r].val);
}
int query(int k,int l,int r){
	if (l==r) return l;
	int mid=(l+r)/2;
	if (tree[k].r) return query(tree[k].r,mid+1,r);
	if (tree[k].l) return query(tree[k].l,l,mid);
	return 0;
}
int find(int k,int l,int r,int x){
	if (x>r){
		if (tree[k].val) return query(k,l,r);
		return 0;
	}
	int mid=(l+r)/2;
	if (x>mid&&tree[k].r) return find(tree[k].r,mid+1,r,x);
	if (tree[k].l) return find(tree[k].l,l,mid,x);
	return 0;
}
int main(){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	int rt=0;
	scanf("%d%d%d",&n,&k,&p);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]%=p;
	for (int i=0;i<=(n<<5);i++) tree[i].val=inf;
	for (int i=1;i<=n;i++) s[i]=(s[i-1]+a[i])%p;
	for (int i=1;i<=n;i++){
		int u=find(1,0,p,s[i]-k);
		if (u&&s[i]-u>=k) ans=min(ans,s[i]-u);
		u=find(1,0,p,s[i]+p-k);
		if (u&&s[i]+p-u>=k) ans=min(ans,s[i]+p-u);
		add(1,0,p,s[i]);
	}
	printf("%d",ans);
}