【题目 背景】

小奇总是在数学课上思考奇怪的问题。

【问题描述】

给定一个长度为 n 的数列， 以及 m 次询问， 每次给出三个数 l， r 和 P， 询问 (a[l' ] + a[l' +1] + . . . + a[r' ] ) mod P 的最小值。 其中 l 9)write(x/10); 27 int xx=x%10; 28 putchar(xx+'0'); 29 } 30 void clear(int x){ 31 ch[x][0]=ch[x][1]=fa[x]=cnt[x]=val[x]=0; 32 } 33 bool Wson(int x){ 34 return ch[fa[x]][1]==x; 35 } 36 void rotate(int x){ 37 int y=fa[x]; 38 int z=fa[y]; 39 int ws=Wson(x); 40 41 if(z)ch[z][Wson(y)]=x; 42 fa[x]=z; 43 44 ch[y][ws]=ch[x][ws^1]; 45 fa[ch[y][ws]]=y; 46 47 ch[x][ws^1]=y; 48 fa[y]=x; 49 } 50 51 void Splay(int x,int goal){ 52 while(fa[x]!=goal){ 53 int y=fa[x]; 54 if(fa[y]!=goal){ 55 if(Wson(x)==Wson(y))rotate(y); 56 else rotate(x); 57 } 58 rotate(x); 59 } 60 if(goal==0)root=x; 61 } 62 63 void Insert(int dt){ 64 if(root==0){ 65 int now=++BH; 66 root=now; 67 ch[now][0]=ch[now][1]=0; 68 val[now]=dt; fa[now]=0; cnt[now]=1; 69 return; 70 } 71 int now=root,pa=0; 72 while(1){ 73 if(val[now]==dt){ 74 cnt[now]++; Splay(now,0); return; 75 } 76 pa=now; 77 now=ch[now][val[now]=p){ 107 putchar('0'); Pn; 108 continue; 109 } 110 For(j,l,r){ 111 int tmp=(s[j]-s[l-1])%p; 112 Insert(tmp); 113 int px=Pre(); 114 fn=min(fn,tmp-px); 115 if(fn==0)break; 116 } 117 write(fn); Pn; 118 } 119 fclose(stdin); fclose(stdout); 120 return 0; 121 }