首页 > 代码库 > poj3109树状数组+扫描线
poj3109树状数组+扫描线
题意：无限大的棋盘上，在横向和纵向上被包围的白子会变成黑子，求最终黑子个数？
分析：
首先这个棋盘十分的大，但已给黑点的个数为1e5，我们需要离散化，所谓的离散化就是数组下标的重新定义。
这里给出离散化函数，返回的是离散化后数组的个数
1 int compress(int *p,int N) 2 { 3 vector<int> ps(N); 4 for (int i = 0; i < N; ++i)ps[i] = p[i]; 5 sort(ps.begin(), ps.end()); 6 ps.erase(unique(ps.begin(), ps.end()), ps.end()); 7 for (int i = 0; i < N; ++i) 8 { 9 p[i] = 1 + distance(ps.begin(), lower_bound(ps.begin(), ps.end(), p[i]));10 }11 return ps.size();12 }
扫描线算法：
扫描线算法其实是计算机几何里面的算法,这里引用
基本思想
按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。
对于一条扫描线填充过程可以分为四个步骤：
(1) 求交：计算扫描线与多边形各边的交点
(2) 排序：把所有交点按 x 坐标递增顺序来排序
(3) 配对：确定扫描线与多边形的相交区间，第一个与第二个，第三个与第四个等等，每对交点代表扫描线与多边形的一个相交区间
(4) 填充：显示相交区间的象素
那么对于这道题目来说我们如何使用？
首先构造扫描线，这里使用Y轴，X轴其实一样的
对于每一条扫描线上的点按x坐标排序，然后得到n个区间，我们需要统计在这个区间里面有多少白色的点可以变为黑点
条件是上下都被黑点包围(左右已经符合)
如何判断上下有没有黑点呢？这里巧妙的使用了一个bool数组used，used[i]表示x=i这条竖线上是否已经出现过黑点
由于扫描线算法中扫描线是按y从小到大枚举的，所以如果之前有出现过黑点，加上当前扫描的点也是黑点，那么这个区间一定是被黑点包围的。
现在来处理区间统计问题，这是树状数组的强项。(区间加减+区间求和)
实际上这里只用到了区间加减+单点查询，都差不多
现在给出算法:
首先离散化，然后构造扫描线。
接着按y从小到大枚举扫描线，对于每条扫描线的点按x从小到大排序，遍历所有的点可以得到n个区间[a[i-1],a[i]]
对于区间[a[i-1],a[i]],当前遍历到a[i]，如果竖轴x=a[i]上used[x]=true 那么需要将答案加上当前竖轴上区间的白点个数query(x,x),否认设置used[x]=true(因为当前遍历的就是黑点),计算完该区间以后一定要记得将该区间的树状数组清掉，因为树状数组维护的区间和，如果不清会导致重复计算(两条扫描线之间的点),
至于更新的话很简单，就是把区间（a[i-1],a[i]）都加上1,因为区间中都是满足左右被黑点包围的白点。（注意不要越界）
最后上代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<cmath> 9 #include<vector>10 #define maxn 10000011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f14 using namespace std;15 typedef long long ll;16 inline int lowbit(int x){17 return x&-x;18 }19 struct BIT{20 int n;21 ll bit[maxn+10],bit2[maxn+10];22 void init(int N){//建立bit23 n=N;24 memset(bit,0,sizeof(bit));25 memset(bit2,0,sizeof(bit2));26 }27 void add(ll *t,int x,ll v){//单点加减28 for(int i=x;i<=n;i+=lowbit(i))t[i]+=v;29 }30 ll sum(ll *t,int x){//[1,x]前缀和31 ll ans=0;32 for(int i=x;i>0;i-=lowbit(i))ans+=t[i];33 return ans;34 }35 void update(int l,int r,ll k){//区间加减36 add(bit,l,k);37 add(bit,r+1,-k);38 add(bit2,l,k*l);39 add(bit2,r+1,-k*(r+1));40 }41 ll getsum(int x){42 return sum(bit,x)*(x+1)-sum(bit2,x);43 }44 ll query(int l,int r){//区间求和45 return getsum(r)-getsum(l-1);46 }47 }T;48 int X[maxn],Y[maxn];49 int compress(int *p,int N)50 {51 vector<int> ps(N);52 for (int i = 0; i < N; ++i)ps[i] = p[i];53 sort(ps.begin(), ps.end());54 ps.erase(unique(ps.begin(), ps.end()), ps.end());55 for (int i = 0; i < N; ++i)56 {57 p[i] = 1 + distance(ps.begin(), lower_bound(ps.begin(), ps.end(), p[i]));58 }59 return ps.size();60 }61 bool used[maxn];62 vector<int>line[maxn];//扫描线63 int main (){64 int n;65 while(scanf("%d",&n)!=EOF){66 T.init(maxn);67 memset(used,false,sizeof(used));68 for(int i=0;i<n;++i)scanf("%d%d",&X[i],&Y[i]);69 int w = compress(X,n);70 int h = compress(Y,n);71 for(int i=0;i<n;++i){72 line[Y[i]].push_back(X[i]);73 }74 ll ans =n;75 for(int i = 1;i<=h;++i){76 vector<int>&v = line[i];77 sort(v.begin(),v.end());78 for(vector<int>::iterator j = v.begin();j!=v.end();++j){79 int x = *j;80 ll s = T.query(x,x);81 if(used[x])ans+=s;82 else used[x]=true;83 T.update(x,x,-s);84 if(j!=v.end()-1)T.update(x+1,*(j+1)-1,1);85 }86 }87 printf("%lld\n",ans);88 }89 }