「NOIP模拟赛」小奇的数列
「题目背景」
小奇总是在数学课上思考奇怪的问题。
「问题描述」
给定一个长度为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
题解
对于20%的数据，最暴力的做法，在区间内枚举子串，暴力求和取模，最后得出最小值，复杂度m*n^3
对于40%的数据，算法1的区间求和改用前缀和相减，复杂度m*n^2
接下来，思考一下抽屉原理，如果询问的区间长度大等p的话，一定有两个前缀和相减等于0，那么直接输出0即可
对于70%的数据，把所有长度大等p的区间特判，其余暴力，复杂度m*p^2
考虑生日悖论，数列如果是随机生成的，找到2个前缀和相同的就返回0，期望复杂度为m*p
由于第10组数据是随机生成的，所以算法3可以通过8个测试点
对于100%的数据，使用平衡树来寻找某个数的前驱，复杂度为m*p*logp（可能高于noip难度），需要手写treap，splay或替罪羊树等。set由于常数较大，实测和暴力结果一样。
|
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 76 77 78 79 80 81 82 83 84 85 |
#include<set> #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,rt,cnt,MN; int a[500005]; ll s[500005]; struct treap{ int rnd,l,r,val; }t[1005]; void rturn(int &k) { int tmp=t[k].l;t[k].l=t[tmp].r;t[tmp].r=k;k=tmp; } void lturn(int &k) { int tmp=t[k].r;t[k].r=t[tmp].l;t[tmp].l=k;k=tmp; } void insert(int &k,int x) { if(k==0) { k=++cnt; t[k].val=x;t[k].rnd=rand(); t[k].l=t[k].r=0; return; } if(t[k].val==x)return; else if(x>t[k].val) { insert(t[k].r,x); if(t[t[k].r].rnd<t[k].rnd)lturn(k); } else { insert(t[k].l,x); if(t[t[k].l].rnd<t[k].rnd)rturn(k); } } void query(int k,int val) { if(!k)return; if(t[k].val==val){MN=0;return;} if(t[k].val>val)query(t[k].l,val); else { MN=min(MN,val-t[k].val); query(t[k].r,val); } } int main() { freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]; while(m--) { int l=read(),r=read(),p=read(),ans=p; if(r-l+1>=p){puts("0");continue;} rt=cnt=0;insert(rt,0); for(int j=l;j<=r;j++) { int tmp=(s[j]-s[l-1])%p; MN=inf;query(rt,tmp); insert(rt,tmp); ans=min(ans,MN); if(ans==0)break; } printf("%d\n",ans); } return 0; } |
OI 课件=>
其实这题用树状数组维护权值直接艹过去就好了……
tyvj,vijos……找以下就行了。
这道题在哪交呢？
没地方交。。
那请问有没有数据呢..
随便拍拍呗
可以尝试离线黑科技。。方便很多呢2333
您是不甘心pkusc这题被暴力艹了么。。。
丧心病狂
0.0。。。我当时正解过不去。。。最终怒写暴力