【BZOJ2639】矩形计算（二维普通莫队）

题意：输入一个n*m的矩阵，矩阵的每一个元素都是一个整数，然后有q个询问，每次询问一个子矩阵的权值。

矩阵的权值是这样定义的，对于一个整数x，如果它在该矩阵中出现了p次，那么它给该矩阵的权值就贡献p^2。

n,m<=200，m<=1e5，abs(a[i][j])<=2e9

思路：学习资料见https://www.cnblogs.com/ouuan/p/2DMoDui.html

和一维普通莫队差不多，先扩大区间再缩小保证不会出错

这个块长很有特色，和n，m，q都有关

map离散化真的不靠谱，换预处理离散化即可

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 //typedef pair<ll,ll>P;
 11 #define N  210
 12 #define M  200010
 13 #define fi first
 14 #define se second
 15 #define MP make_pair
 16 #define pb push_back
 17 #define pi acos(-1)
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 20 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 21 #define lowbit(x) x&(-x)
 22 #define Rand (rand()*(1<<16)+rand())
 23 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 24 #define ls p<<1
 25 #define rs p<<1|1
 26 
 27 const int MOD=1e9+7,inv2=(MOD+1)/2;
 28       double eps=1e-4;
 29       int INF=1e9;
 30       int inf=0x7fffffff;
 31       int dx[4]={-1,1,0,0};
 32       int dy[4]={0,0,-1,1};
 33 
 34 struct Q
 35 {
 36     int x1,y1,x2,y2,id;
 37 }t[M];
 38 
 39 int cnt[N*N],c[N*N];
 40 int ans[M],pos[250],a[N][N],sum,L1,L2,R1,R2;
 41 
 42 int read()
 43 {
 44    int v=0,f=1;
 45    char c=getchar();
 46    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 47    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 48    return v*f;
 49 }
 50 
 51 bool cmp(Q a,Q b)
 52 {
 53     return pos[a.x1]<pos[b.x1]
 54          ||pos[a.x1]==pos[b.x1]&&pos[a.y1]<pos[b.y1]
 55          ||pos[a.x1]==pos[b.x1]&&pos[a.y1]==pos[b.y1]&&pos[a.x2]<pos[b.x2]
 56          ||pos[a.x1]==pos[b.x1]&&pos[a.y1]==pos[b.y1]&&pos[a.x2]==pos[b.x2]&&pos[a.y2]<pos[b.y2];
 57 }
 58 
 59 void add(int op,int x,int y,int z)
 60 {
 61     if(op==1)
 62     {
 63         if(!x) return;
 64         rep(j,y,z)
 65          if(j)
 66          {
 67             sum+=(cnt[a[x][j]]<<1)+1;
 68             cnt[a[x][j]]++;
 69          }
 70     }
 71      else
 72      {
 73          if(!z) return;
 74          rep(i,x,y)
 75           if(i)
 76           {
 77               sum+=(cnt[a[i][z]]<<1)+1;
 78               cnt[a[i][z]]++;
 79           }
 80      }
 81 }
 82 
 83 void del(int op,int x,int y,int z)
 84 {
 85     if(op==1)
 86     {
 87         if(!x) return;
 88         rep(j,y,z)
 89          if(j)
 90          {
 91              sum=sum-(cnt[a[x][j]]<<1)+1;
 92              cnt[a[x][j]]--;
 93          }
 94     }
 95      else
 96      {
 97          if(!z) return;
 98          rep(i,x,y)
 99           if(i)
100           {
101               sum=sum-(cnt[a[i][z]]<<1)+1;
102               cnt[a[i][z]]--;
103           }
104      }
105 }
106 
107 int main()
108 {
109     int n=read(),m=read();
110     int tot=0;
111     rep(i,1,n)
112      rep(j,1,m)
113      {
114          a[i][j]=read();
115          c[++tot]=a[i][j];
116      }
117     sort(c+1,c+tot+1);
118     int k=unique(c+1,c+tot+1)-c-1;
119     rep(i,1,n)
120      rep(j,1,m) a[i][j]=lower_bound(c+1,c+k+1,a[i][j])-c;
121     int q=read();
122     int S=pow(n*m,0.5)/pow(q,0.25)+1;
123     rep(i,1,200) pos[i]=(i-1)/S;
124     rep(i,1,q)
125     {
126         int x1=read(),y1=read(),x2=read(),y2=read();
127         t[i].x1=min(x1,x2);
128         t[i].x2=max(x1,x2);
129         t[i].y1=min(y1,y2);
130         t[i].y2=max(y1,y2);
131         t[i].id=i;
132     }
133     sort(t+1,t+q+1,cmp);
134     L1=0,L2=0,R1=0,R2=0;
135     sum=0;
136     rep(i,1,q)
137     {
138         while(L1>t[i].x1)
139         {
140             L1--;
141             add(1,L1,R1,R2);
142         }
143         while(L2<t[i].x2)
144         {
145             L2++;
146             add(1,L2,R1,R2);
147         }
148         while(R1>t[i].y1)
149         {
150             R1--;
151             add(2,L1,L2,R1);
152         }
153         while(R2<t[i].y2)
154         {
155             R2++;
156             add(2,L1,L2,R2);
157         }
158 
159         while(L1<t[i].x1)
160         {
161             del(1,L1,R1,R2);
162             L1++;
163         }
164         while(L2>t[i].x2)
165         {
166             del(1,L2,R1,R2);
167             L2--;
168         }
169         while(R1<t[i].y1)
170         {
171             del(2,L1,L2,R1);
172             R1++;
173         }
174         while(R2>t[i].y2)
175         {
176             del(2,L1,L2,R2);
177             R2--;
178         }
179         ans[t[i].id]=sum;
180     }
181     rep(i,1,q) printf("%d
",ans[i]);
182     return 0;
183 }