题解 P1956 【Sum_NOI导刊2009提高（5）】

数据水炸的一道题

以至于我拿一个卡时的暴力过掉了还拿了rk1???

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[200000],a[200000],ans=1e9+7,kkk=0,n,k,p;
int getin()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x;
}
int rem(int a,int b)
{
	a-=b;
	if(a<0)a+=p;
	return a;
} 
int main()
{
	n=getin(),k=getin(),p=getin();
	for(int i=1;i<=n;i++)a[i]=getin()%p,s[i]=(s[i-1]+a[i])%p;
	for(int i=0;i<n&&kkk<=4500000;i++)
		for(int j=i+1;j<=n;j++)
		{
			int d=rem(s[j],s[i]);
			if(d>=k&&d<ans)ans=d;
			kkk++;
		}
	cout<<ans<<endl;
} 
```
最终版本的卡时~~肯定有大爷能卡进100ms~~

还是来说(可能的~~不过我觉得补星~~)正解

首先前缀和一下顺便取模

然后可以发现我们要求的就是$s_j-s_i$或者$s_j-s_i+p$(以下省略后者，式子肯定都会化,取个min就行了)

因为要不小于k，所以减去一个k变成

$min\{s_j-s_i-k|s_j-s_i-k>=0,j>i\}$

假设已知$s_j$,那么就是要找一个最大的$s_i$使$s_j>=s_i+k$

这个东西看起来就是一个前驱的样子了

所以可以二叉查找树解决

为什么不用平衡树？

因为~~不好写~~随机数据显然二叉查找树的复杂度可以保证~~不然暴力怎么能过~~

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ch[200000][2],f[200000],rt,id,w[200000]={1e9+7},m,opt,x,ans=1e9+7,s[200000],n,k,p;
int prep(int x)
{
	int lst=0,o=rt;
	while(o)
	{
		if(x>w[o])lst=o,o=ch[o][1];
		else o=ch[o][0];
	} 
	return w[lst];
}
void ins(int x)
{
	if(!rt){w[++id]=x,rt=id;return;}
	int o=rt,lst;
	while(o)
	{
		lst=o;
		if(x>w[o])o=ch[o][1];
		else if(x<w[o])o=ch[o][0];
		else break;
	}
	if(!o)
	{
		w[o=++id]=x;
		f[id]=lst,ch[lst][x>w[lst]]=id;
	}
}
int getin()
{
	int x=0,f=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x*f;
}
int main()
{
	n=getin(),k=getin(),p=getin();
	for(int i=1;i<=n;i++)s[i]=(s[i-1]+getin())%p;
	ins(s[1]+k);
	for(int i=2;i<=n;i++)
	{
		ans=min(ans,(s[i]-min(prep(s[i]+1),prep(s[i]+p+1))+k+p)%p);
		ins(s[i]+k);
	}
	cout<<ans<<endl;
}
```

正在渲染内容...