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

#include<bits/stdc++.h>

using namespace std;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

	char ch; int flg = 1; for(;!isdigit(ch=getc());)if(ch=='-')flg=-flg;

	for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 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 == b.x ? a.y < b.y : a.x < b.x; }

inline bool cmpy(const node &a, const node &b) { return a.y == 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 <= N) T[x] += val, x += x&-x; }

inline int qsum(int x) { int re = 0; while(x) re += T[x], x -= x&-x; return re; }

int main() {

	read(n);

	for(int i = 1; i <= n; ++i)

		read(a[i].x), read(a[i].y), b[++N] = a[i].x;

	sort(b + 1, b + N + 1);

	N = unique(b + 1, b + N + 1) - b - 1;

	for(int i = 1; i <= n; ++i) //离散化x坐标

		a[i].x = lower_bound(b + 1, b + N + 1, a[i].x) - b;

	sort(a + 1, a + n + 1, cmpx);

	for(int i = 1, j; i <= n; i = j) {

		int L = a[i].y, R;

		for(j = i; j <= n && a[j].x == a[i].x; ++j)

			R = a[j].y;

		if(R-L > 1) { //差分

			++tot, q[tot].x = a[i].x, q[tot].y = L+1, q[tot].v = 1;

			++tot, q[tot].x = a[i].x, q[tot].y = R, q[tot].v = -1;

		}

	}

	sort(a + 1, a + n + 1, cmpy);

	sort(q + 1, q + tot + 1);

	int cur = 1, ans = n;

	for(int i = 1, j; i <= n; i = j) {

		while(cur <= tot && q[cur].y <= a[i].y)

			upd(q[cur].x, q[cur].v), ++cur;

			for(j = i+1; j <= n && a[j].y == a[i].y; ++j)

				if(a[j-1].x+1 <= a[j].x-1)

					ans += qsum(a[j].x-1) - qsum(a[j-1].x); //差分

				//注意这里不能只用最靠左和最靠右的点形成的线段在BIT里查找

				//因为这段里面可能有最初就存在的黑点

	}

	printf("%d\n", ans);

}
巴特西

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

CODE

最新文章

热门文章
