模拟赛20181031 雅礼 养花

#include<bits/stdc++.h>
using namespace std;
int n = 0 , m = 0 , bound = 1000;
int val[100005];
int tot[100005];
int ans[105][100005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;	
	for(int i = 1;i <= n;++ i) cin >> val[i];
	int num = (n - 1) / bound + 1;
	for(int i = 1;i <= num;++ i)
	{
		memset(tot,0,sizeof(tot));
		int l = (i - 1) * bound + 1 , r = min(i * bound , n);
		for(int j = l;j <= r;++ j) tot[val[j]] = val[j];
		for(int j = 1;j <= 100000;++ j) tot[j] = max(tot[j] , tot[j - 1]);
		for(int j = 1;j <= 100000;++ j)
		{
			for(int k = 0;k <= 100000;k += j)
			{
				ans[i][j] = max(ans[i][j] , tot[min(k + j - 1 , 100000)] - k);
			}
		}
	}
	for(int i = 1;i <= m;++ i)
	{
		int l = 0 , r = 0 , k = 0 , res = 0;
		cin >> l >> r >> k;
		int numl = (l - 1) / bound + 1 , numr = (r - 1) / bound + 1;
		for(int j = numl + 1;j <= numr - 1;++ j)
		{
			res = max(res , ans[j][k]);
		}
		for(int j = l;j <= min(numl * bound , r);++ j)
		{
			res = max(res , val[j] % k);
		}
		for(int j = max((numr - 1) * bound + 1 , l);j <= r;++ j)
		{
			res = max(res , val[j] % k);
		}
		cout << res << endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n = 0 , m = 0 , bound = 1000;
array<int , 100100> val , tot;
array<array<int , 105> , 100100> ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;	
	for(int i = 1;i <= n;++ i) cin >> val[i];
	int num = (n - 1) / bound + 1;
	for(int i = 1;i <= num;++ i)
	{
		tot.fill(0);
		int l = (i - 1) * bound + 1 , r = min(i * bound , n);
		for(int j = l;j <= r;++ j) tot[val[j]] = val[j];
		for(int j = 1;j <= 100000;++ j) tot[j] = max(tot[j] , tot[j - 1]);
		for(int j = 1;j <= 100000;++ j)
		{
			for(int k = 0;k <= 100000;k += j)
			{
				ans[i][j] = max(ans[i][j] , tot[min(k + j - 1 , 100000)] - k);
			}
		}
	}
	for(int i = 1;i <= m;++ i)
	{
		int l = 0 , r = 0 , k = 0 , res = 0;
		cin >> l >> r >> k;
		int numl = (l - 1) / bound + 1 , numr = (r - 1) / bound + 1;
		for(int j = numl + 1;j <= numr - 1;++ j)
		{
			res = max(res , ans[j][k]);
		}
		for(int j = l;j <= min(numl * bound , r);++ j)
		{
			res = max(res , val[j] % k);
		}
		for(int j = max((numr - 1) * bound + 1 , l);j <= r;++ j)
		{
			res = max(res , val[j] % k);
		}
		cout << res << endl;
	}
	return 0;
}

完全一样，为什么array会爆零