[题解] [JSOI2013] 贪心的导游

题解

题解

分治不会, 但是会分块(滑稽)

设 (f[i][j]) 为第 (i) 块, (0 o j) 中最大的是多少

设 (g[i][j]) 为第 (i) 块, 膜 (j) 最大的是多少

把值域分为 (frac{S}{j}) 块, (S) 为值域大小, 对于每一块中膜 (j) 的最大值取一下 (max) , 最后因为最后一块不一定完整, 所以在 (S) 那里也要取一下

然后查询直接分块查就行

复杂度的话, (O(1000*sqrt n))

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
const int N = 1e6 + 5;
const int S = 1e3 + 5; 
using namespace std;

int n, m, gap, bl[N], f[S][S], g[S][S], a[N]; 

template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}

int solve(int l, int r, int mod)
{
    int res = 0;
    for(int i = l; i <= min(bl[l] * gap, r); i++)
	res = max(res, a[i] % mod);
    if(bl[l] != bl[r])
	for(int i = max(1, (bl[r] - 1) * gap + 1); i <= r; i++)
	    res = max(res, a[i] % mod);
    for(int i = bl[l] + 1; i <= bl[r] - 1; i++)
	res = max(res, g[i][mod]);
    return res; 
}

int main()
{
    n = read <int> (), m = read <int> (), gap = sqrt(n);
    for(int i = 1; i <= n; i++)
	bl[i] = (i - 1) / gap + 1, f[bl[i]][a[i] = read <int> ()] = a[i];
    for(int i = 1; i <= bl[n]; i++)
	for(int j = 1; j <= 1000; j++)
	    f[i][j] = max(f[i][j], f[i][j - 1]);
    for(int i = 1; i <= bl[n]; i++)
	for(int j = 1; j <= 1000; j++)
	{
	    for(int k = 1; k * j - 1 <= 1000; k++)
		g[i][j] = max(g[i][j], f[i][k * j - 1] % j);
	    g[i][j] = max(g[i][j], f[i][1000] % j); 
	}
    int l, r, p; 
    while(m--)
    {
	l = read <int> () + 1, r = read <int> () + 1, p = read <int> (); 
	printf("%d
", solve(l, r, p)); 
    }
    return 0; 
}

BZOJ 搞了一下之后码风就不对了, 见谅