小奇的数列

题目描述 【题目背景】 小奇总是在数学课上思考奇怪的问题。 【问题描述】 给定一个长度为n的数列，以及m次询问，每次给出三个数l，r和P，询问 (a[l’] + a[l’+1] + … + a[r’]) mod P的最小值。 其中l <= l’ <= r’ <= r。 即模意义下的区间子串和最小值。 【输入格式】 第一行包含两个正整数n和m，表示数列的长度和询问的个数。
第二行为n个整数，为a[1]…a[n]。
接下来m行，每行三个数l，r和P，代表一次询问。 【输出格式】 对于每次询问，输出一行一个整数表示要求的结果 【样例输入】 4 2 8 15 9 9 1 3 10 1 4 17 【样例输出】 2 1 【数据范围】 对于20%的数据 n<=100，m<=100，p<=200 对于40%的数据 n<=200，m<=1000，p<=500 对于70%的数据 n<=100000，m<=10000，p<=200 对于100%的数据 n<=500000，m<=10000，p<=500，1<=a[i]<=10^9

题目分析__(骗分思路 )

维护出前缀和，输入L和R后，枚举l，r，找出[L,R】字串的最小值，不加优化过50，加上一个小优化90；
小优化：如果ans==0了，就退出枚举，因为答案要对P取模，而一个数对P取模的最小值就是0，说明已经找到最优解，就不用再继续枚举了！

友情提示：

竞赛十年功

不开long long见祖宗

至于正解要用平衡树做，会继续更新。

Code:

#include using namespace std; #define ll long long #define maxn 500010 ll n,m,a[maxn],w[maxn]; inline ll read_(){ ll x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } return x*f; } inline void clean_(){ memset(a,0,sizeof(a)); memset(w,0,sizeof(w)); } inline void init_(){ freopen("2.txt","r",stdin); } inline void readda_(){ clean_(); n=read_();m=read_(); for(ll i=1;i<=n;i++){ a[i]=read_(); w[i]=w[i-1]+a[i]; } for(ll i=1;i<=m;i++){ ll ans=99999999999999999; ll l=read_(),r=read_(),p=read_(); for(ll j=l;j<=r;j++){ if(ans==0) break; for(ll k=j;k<=r;k++){ ll px=(w[k]-w[j-1])%p; ans=min(ans,px); if(ans==0) break; } } printf("%lld ",ans); } } inline void work_(){ } int main(){ init_(); readda_(); //work_(); return 0; }