<法一>二维莫队，对n和m分别分块后，对块从上到下从左到右依次编号，询问以左上角所在块编号为第一关键字，以右下角标号为第二关键字排序，转移时非常厉害。

O(q*n*sqrt(n))。

#include
     
      #include
      
       #include
       
        using namespace std;#define N 201#define M 100001struct LiSan{int p,v;}t[N*N];bool operator < (const LiSan &a,const LiSan &b){return a.v
        
         Q[i].x2) swap(Q[i].x1,Q[i].x2);        if(Q[i].y1>Q[i].y2) swap(Q[i].y1,Q[i].y2);        Q[i].p=i;      }    sort(Q+1,Q+1+q);    for(int i=Q[1].x1;i<=Q[1].x2;++i)      for(int j=Q[1].y1;j<=Q[1].y2;++j)        Insert(i,j);    anss[Q[1].p]=ans;    for(int i=2;i<=q;++i)      {        trans(Q[i-1],Q[i]);        anss[Q[i].p]=ans;      }    for(int i=1;i<=q;++i)      printf("%d\n",anss[i]);    return 0;}
        
       
      
     

<法二>二维分块，分块在矩阵中的扩展，预处理前缀矩阵每个数出现的次数，以及所有“子矩块”的答案。询问的时候整块的部分直接获取，零散的部分暴力转移。TLE。

复杂度O(n^2+q)*n*sqrt(n)，常数较大。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int f,C;inline void R(int &x){    C=0;f=1;    for(;C<'0'||C>'9';C=getchar())if(C=='-')f=-1;    for(x=0;C>='0'&&C<='9';C=getchar())(x*=10)+=(C-'0');    x*=f;}inline void P(int x){    if(x<10)putchar(x+'0');    else{P(x/10);putchar(x%10+'0');}}#define N 202#define BN 17int n,m,nm;struct Point{int x,y;}num[N][N];inline bool operator == (const Point &a,const Point &b){return a.x==b.x && a.y==b.y;}struct LiSan{int p,v;}t[N*N];inline bool operator < (const LiSan &a,const LiSan &b){return a.v
          
           =X1 && Y2>=Y1)) return 0;// int a[20][20]; static int* b=&sumv[0][0][0]; int *x=b+haha[X2]+hehe[Y2]+v; int *y=b+haha[X1-1]+hehe[Y2]+v; int *z=b+haha[X2]+hehe[Y1-1]+v; int *l=b+haha[X1-1]+hehe[Y1-1]+v;// if(*z!=sumv[X2][Y1-1][v])puts("jhsdhe");// if(*(sumv+x))!=sumv[X2][Y2][v])puts("BaoJingLa"); return *x-*y-*z+*l;}void Init_Ans(){ for(int i=1;i<=sun;++i) for(int j=1;j<=sum;++j) for(int k=i;k<=sun;++k) for(int l=j;l<=sum;++l) { anss[i][j][k][l]=anss[i][j][k-1][l]; for(int o=j;o<=l;++o) for(int p=ln[k];p<=rn[k];++p) for(int q=lm[o];q<=rm[o];++q) { anss[i][j][k][l]+=((Calc(i,j,k-1,l,a[p][q])+T[a[p][q]])<<1|1); ++T[a[p][q]]; } for(int o=j;o<=l;++o) for(int p=ln[k];p<=rn[k];++p) for(int q=lm[o];q<=rm[o];++q) --T[a[p][q]]; }}int q;int main(){// freopen("bzoj2639.in","r",stdin);// freopen("bzoj2639.out","w",stdout); R(n); R(m); nm=n*m; for(int i(1);i
           
            X2) swap(X1,X2); if(Y1>Y2) swap(Y1,Y2); Point zs=(Point){num[X1][Y1].x+(num[X1][Y1]==num[X1-1][Y1]), num[X1][Y1].y+(num[X1][Y1]==num[X1][Y1-1])}; Point yx=(Point){num[X2][Y2].x-(num[X2][Y2]==num[X2+1][Y2]), num[X2][Y2].y-(num[X2][Y2]==num[X2][Y2+1])}; int ans=0; if(!(yx.x>=zs.x && yx.y>=zs.y)) { for(int i=X1;i<=X2;++i) for(int j=Y1;j<=Y2;++j) { ans+=((T[a[i][j]])<<1|1); ++T[a[i][j]]; } for(int i=X1;i<=X2;++i) for(int j=Y1;j<=Y2;++j) --T[a[i][j]]; } else { ans=anss[zs.x][zs.y][yx.x][yx.y]; int TX=ln[zs.x]-1; int TY=rm[yx.y]; for(int i=X1;i<=TX;++i) for(int j=Y1;j<=TY;++j) { ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1); ++T[a[i][j]]; } int TX2=rn[yx.x]; int TY2=rm[yx.y]+1; for(int i=X1;i<=TX2;++i) for(int j=TY2;j<=Y2;++j) { ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1); ++T[a[i][j]]; } int TX3=rn[yx.x]+1; int TY3=lm[zs.y]; for(int i=TX3;i<=X2;++i) for(int j=TY3;j<=Y2;++j) { ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1); ++T[a[i][j]]; } int TX4=ln[zs.x]; int TY4=lm[zs.y]-1; for(int i=TX4;i<=X2;++i) for(int j=Y1;j<=TY4;++j) { ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1); ++T[a[i][j]]; } for(int i=X1;i<=TX;++i) for(int j=Y1;j<=TY;++j) --T[a[i][j]]; for(int i=X1;i<=TX2;++i) for(int j=TY2;j<=Y2;++j) --T[a[i][j]]; for(int i=TX3;i<=X2;++i) for(int j=TY3;j<=Y2;++j) --T[a[i][j]]; for(int i=TX4;i<=X2;++i) for(int j=Y1;j<=TY4;++j) --T[a[i][j]]; } P(ans),puts(""); } return 0;}