欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ5045
题意概括
有一堵墙。
现在挖掉某些砖。如果有相邻的某两个砖没有了，那么他们中上方的那块也没了。
比如(0,0)和(0,2)被挖掉了，那么(1,1)也没了; (1,1)没了(1,3)没了，那么(2,2)也没了。
现在挖掉n(n<=100000)块砖，问会掉多少块砖；
砖块坐标<=109
题解
我们按照纵坐标离散化。
我们把对于最低行的所有砖块改成用许多条线段不重复覆盖的形式。这个需要排序和线性处理。
每条线段可以弄掉的位置为一个以线段为底的三角形区域。
然后跳转往上到第二个纵坐标。
枚举原来处理过的线段。如果线段能打掉的三角形的顶点在当前纵坐标之上，那么我们把一个新的梯形区域记入，并构成一条当前纵坐标的线段。
如果顶点在下面，那么直接统计即可。
对于现在，有两类线段，一种是从下面继承的，一种是当前原有的。
其实没什么区别的。
直接按照对最低行的处理搞一搞就可以了。
然后循环解决。
这样的时间复杂度是O(nlogn)的。
为什么？因为我们把所有的线段看一看。我们发现，由x块砖构成的线段，最多可以演变成x条纵坐标不同的线段，那么不同的线段总数<=n。
对于每一条不同的线段，处理的均摊复杂度为O(logn)；最多n条不同线段，那么O(nlogn);
具体处理还是也具体看待。
代码
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=100000+5;
int n,x[N],xz;
LL ans=0;
struct Point{
int x,y;
}p[N];
struct vec{
Point seg[N];
int z;
void clear(){
z=0;
}
void push(int a,int b){
seg[++z].x=a,seg[z].y=b;
}
}a,b;
bool cmpx(Point a,Point b){
return a.x<b.x;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y),x[i]=p[i].x;
sort(p+1,p+n+1,cmpx);
sort(x+1,x+n+1);
xz=1;
for (int i=2;i<=n;i++)
if (x[i]!=x[i-1])
x[++xz]=x[i];
a.clear();
for (int pos=1,xp=1;pos<=n,xp<=xz;xp++){
b.clear();
for (int i=1;i<=a.z;i++){
int L=a.seg[i].x,R=a.seg[i].y,w=(R-L)/2,dx=x[xp]-x[xp-1];
if (w<=dx)
ans+=1LL*w*(w+1)/2;
else {
ans+=1LL*(w+w-dx+1)*dx/2;
b.push(L+dx,R-dx);
}
}
for (;p[pos].x==x[xp];pos++)
b.push(p[pos].y,p[pos].y+2);
sort(b.seg+1,b.seg+b.z+1,cmpx);
a.clear();
vec &c=a;
for (int i=1;i<=b.z;i++)
if (c.z==0||c.seg[c.z].y<b.seg[i].x)
c.push(b.seg[i].x,b.seg[i].y);
else
c.seg[c.z].y=max(c.seg[c.z].y,b.seg[i].y);
}
for (int i=1;i<=a.z;i++){
int L=a.seg[i].x,R=a.seg[i].y,w=(R-L)/2;
ans+=1LL*w*(w+1)/2;
}
printf("%lld",ans);
return 0;
}