YZOJ P2358 [ZJOI 2012]Naive – Matrix
时间限制：1000MS 内存限制：131072KB
难度：\(7.0\)
-
题目描述
给出一个 \(R \times C\) 的矩阵，上面有 \(N\) 个 \(0\)，其他的都是 \(1\)，现在给出这些 \(0\) 的位置，要求求出有多少个子矩阵包含至少一个 \(0\) 。
-
输入格式
第一行输入三个整数 \(R\)、\(C\)、\(N\) 。
接下来 \(N\) 行，每行两个整数 \(x\)、\(y\)，表示 \(0\) 的坐标。
-
输出格式
输出一个数表示子矩阵的个数。
-
样例输入
|
1 2 3 4 |
5 5 3 1 1 1 4 4 4 |
-
样例输出
|
1 |
103 |
-
数据规模与约定
对于 \(100\%\) 的数据，\(R, C \leq 40000\)，\(N \leq \min\{R \times C,100000\}\)，所有 \(0\) 的位置两两不同且随机生成。
Source: BZOJ 2658
好题！
很显然的是转换「至少包含一个 \(0\) 子矩形的数量」为「不包含 \(0\) 的子矩形的数量」，然后就不会做了（。
想到扫描线，从上往下扫描，处理出每一个点向左向右向上能到达的最远距离，发现这一步骤可以使用单调栈！笛卡尔树维护，答案就是 \(\sum\limits_{x}{\frac{size_x \times \left(size_x+1\right)}{2}\times \left(height_x-height_{fa}\right)}\) 。
注：这里每个节点维护的是其对父亲节点的贡献！
考虑如何由这一层的笛卡尔树转换至下一层。
发现笛卡尔树其实和 \(Treap\) 是一样的东西，再加上本题的权值 \(height\) 是随机的，所以就可以用 \(Treap\) 维护这一操作。跳层其实就是把所有节点的 \(pri\) 都加上 \(1\) ，然后把当前层所有值为 \(0\) 的节点的 \(pri\) 设为 \(0\) 即可。
时间复杂度 \(O(NlogN+NlogC)\) 。
|
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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } int root,pri[40505],size[40505],lson[40505],rson[40505]; int tag[40505]; long long ans[40505]; inline void PushUp(register int x) { size[x]=size[lson[x]]+size[rson[x]]+1; // father[x] hasn't been defined yet!!! //ans[x]=ans[lson[x]]+ans[rson[x]]+((long long)size[x]*(size[x]+1)>>1)*(pri[x]-pri[father[x]]); ans[x]=0; if(lson[x]) ans[x]+=ans[lson[x]]+((long long)size[lson[x]]*(size[lson[x]]+1)>>1)*(pri[lson[x]]-pri[x]); if(rson[x]) ans[x]+=ans[rson[x]]+((long long)size[rson[x]]*(size[rson[x]]+1)>>1)*(pri[rson[x]]-pri[x]); } inline void PushDown(register int x) { if(tag[x]) { if(lson[x]) tag[lson[x]]+=tag[x],pri[lson[x]]+=tag[x]; if(rson[x]) pri[rson[x]]+=tag[x],tag[rson[x]]+=tag[x]; tag[x]=0; } } inline int MergeTree(register int x,register int y) { if(!x || !y) return x^y; PushDown(x),PushDown(y); if(pri[x] < pri[y]) { rson[x]=MergeTree(rson[x],y); return PushUp(x),x; } else { lson[y]=MergeTree(x,lson[y]); return PushUp(y),y; } } inline void SplitTreeByOrder(register int o,register int k,int&x,int&y) { if(!o) { x=y=0; return; } PushDown(o); if(k <= size[lson[o]]) y=o,SplitTreeByOrder(lson[o],k,x,lson[o]); else x=o,SplitTreeByOrder(rson[o],k-size[lson[o]]-1,rson[o],y); PushUp(o); } inline int BuildTree(register int l,register int r) { if(l>r) return 0; register int mid=(l+r)>>1; lson[mid]=BuildTree(l,mid-1); rson[mid]=BuildTree(mid+1,r); return PushUp(mid),mid; } struct _point { int x,y; bool operator < (const _point&o)const { if(x != o.x) return x<o.x; return y<o.y; } }pnts[105050]; int main() { register int R=getnum(),C=getnum(),N=getnum(); for(register int i=1;i<=N;i++) pnts[i]=(_point){getnum(),getnum()}; std::sort(&pnts[1],&pnts[N+1]); root=BuildTree(1,C); long long ans=((long long)R*(R+1)>>1)*((long long)C*(C+1)>>1); for(register int x=1,j=1;x<=R;x++) { pri[root]++,tag[root]++; while(j<=N && pnts[j].x==x) { int a,b,c,d; SplitTreeByOrder(root,pnts[j].y-1,a,b); SplitTreeByOrder(b,1,c,d); pri[c]=0; root=MergeTree(a,MergeTree(c,d)); j++; } ans-=::ans[root]+((long long)size[root]*(size[root]+1)>>1)*pri[root]; } printf("%lld\n",ans); return 0; } |