[BZOJ1818][CQOI2010]内部白点

题目链接：

BZOJ1818

首先，题目根本不会有\(-1\)的情况，且所有节点变色只发生在第一秒。

证明？如果一个节点\((x,y)\)在第二秒变色，那么一定有一个节点会在第一秒内于\((x,y)\)的四周生成。

假设在左边（其他方向也一样），则设坐标为\((x`,y)\)。

那么因为\((x`,y)\)出现了，说明\((x`,y)\)是个内部节点，那么在此之前\((x`,y)\)的左边也一定有一个黑色节点，否则此节点不能变色。

那么\((x,y)\)就可以在第一秒变色。

则题目变成求线段（两个\(x\)或\(y\)轴坐标相同点的连线）的交点数量。

那么将所有线段离散化，从左向右扫描竖线，对于横线用树状数组维护当前哪些地方有横向线段。

若碰到线段左端，此线段对\(y\)坐标做出\(1\)的贡献，反之\(-1\)。

对于如\((1,1),(3,1),(5,1)\)三个点，应该拆成两条线段，防止覆盖。

看了看别人的代码，感觉自己的好麻烦。。还慢

时间复杂度 \(O(nlog_2n)\)

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>int n,Horc,Verc;
int xs[100005],ys[100005];
int as[100005];
std::vector<int> cs[100005],St[100005],Ed[100005];struct Segment
{int l,r,p;
}Hor[100005],Ver[100005];//线段，Hor为横向struct Binary_Indexed_Tree
{int c[100005];inline void Modify(int x,int v){for(;x<=n;x+=x&-x)c[x]+=v;}inline int Query(int x){int Res=0;for(;x;x^=x&-x)Res+=c[x];return Res;}
}BIT;//树状数组void Simplify(int *a)//离散化
{memcpy(as,a,sizeof as);std::sort(as+1,as+n+1);int nl=std::unique(as+1,as+n+1)-as-1;for(int i=1;i<=n;++i)a[i]=std::lower_bound(as+1,as+nl+1,a[i])-as;
}void Getseg(int *a,int *b,int &Cnt,Segment *Tar)//求线段
{for(int i=1;i<=n;++i)cs[i].clear();for(int i=1;i<=n;++i)cs[b[i]].push_back(a[i]);for(int i=1;i<=n;++i)std::sort(cs[i].begin(),cs[i].end());for(int i=1;i<=n;++i)for(int j=1;j<(int)cs[i].size();++j)if(cs[i][j]-cs[i][j-1]>=2)Tar[++Cnt]=(Segment){cs[i][j-1]+1,cs[i][j]-1,i};
}int main()
{scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d%d",&xs[i],&ys[i]);Simplify(xs);Simplify(ys);Getseg(xs,ys,Horc,Hor);Getseg(ys,xs,Verc,Ver);for(int i=1;i<=Horc;++i){St[Hor[i].l].push_back(Hor[i].p);Ed[Hor[i].r].push_back(Hor[i].p);}int Sv=1;long long Ans=0;for(int i=1;i<=n;++i){for(int j=0;j<(int)St[i].size();++j)BIT.Modify(St[i][j],+1);//碰到左端端点for(;Sv<=Verc&&Ver[Sv].p==i;++Sv)Ans+=BIT.Query(Ver[Sv].r)-BIT.Query(Ver[Sv].l-1);for(int j=0;j<(int)Ed[i].size();++j)BIT.Modify(Ed[i][j],-1);//碰到右端端点}printf("%lld\n",Ans+n);//还要加上原来的黑点return 0;
}