題意：
給你N<=100000個點 同樣x坐標的形成豎線段 同樣y坐標的形成橫線段
讓你求出豎線段和橫線段的交點數，包括端點。
做法：
我的做法是先求出非端點的交點 最后答案便是 tot+N
先將數組復制一遍 一個數組按照1關鍵字x 2關鍵字y排序 另一個關鍵字順序反一反
將x或者y離散化 這里以y為例
因為已經按y排過序 所以所有橫線段已經都能得到了(相鄰一段相同y坐標的點屬于同一條線段)
并標記每條橫線段的兩個端點。
然后我們枚舉按x坐標由左邊向右邊的每條豎線段
我們只要求出有多少橫線段與它有交 便是這條豎線段形成的交點數
這等價于求出在當前x坐標的情況下 橫線段的右端點x坐標大于當前豎線段x坐標的線數
這樣就可以用線段樹或者樹狀數組維護y坐標的點（即維護當前還存在的線段）就可以了
如何維護呢？
對于一條豎線段 我們枚舉形成當前豎線的所有點 如果某個點已經是橫線段的結尾 那就從樹中刪除這個y坐標
反之如果是橫線段的開始 那就加入這個y坐標
在枚舉之前當然要求當前線的交點個數：
對于枚舉到的相鄰兩個相同x坐標的點 假設y1<y2 我們求出 [y1,y2)的存在的線段個數 那便是交點個數
這樣就在NLogN時間內解決了此題
ps：發覺我的基礎太差了。。二分查找[y1,y2)的兩個端點時候竟然忘記了 (y2-1)這個坐標事實上可能不存在
所以二分查找找端點的時候掛了。。
BS我把本題加強版是 dhx學長 出的 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