四川网站设计首选柚米科技,购物网站的后台做哪些东西,做视频赚钱的网站有哪些,WordPress设置页面宽度占满洛谷P5987 [PA2019] Terytoria
题目大意
在一个平面直角坐标系上#xff0c;有一个长度为 X X X#xff0c;宽度为 Y Y Y的地图#xff0c;这个地图的左边界和右边界是连通的#xff0c;下边界和上边界也是连通的。
在地图中#xff0c;有 X Y X\times Y XY个格子以及…洛谷P5987 [PA2019] Terytoria
题目大意
在一个平面直角坐标系上有一个长度为 X X X宽度为 Y Y Y的地图这个地图的左边界和右边界是连通的下边界和上边界也是连通的。
在地图中有 X × Y X\times Y X×Y个格子以及 n n n个矩形这些矩形的边与坐标轴平行。你只知道每个矩形两个对顶点的坐标求被所有矩形覆盖住的格子数量的最大值 1 ≤ n ≤ 5 × 1 0 5 , 2 ≤ X , Y ≤ 1 0 9 1\leq n\leq 5\times 10^5,2\leq X,Y\leq 10^9 1≤n≤5×105,2≤X,Y≤109 题解
因为每个矩形在横坐标上是取两边或中间在纵坐标上也是取两边或中间所以横坐标和纵坐标是不相关的。我们把这些矩形分成映射在 x x x轴的线段和映射在 y y y轴的线段则最终的答案为 x x x轴上能被所有线段覆盖的最大长度 × y \times y ×y轴上能被所有线段覆盖的最大长度。那么我们就可以将横坐标和纵坐标分开来做。
对横纵坐标进行离散化对于离散化后的两个相邻的离散点连成的线段。那么每种线段只有唯一的取法取中间或者两边才能覆盖这条由两个离散点连成的线段。我们用 01 01 01状态来表示每个矩形的覆盖情况 0 0 0表示取两边 1 1 1表示取中间状态可以用哈希和差分来维护然后用哈希表来存储对应状态的长度边维护边取最大值。
时间复杂度为 O ( n log n P ) O(n\log nP) O(nlognP)其中 P P P为哈希表的大小。
code
#includebits/stdc.h
using namespace std;
const int N500000,P19260817,base7;
const long long mod1998244353,mod21e97;
int n,X,Y,tot0,l[2*N5],r[P5],hv[2*N5],w1[2*N5],w2[2*N5];
long long re,ans0,pw1[N5],pw2[N5];
struct node{int x,w,id;
}x[2*N5],y[2*N5];
bool cmp(node ax,node bx){return ax.xbx.x;
}
void add(int x,int h1,int h2,int vt){l[tot]r[x];w1[tot]h1;w2[tot]h2;hv[tot]vt;r[x]tot;
}
void pl(int h1,int h2,int vt){int uh1%P;for(int ir[u];i;il[i]){if(w1[i]h1w2[i]h2){hv[i]vt;remax(re,1ll*hv[i]);return;}}add(u,h1,h2,vt);remax(re,1ll*vt);
}
long long solve(node *a,int mx){memset(r,0,sizeof(r));re0;tot0;long long h10,h20;pl(0,0,a[1].x);for(int i1;i2*n;i){h1(h1pw1[a[i].id]*a[i].wmod1)%mod1;h2(h2pw2[a[i].id]*a[i].wmod2)%mod2;pl(h1,h2,a[i1].x-a[i].x);}pl(0,0,mx-a[2*n].x);return re;
}
int main()
{
// freopen(globe.in,r,stdin);
// freopen(globe.out,w,stdout);scanf(%d%d%d,n,X,Y);for(int i1,dx,dy,ux,uy;in;i){scanf(%d%d%d%d,dx,dy,ux,uy);if(dxux) swap(dx,ux);if(dyuy) swap(dy,uy);x[i*2-1](node){dx,1,i};x[i*2](node){ux,-1,i};y[i*2-1](node){dy,1,i};y[i*2](node){uy,-1,i};}sort(x1,x2*n1,cmp);sort(y1,y2*n1,cmp);pw1[0]pw2[0]1;for(int i1;iN;i){pw1[i]pw1[i-1]*base%mod1;pw2[i]pw2[i-1]*base%mod2;}anssolve(x,X)*solve(y,Y);printf(%lld,ans);return 0;
}
