【题解】[AHOI2013] 作业 莫队+分块统计答案 luogu4396 ——quhengyi11

传送喵

题解

记数列长度为 $n$，询问数为 $q$

这题比较 $naive$的做法就是离散化颜色 (下文的颜色都指那个数列中的数，所谓不同数值也就是数不同的颜色个数) 之后，暴力跑个莫队，然后用树状数组统计答案，因为莫队是 $O(n\sqrt q)$的，转移的时候又要带个 $O(logn)$，复杂度妥妥爆了。

其实这个暴力已经很接近正解了，我们想想哪里可以优化改进

所谓莫队，它就是通过 $n\sqrt q$次单点移动区间两边的指针来离线回答询问的。

那么它本身用来转移的复杂度就是 $O(n\sqrt q)\times O(修改)$

我们再来想想询问，有些题目莫队询问是可以做到 $O(1)$的，而这题如果用树状数组维护当前的颜色信息，每次询问就是 $O(logn)$，总共是 $O(qlogn)$

所以一个呼之欲出的思路就是，我们能不能通过增加询问的复杂度来减少转移的复杂度。

差分维护颜色信息？的确修改会变成 $O(1)$，但是询问就总共 $O(nq)$了，咕咕咕。

其实我们可以直接分块搞呀。

因为是单点修改，使用分块我们的修改复杂度也是 $O(1)$的。

询问可以通过分块优化到 $O(q\sqrt n)$

然后总复杂度就是 $O(n\sqrt q+q\sqrt n)$啦，皆大欢喜。

#include<bits/stdc++.h>
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define N 300005
#define inf 1000000005
#define ls t[u].s[0]
#define rs t[u].s[1]
#define pb push_back
int n, m, block[N], sq1, b[N], a[N], belong[N], sq2;
struct node{
    int l, r, a, b, id;
    friend bool operator < (node x, node y)
    {
        return belong[x.l] != belong[y.l] ? belong[x.l] < belong[y.l] : belong[x.l] & 1 ? x.r > y.r : x.r < y.r;
    }
}t[N];
struct ques{
    int x, y;
}ans[N];
int tot, cnt[N], cnt2[N], c[N];
inline ques calc (int l, int r)
{
    ques ret = (ques) {0, 0};
    if (block[l] == block[r])
    {
        fo (i, l, r)
        {
            ret.x += c[i];
            ret.y += (bool) c[i];
        }
        return ret;
    }
    int bl = block[l] + 1, br = block[r] - 1;
    fo (i, bl, br)
    {
        ret.x += cnt[i];
        ret.y += cnt2[i];
    }
    bl = bl * sq1 - 1;
    fo (i, l, bl)
    {
        ret.x += c[i];
        ret.y += (bool) c[i];
    }
    br = (br + 1) * sq1;
    fo (i, br, r)
    {
        ret.x += c[i];
        ret.y += (bool) c[i];
    }
    return ret;
}
inline void add (int col, bool flag)
{
    if (flag)
    {
        if (!c[col]) ++cnt2[block[col]];
        ++c[col];
        ++cnt[block[col]];
    }
    else
    {
        --c[col];
        --cnt[block[col]];
        if (!c[col]) --cnt2[block[col]];
    }
}
int main ()
{
    scanf("%d %d", &n, &m);
    sq2 = std::max((int) (n / sqrt(1.0 * m * 2 / 3)), 1);
    fo (i, 1, n) belong[i] = i / sq2;
    fo (i, 1, n) {scanf("%d", &a[i]); b[i] = a[i];}
    tot = n;
    fo (i, 1, m)
    {
        scanf("%d %d %d %d", &t[i].l, &t[i].r, &t[i].a, &t[i].b);
        b[++tot] = t[i].a; b[++tot] = t[i].b;
        t[i].id = i;
    }
    std::sort(b + 1, b + tot + 1);
    tot = std::unique(b + 1, b + tot + 1) - b - 1;
    sq1 = (int) sqrt(tot);
    fo (i, 1, tot) block[i] = i / sq1;
    fo (i, 1, n) a[i] = std::lower_bound(b + 1, b + tot + 1, a[i]) - b;
    fo (i, 1, m) 
    {
        t[i].a = std::lower_bound(b + 1, b + tot + 1, t[i].a) - b;
        t[i].b = std::lower_bound(b + 1, b + tot + 1, t[i].b) - b;
    }
    std::sort(t + 1, t + m + 1);
    int L = 1, R = 0;
    fo (i, 1, m)
    {
        while (t[i].l < L) {--L; add(a[L], 1);}
        while (t[i].r > R) {++R; add(a[R], 1);}
        while (t[i].l > L) {add(a[L], 0); ++L;}
        while (t[i].r < R) {add(a[R], 0); --R;}
        ans[t[i].id] = calc(t[i].a, t[i].b);
    }
    fo (i, 1, m) printf("%d %d\n", ans[i].x, ans[i].y);
    return 0;
}