题解 P4396 【[AHOI2013]作业】

· · 题解

大家好， 我非常喜欢暴力数据结构， 于是就用分块A了此题

这里提供的是支持在线的纯分块做法 ， 而不是主流的莫队做法

具体做法是先对数列分块， 再对值域分块， 维护三个数组cnt1, cnt2, cnt3

我偏要反着放

显然这个预处理的时间复杂度是n sqrt n 的（具体的复杂度在程序的注释中有写）

然后对于询问两点在相邻数列块的时候直接暴力求， 否则的话先扫一遍两遍的散块（数列块） 统计一下符合要求的颜色个数和其他信息（这里可以开一些临时数组来完成答案的统计， 具体实现见代码）。

然后我们看看整块怎样处理：

如果上下界在相邻的值域块里我们暴力扫一遍值域块就能得到答案了 ， 否则我们可以先扫一下上下两个散块（值域块）， 然后再扫一下中间的整块（值域块）， 统计一下答案就可以啦qwqwq（统计答案的方法一看就会， 各位神仙直接看代码就好了， 小蒟蒻这里就不啰嗦了试图掩盖懒的事实）

具体实现代码里都有注释， 如果有什么疑问的话私信小蒟蒻就好

预处理复杂度是n sqrt(n), 单次查询的复杂度是sqrt，唯一的缺点就是常数略大， 如果想不开O2过最后一个点可能要卡卡常， 这里为了便于理解就把便（chang）于（shu）理（ju）解（da）的版本放上来啦。

那么代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath> 
#include <algorithm>
#define maxn 100010
#define maxs 400
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, low, high;
int sq1, sq2;
int a[maxn], z[maxn], b1[maxn], b2[maxn], cnt1[maxs][maxs], cnt2[maxs][maxn];
unsigned short cnt3[maxs][maxs][maxs];
int col[maxn], cn[maxn], blkcol[maxn];

inline void in(int &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
} 

void query(int x, int y, int k1, int k2) {
    if(b1[x] == b1[y] || b1[y] == b1[x]+1) { //x和y在同一个块里或在相邻的块里 
        int ans1 = 0, ans2 = 0;
        FOR(i, x, y) {
            ++col[a[i]];
            if(a[i] >= k1 && a[i] <= k2 && col[a[i]] == 1)
              ++ans2;
            if(a[i] >= k1 && a[i] <= k2)
              ++ans1;
        }
        printf("%d %d\n", ans1, ans2);
        FOR(i, x, y) 
          --col[a[i]];
        return;
    }

    FOR(i, x, min(y, b1[x]*sq1)) { //x, y 所在的块不相邻 
        ++col[a[i]]; //单个颜色的个数 
        ++blkcol[b2[a[i]]]; //值域块内颜色的个数 
        if(col[a[i]]+cnt2[b1[y]-1][a[i]]-cnt2[b1[x]][a[i]] == 1)
          ++cn[b2[a[i]]]; //统计颜色种类数 
    }
    FOR(i, (b1[y]-1)*sq1+1, y) {
        ++col[a[i]];
        ++blkcol[b2[a[i]]];
        if(col[a[i]]+cnt2[b1[y]-1][a[i]]-cnt2[b1[x]][a[i]] == 1)
          ++cn[b2[a[i]]]; 
    } 

    if(b2[k1] == b2[k2] || b2[k1]+1 == b2[k2]) { //上下界在同一个值域块里或上下界在相邻值域块里 
        int ans1 = 0, ans2 = 0;
        FOR(i, k1, k2) {  //直接枚举值域 
            if(col[i]+cnt2[b1[y]-1][i]-cnt2[b1[x]][i] > 0) 
              ++ans2;
            ans1 += col[i]+cnt2[b1[y]-1][i]-cnt2[b1[x]][i]; 
        }
        printf("%d %d\n", ans1, ans2);
    }
    else { //x 和y的块不相邻且上下界值域块不相邻 
        int ans1 = 0, ans2 = 0;
        FOR(i, k1, b2[k1]*sq2) {
            if(col[i]+cnt2[b1[y]-1][i]-cnt2[b1[x]][i] > 0) {
                ++ans2;
            }

            ans1 += col[i]+cnt2[b1[y]-1][i]-cnt2[b1[x]][i];
        }
        FOR(i, (b2[k2]-1)*sq2+1, k2) {
            if(col[i]+cnt2[b1[y]-1][i]-cnt2[b1[x]][i] > 0) {
                 ++ans2;
            }

            ans1 += col[i]+cnt2[b1[y]-1][i]-cnt2[b1[x]][i];
        }

        FOR(i, b2[k1]+1, b2[k2]-1) { //整值域块 
            ans1 += blkcol[i]+cnt1[b1[y]-1][i]-cnt1[b1[x]][i]; //统计总个数 
            ans2 += cn[i]+cnt3[b1[x]+1][b1[y]-1][i]; //种类数 
        }
        printf("%d %d\n", ans1, ans2);
    }

    FOR(i, x, min(y, b1[x]*sq1)) { //消除影响 
        --col[a[i]]; 
        --blkcol[b2[a[i]]]; 
        if(col[a[i]]+cnt2[b1[y]-1][a[i]]-cnt2[b1[x]][a[i]] == 0)
          --cn[b2[a[i]]]; 
    }
    FOR(i, (b1[y]-1)*sq1+1, y) {
        --col[a[i]];
        --blkcol[b2[a[i]]];
        if(col[a[i]]+cnt2[b1[y]-1][a[i]]-cnt2[b1[x]][a[i]] == 0)
          --cn[b2[a[i]]]; 
    } 
}

int main() {
    //cnt3(i,j,k)表示第i到第j个块中第k个值域块的数的种类数 
    //cnt2(i,j)表示前i个块中j这个数（离散后)的个数
    //cnt1(i,j)表示前i个块中第j个值域块中数的个数 
    in(n), in(m);
    sq1 = sqrt(n);
    FOR(i, 1, n)
      in(a[i]), z[++z[0]] = a[i];
    sort(z+1, z+z[0]+1);
    z[0] = unique(z+1, z+z[0]+1)-z-1;
    sq2 = sqrt(z[0]);
    FOR(i, 1, z[0])
      b2[i] = (i-1)/sq2+1;
    FOR(i, 1, n) {
        a[i] = lower_bound(z+1, z+z[0]+1, a[i])-z; //离散 
        b1[i] = (i-1)/sq1+1;
        ++cnt1[b1[i]][b2[a[i]]];
        ++cnt2[b1[i]][a[i]];
    }
    FOR(i, 1, b1[n]) {
        FOR(j, 1, b2[z[0]])  //处理cnt1的前缀和 总复杂度On 
          cnt1[i][j] += cnt1[i-1][j];
        FOR(j, 1, z[0]) //处理cnt2的前缀和  总复杂度O(n sqrt(n)) 
          cnt2[i][j] += cnt2[i-1][j];

        FOR(j, i, b1[n]) { //处理出cnt3的值 总复杂度O(n sqrt(n)) 
            FOR(k, (j-1)*sq1+1, min(n, j*sq1)) {
                ++col[a[k]];
                if(col[a[k]] == 1) {
                     ++cnt3[i][j][b2[a[k]]];
                }
            }
        }

        FOR(j, i, b1[n])
          FOR(k, 1, b2[z[0]])
            cnt3[i][j][k] += cnt3[i][j-1][k];

        FOR(j, i, b1[n]) { //消除影响 
            FOR(k, (j-1)*sq1+1, min(n, j*sq1)) {
                --col[a[k]];
            }
        }
    }

    FOR(i, 1, m) {
        in(x), in(y), in(low), in(high);
        if(low < z[1] && high < z[1])  { //几种特殊情况的判定
            puts("0 0");
            continue;
        } 
        if(low > z[z[0]])  {
            puts("0 0");
            continue;
        }
        low = lower_bound(z+1, z+z[0]+1, low)-z;
        high = upper_bound(z+1, z+z[0]+1, high)-z-1;  
        if(low == high+1) {
            puts("0 0");
            continue;
        }
        query(x, y, low, high); 
    }
}

完结撒花qwqwq