題意：
給你N<=100000個(gè)點(diǎn) 同樣x坐標(biāo)的形成豎線段 同樣y坐標(biāo)的形成橫線段
讓你求出豎線段和橫線段的交點(diǎn)數(shù)，包括端點(diǎn)。
做法：
我的做法是先求出非端點(diǎn)的交點(diǎn) 最后答案便是 tot+N
先將數(shù)組復(fù)制一遍 一個(gè)數(shù)組按照1關(guān)鍵字x 2關(guān)鍵字y排序 另一個(gè)關(guān)鍵字順序反一反
將x或者y離散化 這里以y為例
因?yàn)橐呀?jīng)按y排過序 所以所有橫線段已經(jīng)都能得到了(相鄰一段相同y坐標(biāo)的點(diǎn)屬于同一條線段)
并標(biāo)記每條橫線段的兩個(gè)端點(diǎn)。
然后我們枚舉按x坐標(biāo)由左邊向右邊的每條豎線段
我們只要求出有多少橫線段與它有交 便是這條豎線段形成的交點(diǎn)數(shù)
這等價(jià)于求出在當(dāng)前x坐標(biāo)的情況下 橫線段的右端點(diǎn)x坐標(biāo)大于當(dāng)前豎線段x坐標(biāo)的線數(shù)
這樣就可以用線段樹或者樹狀數(shù)組維護(hù)y坐標(biāo)的點(diǎn)（即維護(hù)當(dāng)前還存在的線段）就可以了
如何維護(hù)呢？
對于一條豎線段 我們枚舉形成當(dāng)前豎線的所有點(diǎn) 如果某個(gè)點(diǎn)已經(jīng)是橫線段的結(jié)尾 那就從樹中刪除這個(gè)y坐標(biāo)
反之如果是橫線段的開始 那就加入這個(gè)y坐標(biāo)
在枚舉之前當(dāng)然要求當(dāng)前線的交點(diǎn)個(gè)數(shù)：
對于枚舉到的相鄰兩個(gè)相同x坐標(biāo)的點(diǎn) 假設(shè)y1<y2 我們求出 [y1,y2)的存在的線段個(gè)數(shù) 那便是交點(diǎn)個(gè)數(shù)
這樣就在NLogN時(shí)間內(nèi)解決了此題
ps：發(fā)覺我的基礎(chǔ)太差了。。二分查找[y1,y2)的兩個(gè)端點(diǎn)時(shí)候竟然忘記了 (y2-1)這個(gè)坐標(biāo)事實(shí)上可能不存在
所以二分查找找端點(diǎn)的時(shí)候掛了。。
BS我把本題加強(qiáng)版是 dhx學(xué)長 出的 Religious
1 #include <cstdio>
2 #include <algorithm>
3 using namespace std;
4 #define n 100005
5 struct Tpoint
6 {
7 #define x0(i) p0[i].x
8 #define y0(i) p0[i].y
9 #define nod0(i) p0[i].nod
10 #define x1(i) p1[i].x
11 #define y1(i) p1[i].y
12 #define nod1(i) p1[i].nod
13 int x,y,nod;
14 } p0[n],p1[n];
15 int N,ny[n],New,T[n],ret=0;
16 bool sta[n],end[n];
17 inline bool cmp0(const Tpoint &a,const Tpoint &b)
18 {
19 return a.y<b.y||a.y==b.y&&a.x<b.x;
20 }
21 inline bool cmp1(const Tpoint &a,const Tpoint &b)
22 {
23 return a.x<b.x||a.x==b.x&&a.y<b.y;
24 }
25 inline int find(int x)
26 {
27 int l=0,r=New;
28 for (int mid=(l+r)>>1;l+1<r;mid=(l+r)>>1)
29 if (ny[mid]<=x) l=mid;
30 else r=mid;
31 if (x<ny[r]) return l;
32 return r;
33 }
34 inline int Sum(int x)
35 {
36 int ret=0;
37 for (;x;x-=x&-x)
38 ret+=T[x];
39 return ret;
40 }
41 inline void Add(int x,int delt)
42 {
43 for (;x<=N;x+=x&-x)
44 T[x]+=delt;
45 }
46 int main()
47 {
48 scanf("%d",&N);
49 for (int i=0;i<N;++i)
50 {
51 scanf("%d%d",&x0(i),&y0(i));
52 nod0(i)=i;nod1(i)=i;
53 x1(i)=x0(i),y1(i)=y0(i);
54 }
55 sort(p0,p0+N,cmp0);
56 sta[nod0(0)]=end[nod0(N-1)]=1;
57 for (int i=1;i<N;++i)
58 sta[nod0(i)]=(y0(i)!=y0(i-1));
59 for (int i=0;i<N-1;++i)
60 end[nod0(i)]=(y0(i)!=y0(i+1));
61 ny[++New]=y0(0);
62 for (int i=1;i<N;++i)
63 if (y0(i)!=y0(i-1)) ny[++New]=y0(i);
64 sort(p1,p1+N,cmp1);
65 for (int i=0,k;i<N;i=k)
66 {
67 for (k=i+1;k<N&&x1(i)==x1(k);++k)
68 if (y1(k-1)<y1(k)-1)
69 ret+=Sum(find(y1(k)-1))-Sum(find(y1(k-1)));
70 for (int j=i;j<k;++j)
71 {
72 if (sta[nod1(j)]&&!end[nod1(j)])
73 Add(find(y1(j)),1);
74 if (!sta[nod1(j)]&&end[nod1(j)])
75 Add(find(y1(j)),-1);
76 }
77 }
78 printf("%d\n",N+ret);
79 return 0;
80 }
81