题意：
给你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