OI题解 - array(NOIP+模拟) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - array(NOIP+模拟)

发表于 分类于 Valine：

#然而还是没能日更博客#

# 题目

给出一个长度为 $n$ 的正整数数列 $A$，回答 $m$ 次询问：

每次询问给定整数 $L,R,P$，求区间 $[L,R]$ 中的一个子区间 $[L’,R’]$，使得 $\left(\sum_{i=L’}^{R’}A_i\right)\bmod P$ 最小，输出该最小值。

数据规模：$1\le n,m\le 10^4$；$1\le P\le3\times10^4$；$0\le A_i\le 10^9$。

# 解析

首先可以想到的是暴力枚举 $[L’,R’]$，然后用前缀和求出区间和，取模后取 min 即可。复杂度 $O(n^2m)$

然后考虑只枚举一个端点，另一个端点直接计算（也是较常规的套路了），这里考虑枚举右端点（左端点也可以）。
记前缀和为 $S$，那么对于每一个 $R’$，要求出一个 $L’$ 使得 $(S_{R’}-S_{L’})\bmod P$ 最小。麻烦在于这个 $\bmod P$，但是稍加思索可以发现一个结论：

使得 $(S_{R’}-S_{L’})\bmod P$ 最小的 $L’$ 一定满足 $S_{R’}\bmod P\ge S_{L’}\bmod P$

jpg1

> 证明

如果 $S_{R’}\bmod P<S_{L’}\bmod P$，那么 $S_{R’}\bmod P<(S_{R’}-S_{L’})\bmod P$，看上面右图就可以发现了。那么 $L’$ 如果取 $R’$ 会更优一些。

那就方便了，我们相当于要找不超过 $(S_{R’}\bmod P)$ 的最大的 $(S_{L’}\bmod P)$，这个可以 $R’$ 从左到右扫一遍，用平衡树来维护前驱。

# 源代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e4;

struct NODE{
	int key,fix;
	NODE *ch[2];
};
struct TREAP{
	NODE nod[N+10],*rt,*ncnt,*NIL;
	void Init(){rt=ncnt=NIL=nod;}
	NODE* NewNode(int key){
		ncnt++;
		ncnt->key=key;ncnt->fix=rand();
		ncnt->ch[0]=ncnt->ch[1]=NIL;
		return ncnt;
	}
	void Rotate(NODE *&u,int d){
		NODE *tmp=u->ch[!d];
		u->ch[!d]=tmp->ch[d];
		tmp->ch[d]=u;
		u=tmp;
	}
	void Insert(NODE *&u,int key){
		if(u==NIL) u=NewNode(key);
		if(u->key==key) return;
		if(key<u->key){
			Insert(u->ch[0],key);
			if(u->fix>u->ch[0]->fix)
				Rotate(u,1);
		}
		else{
			Insert(u->ch[1],key);
			if(u->fix>u->ch[1]->fix)
				Rotate(u,0);
		}
	}
	int Query(NODE *u,int key){
		if(u==NIL) return (1<<29);
		if(u->key==key) return 0;
		if(u->key>key) return Query(u->ch[0],key);
		else return min(Query(u->ch[1],key),key-u->key);
	}
};
TREAP Tr;

int n,m;
long long sum[N+3];

int main(){
	freopen("array.in","r",stdin);
	freopen("array.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int num;scanf("%d",&num);
		sum[i]=sum[i-1]+num;
	}
	while(m--){
		int le,ri,P;scanf("%d%d%d",&le,&ri,&P);
		if(ri-le+1>=P){printf("0\n");continue;}
		Tr.Init();Tr.Insert(Tr.rt,0);
		int ans=P;
		for(int i=le;i<=ri;i++){
			int cur=int((sum[i]-sum[le-1])%P);
			ans=min(ans,Tr.Query(Tr.rt,cur));
			Tr.Insert(Tr.rt,cur);
		}
		printf("%d\n",ans);
	}
	return 0;
}

The End

Thanks for reading!

-“如你所愿”