考试拿两年前的雅礼集训题考，自闭了。
mdnmd，这就全都不会做呗。
desprition
小 C 在家种了 (n) 盆花, 每盆花有一个艳丽度 (a_i). 在接下来的 m 天中, 每天早晨他会从一段编号连续的花中选择一盆摆放在客厅, 并在晚上放回 同时每天有特定的光
照强度 (k_i), 如果这一天里摆放在客厅的花艳丽度为 (x) , 则他能获得的喜悦度为 (x mod k_i). 他希望知道, 每一天他能获得的最大喜悦度是多少.
Input Format
数据第一行包含两个正整数 (n), $ m$ . 接下来一行 (n) 个正整数, 第 (i) 个数 (a_i) 表示第 (i) 盆花的艳丽度.
接下来 (m) 行, 每行三个正整数 (l_i) (r_i) $ k_i$, 表示选花区间和光照强度
Output Format
输出 m 行, 每行一个整数, 表示最大喜悦度
Constraints
对于 20% 的数据, (n, m ≤ 4000).
对于 40% 的数据, (n, m ≤ 50000).
对于另外 20% 的数据, (a_i ≤ 300).
对于 100% 的数据, (n, m, a_i , k_i ≤ 10^5)
sloution
讲个笑话，正解是分块。
我们可以考虑预处理出对于每个模数，每个块的答案。
这个预处理大概可以做到 (O(n + kln k))
我们要求的是 形如 ([ak,(a+1)k-1]) 这一段区间的最大值 减去 (ak) 的结果。
那么我们就可以枚举每个 (ak) ,然后算出在这个答案。
直接暴力枚举的话，复杂度还是比较高，所以求一下前缀最大值就可以。
询问的复杂度是 (O(ms)) 的，取 (s = sqrt{kln k}) 是达到最优复杂度 (n sqrt{kln k})
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
const int N = 1e5+10;
int n,m,block,l,r,w;
int sum[1001][N],tong[N],a[N];
using namespace std;
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void YYCH()
{
for(int i = 1; i <= (n-1)/block+1; i++)
{
memset(tong,0,sizeof(tong));
for(int j = (i-1) * block + 1; j <= min(i * block, n); j++) tong[a[j]] = a[j];
for(int j = 1; j <= 100000; j++) tong[j] = max(tong[j],tong[j-1]);//求前缀最大值
for(int j = 1; j <= 100000; j++)//枚举每个模数
{
for(int k = 0; k <= 100000; k += j)//枚举每个 ak
{
sum[i][j] = max(sum[i][j],tong[min(k+j-1,100000)]-k);//ak - (a+1)k-1 的最大值
}
}
}
}
int query(int l,int r,int w)//正常的分块询问
{
int ans = 0;
int fx = (l-1) / block + 1, fy = (r-1) / block + 1;
for(int i = l; i <= min(fx * block, r); i++) ans = max(ans,a[i] % w);
for(int i = fx+1; i <= fy-1; i++) ans = max(ans,sum[i][w]);
for(int i = max((fy-1) * block + 1,l); i <= r; i++) ans = max(ans,a[i] % w);
return ans;
}
int main()
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
n = read(); m = read(); block = 1000;
for(int i = 1; i <= n; i++) a[i] = read();
YYCH();
for(int i = 1; i <= m; i++)
{
l = read(); r = read(); w = read();
printf("%d
",query(l,r,w));
}
fclose(stdin); fclose(stdout);
return 0;
}