BZOJ 2639: 矩形计算（二维莫队）
Posted On 2018年10月10日
Description
输入一个n*m的矩阵，矩阵的每一个元素都是一个整数，然后有q个询问，每次询问一个子矩阵的权值。矩阵的权值是这样定义的，对于一个整数x，如果它在该矩阵中出现了p次，那么它给该矩阵的权值就贡献p2。
Input
第一行两个整数n，m表示矩阵的规模。
接下来n行每行m个整数，表示这个矩阵的每个元素。
再下来一行一个整数q，表示询问个数。
接下来q行每行四个正整数x1，y1，x2，y2，询问以第x1行第y1列和第x2行第y2列的连线为对角线的子矩阵的权值。
接下来n行每行m个整数，表示这个矩阵的每个元素。
再下来一行一个整数q，表示询问个数。
接下来q行每行四个正整数x1，y1，x2，y2，询问以第x1行第y1列和第x2行第y2列的连线为对角线的子矩阵的权值。
Output
输出q行每行一个整数回答对应询问。
Sample Input
3 4
1 3 2 1
1 3 2 4
1 2 3 4
8
1 2 2 1
1 1 2 1
1 1 3 4
1 1 1 1
2 2 3 3
3 4 2 2
1 3 3 1
2 4 3 4
1 3 2 1
1 3 2 4
1 2 3 4
8
1 2 2 1
1 1 2 1
1 1 3 4
1 1 1 1
2 2 3 3
3 4 2 2
1 3 3 1
2 4 3 4
Sample Output
8
4
38
1
8
12
27
4
4
38
1
8
12
27
4
HINT
对于全部数据
1<=n,m<=200
q<=100000
|矩阵元素大小|<=2*109
Source
Solution
今天NOIPlus灰心赛T2
第n眼莫队，然而并不会证复杂度，百度一搜矩形莫队就搜出了原题。。
考虑对左上的端点的编号分块排序，右下按编号排序（编号从左到右，从上到下）
注意指针移动时要维护好两个指针对的关系，可以通过每个指针都移动一次保证关系不改变
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <algorithm> #include <bitset> #include <queue> #include <set> #include <iostream> typedef long long ll; #define y1 cpp11 using namespace std; bool flag; const int maxn=207,maxq=100000+9; char s[maxq*100],*c; inline int read() { int f=1,k=0; while (*c<'0'||*c>'9')*c++=='-'&&(f=-1); while (*c>='0'&&*c<='9')k=k*10+*c++-'0'; return k*f; } struct mc{int posx,posy,val;}store[maxn*maxn]; struct zmc{int x1,y1,x2,y2,pos;}ask[maxq]; int val[maxn][maxn],bl[maxn][maxn],cnt[maxn*maxn]; int id[maxn][maxn]; ll ans[maxq],aw=1; int x1,y1,x2,y2; inline void mt() { flag=1; } inline int max(const int a,const int b){return a>b?a:b;} inline int min(const int a,const int b){return a<b?a:b;} inline bool cmp(const mc&a,const mc&b){return a.val<b.val;} inline bool cmp2(const zmc&a,const zmc&b){return bl[a.x1][a.y1]==bl[b.x1][b.y1]?id[a.x2][a.y2]<id[b.x2][b.y2]:bl[a.x1][a.y1]<bl[b.x1][b.y1];} inline void upd(const int x1,const int y1,const int x2,const int y2,const int delta) { for (int i=x1;i<=x2;i++) for (int j=y1;j<=y2;j++) { int&v=cnt[val[i][j]]; if (delta==1)aw-=v*v,++v,aw+=v*v; else aw-=v*v,--v,aw+=v*v; } } signed main() { fread(c=s,1,sizeof(s),stdin); int r=read(),c=read(),sizx=sqrt(r),sizy=sqrt(c),nt=0; for (int i=1;i<=r;i++) for (int j=1;j<=c;j++) store[(i-1)*c+j]=(mc){i,j,read()},bl[i][j]=((i-1)/sizx)*sizy+((j-1)/sizy+1),id[i][j]=++nt; sort(store+1,store+1+r*c,cmp); int tot=1; val[store[1].posx][store[1].posy]=1; for (int i=2;i<=r*c;i++) if (store[i].val!=store[i-1].val) val[store[i].posx][store[i].posy]=++tot; else val[store[i].posx][store[i].posy]=tot; int q=read(); for (int i=1;i<=q;i++) { int x1=read(),y1=read(),x2=read(),y2=read(); ask[i]=(zmc){min(x1,x2),min(y1,y2),max(x1,x2),max(y1,y2),i}; } sort(ask+1,ask+1+q,cmp2); cnt[val[1][1]]=1; x1=1,y1=1,x2=1,y2=1; for (int i=1;i<=q;i++) { while (1) { flag=0; if (x2<ask[i].x2)++x2,upd(x2,y1,x2,y2,1),mt(); if (x2>ask[i].x2)upd(x2,y1,x2,y2,-1),--x2,mt(); if (y2<ask[i].y2)++y2,upd(x1,y2,x2,y2,1),mt(); if (y2>ask[i].y2)upd(x1,y2,x2,y2,-1),--y2,mt(); if (x1<ask[i].x1)upd(x1,y1,x1,y2,-1),++x1,mt(); if (x1>ask[i].x1)--x1,upd(x1,y1,x1,y2,1),mt(); if (y1<ask[i].y1)upd(x1,y1,x2,y1,-1),++y1,mt(); if (y1>ask[i].y1)--y1,upd(x1,y1,x2,y1,1),mt(); if (!flag)break; } ans[ask[i].pos]=aw; } for (int i=1;i<=q;i++)printf("%lld\n",ans[i]); } |
?
?