BZOJ #2639 | 矩形计算

看到这个数据范围，应该会自然而然地想到莫队。我们可以维护一个四维莫队，依次对 $x1$、$y1$、$x2$ 和 $y2$ 进行更改。

注意一个坑，每次更改任意一维后，修改会影响矩阵上的一个子矩阵而非单点，需要遍历一遍这个范围进行修改。

下面放出一张我打的草稿，应该会让你理解我的意思。

接下来就是莫队板子了，注意离散化。

▶

Code

/******************************
  @GavinCQTD / %$Time$%
  "%$Problem$%" From %$Contest$%
  # %$URL$%
  %$TimeL$% ms / %$MemoryL$% MB
******************************/
/* We all make choices, but in the end our choices make us. */

// #pragma GCC optimize(1,2,3,"Ofast","inline")
// #pragma GCC optimize("Ofast,no-stack-protector,inline,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// #define NDEBUG
// #define EXT
// #define ATCODER_LIBRARY

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <unordered_map>
using namespace std;
#ifdef EXT
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#endif
#ifdef ATCODER_LIBRARY
using namespace atcoder;
#endif
inline void pass(){return;}
inline void hold(){while(1);}
#define endl "\n"
#define mp(a,b) make_pair(a,b)
#define ct(a) while(!a.empty()) a.pop()
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define cdb cerr<<"Debug: "
#define cwn cerr<<"Warn: "
#define debug(x) cerr<<"In Line "<<__LINE__<<": "<<#x<<" = "<<x<<"\n"
#define sp(a) fixed<<setprecision(a)
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#define ll long long
#define ull unsigned long long
#define ld long double
// #define int ll
// #define _debug

int _t,n,m,q,a[205][205],bl[205],cnt[40005],ans[100005],tot=0;
struct qur{
    int x1,y1,x2,y2,id;
}qr[100005];
unordered_map <int,int> lsh;

bool cmp(qur x,qur y){
    if(bl[x.x1]!=bl[y.x1]){
        return bl[x.x1]<bl[y.x1];
    }
    else if(bl[x.y1]!=bl[y.y1]){
        return bl[x.y1]<bl[y.y1];
    }
    else if(bl[x.x2]!=bl[y.x2]){
        return bl[x.x2]<bl[y.x2];
    }
    else{
        return bl[x.y2]<bl[y.y2];
    }
}

void addl(int l,int r1,int r2,int id){
    for(int i=r1;i<=r2;i++){
        ans[id] -= cnt[a[l][i]]*cnt[a[l][i]];
        cnt[a[l][i]]++;
        ans[id] += cnt[a[l][i]]*cnt[a[l][i]];
    }
}

void addr(int l1,int l2,int r,int id){
    for(int i=l1;i<=l2;i++){
        ans[id] -= cnt[a[i][r]]*cnt[a[i][r]];
        cnt[a[i][r]]++;
        ans[id] += cnt[a[i][r]]*cnt[a[i][r]];
    }
}

void dell(int l,int r1,int r2,int id){
    for(int i=r1;i<=r2;i++){
        ans[id] -= cnt[a[l][i]]*cnt[a[l][i]];
        cnt[a[l][i]]--;
        ans[id] += cnt[a[l][i]]*cnt[a[l][i]];
    }
}

void delr(int l1,int l2,int r,int id){
    for(int i=l1;i<=l2;i++){
        ans[id] -= cnt[a[i][r]]*cnt[a[i][r]];
        cnt[a[i][r]]--;
        ans[id] += cnt[a[i][r]]*cnt[a[i][r]];
    }
}

void solve(int testID){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> a[i][j];
            if(!lsh[a[i][j]]){
                lsh[a[i][j]] = ++tot;
            }
            a[i][j] = lsh[a[i][j]];
        }
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        int l1,r1,l2,r2;
        cin >> l1 >> r1 >> l2 >> r2;
        qr[i] = (qur){min(l1,l2),min(r1,r2),max(l1,l2),max(r1,r2),i};
    }
    int block=sqrt(n);
    for(int i=1;i<=n;i++){
        bl[i] = (i-1)/block+1;
    }
    sort(qr+1,qr+q+1,cmp);
    int l1=1,r1=1,l2=0,r2=0;
    for(int i=1;i<=q;i++){
        ans[qr[i].id] = ans[qr[i-1].id];
        while(l1<qr[i].x1){
            dell(l1,r1,r2,qr[i].id);
            l1++;
        }
        while(l1>qr[i].x1){
            l1--;
            addl(l1,r1,r2,qr[i].id);
        }
        while(l2<qr[i].x2){
            l2++;
            addl(l2,r1,r2,qr[i].id);
        }
        while(l2>qr[i].x2){
            dell(l2,r1,r2,qr[i].id);
            l2--;
        }
        while(r1<qr[i].y1){
            delr(l1,l2,r1,qr[i].id);
            r1++;
        }
        while(r1>qr[i].y1){
            r1--;
            addr(l1,l2,r1,qr[i].id);
        }
        while(r2<qr[i].y2){
            r2++;
            addr(l1,l2,r2,qr[i].id);
        }
        while(r2>qr[i].y2){
            delr(l1,l2,r2,qr[i].id);
            r2--;
        }
    }
    for(int i=1;i<=q;i++){
        cout << ans[i] << "\n";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    // freopen("PublicDebug.debug", "w", stderr);

    // cout << sp();
    // cerr << sp();

    _t = 1;
    // cin >> _t;

    for(int ran=0;ran<_t;ran++) solve(ran);

    fflush(stdout);
    return 0;
}