bzoj 5177: [Jsoi2013]贪心的导游

.

题意：给你一个长度为$n$的数列，$m$次询问$\max(a_i \% p) (i \in [l,r])$。
题解：主席树
建出主席树后，枚举$k$，求出$\max(a_i \% p) (i \in [l,r], a_i \in [kp, (k+1)p))$。虽然复杂度看上去不是很靠谱，但是过了。。
代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, a[1000010];
namespace chairman_tree
{
    struct tree
    {
        int c, l, r;
        tree *lc, *rc;
    } * root[1000010];
    tree *ins(tree *ori, int l, int r, int x)
    {
        tree *i = new tree(*ori);
        i->l = l;
        i->r = r;
        i->c++;
        if (l < r)
        {
            int md = l + r >> 1;
            if (x <= md)
                i->lc = ins(ori->lc, l, md, x);
            else
                i->rc = ins(ori->rc, md + 1, r, x);
        }
        return i;
    }
    void build()
    {
        root[0] = new tree;
        root[0]->c = 0;
        root[0]->lc = root[0]->rc = root[0];
        for (int i = 1; i <= n; i++)
            root[i] = ins(root[i - 1], 0, 1000, a[i]);
    }
    int get(tree *lt, tree *rt, int i, int j)
    {
        int l = rt->l, r = rt->r;
        if (rt->c - lt->c == 0)
            return -1;
        if (l == r)
            return l;
        int md = l + r >> 1;
        if (i > md)
            return get(lt->rc, rt->rc, i, j);
        else if (j <= md)
            return get(lt->lc, rt->lc, i, j);
        int hl = get(lt->rc, rt->rc, i, j);
        if (~hl)
            return hl;
        else
            return get(lt->lc, rt->lc, i, j);
    }
    int wk(const int l, const int r, const int p)
    {
        int ans = 0;
        for (int i = 0; i <= 1000; i += p)
        {
            int j = min(1000, i + p - 1);
            ans = max(ans, get(root[l - 1], root[r], i, j) % p);
        }
        return ans;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    chairman_tree::build();
    for (int i = 0; i < m; i++)
    {
        int l, r, p;
        scanf("%d%d%d", &l, &r, &p);
        l++;
        r++;
        if (l > r)
            swap(l, r);
        printf("%d\n", chairman_tree::wk(l, r, p));
    }
}