BZOJ1818:[Cqoi2010]内部白点(BIT+扫描线)

就是求多条线段的交点数,直接BIT&＃43;扫描线就行了. 注意不要算重最初存在的点.

#include
using namespace std;
char cb[1<<15],*cs&＃61;cb,*ct&＃61;cb;
#define getc() (cs&＃61;&＃61;ct&&(ct&＃61;(cs&＃61;cb)&＃43;fread(cb,1,1<<15,stdin),cs&＃61;&＃61;ct)?0:*cs&＃43;&＃43;)
template<class T>inline void read(T &res) {char ch; int flg &＃61; 1; for(;!isdigit(ch&＃61;getc());)if(ch&＃61;&＃61;&＃39;-&＃39;)flg&＃61;-flg;for(res&＃61;ch-&＃39;0&＃39;;isdigit(ch&＃61;getc());res&＃61;res*10&＃43;ch-&＃39;0&＃39;); res*&＃61;flg;
}
const int MAXN &＃61; 100005;
struct node { int x, y; }a[MAXN];
struct Node { int x, y, v; inline bool operator <(const Node &o)const { return y < o.y; } }q[MAXN];
inline bool cmpx(const node &a, const node &b) { return a.x &＃61;&＃61; b.x ? a.y < b.y : a.x < b.x; }
inline bool cmpy(const node &a, const node &b) { return a.y &＃61;&＃61; b.y ? a.x < b.x : a.y < b.y; }
int n, T[MAXN], b[MAXN], tot, N;
inline void upd(int x, int val) { while(x <&＃61; N) T[x] &＃43;&＃61; val, x &＃43;&＃61; x&-x; }
inline int qsum(int x) { int re &＃61; 0; while(x) re &＃43;&＃61; T[x], x -&＃61; x&-x; return re; }
int main() {read(n);for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)read(a[i].x), read(a[i].y), b[&＃43;&＃43;N] &＃61; a[i].x;sort(b &＃43; 1, b &＃43; N &＃43; 1);N &＃61; unique(b &＃43; 1, b &＃43; N &＃43; 1) - b - 1;for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) //离散化x坐标a[i].x &＃61; lower_bound(b &＃43; 1, b &＃43; N &＃43; 1, a[i].x) - b;sort(a &＃43; 1, a &＃43; n &＃43; 1, cmpx);for(int i &＃61; 1, j; i <&＃61; n; i &＃61; j) {int L &＃61; a[i].y, R;for(j &＃61; i; j <&＃61; n && a[j].x &＃61;&＃61; a[i].x; &＃43;&＃43;j)R &＃61; a[j].y;if(R-L > 1) { //差分&＃43;&＃43;tot, q[tot].x &＃61; a[i].x, q[tot].y &＃61; L&＃43;1, q[tot].v &＃61; 1;&＃43;&＃43;tot, q[tot].x &＃61; a[i].x, q[tot].y &＃61; R, q[tot].v &＃61; -1;}}sort(a &＃43; 1, a &＃43; n &＃43; 1, cmpy);sort(q &＃43; 1, q &＃43; tot &＃43; 1);int cur &＃61; 1, ans &＃61; n;for(int i &＃61; 1, j; i <&＃61; n; i &＃61; j) {while(cur <&＃61; tot && q[cur].y <&＃61; a[i].y)upd(q[cur].x, q[cur].v), &＃43;&＃43;cur;for(j &＃61; i&＃43;1; j <&＃61; n && a[j].y &＃61;&＃61; a[i].y; &＃43;&＃43;j)if(a[j-1].x&＃43;1 <&＃61; a[j].x-1)ans &＃43;&＃61; qsum(a[j].x-1) - qsum(a[j-1].x); //差分//注意这里不能只用最靠左和最靠右的点形成的线段在BIT里查找//因为这段里面可能有最初就存在的黑点}printf("%d\n", ans);
}