www.cnblogs.com/shaokele/
1340: 矩形##
Time Limit: 1 Sec
Memory Limit: 128 MBDescription###
因为对polo忍无可忍， dzf使用圣剑在地上划出了许多纵横交错的沟壑来泄愤。这些沟壑都严格与X轴平行或垂直。
polo嘲笑了dzf无聊的行为，然后做了一件更加无聊的事。他蹲下来数这些沟壑的条数。数着数着，polo意识到一个问题，那就是因为圣剑的威力太大，划出的沟壑太多，地面就会塌陷。而如果两条水平的沟壑和两条垂直的沟壑相交组成了一个矩形，那么塌陷的危险就会进一步增加。现在polo已经数了n条沟壑，他想知道这些沟壑组成了多少个矩形。
Input###
第一行一个数n,接下来每行4个数x1,y1,x2,y2，表示沟壑的两个端点(x1,y1),(x2,y2)
Output###
一个数，组成的矩形个数。
Sample Input###
4
0 0 1 0
0 0 0 1
1 1 1 -1
1 1 0 1
8
1 0 4 0
2 1 2 0
0 0 0 3
2 2 2 3
3 3 3 -1
0 3 4 3
4 1 -1 1
3 2 -1 2
Sample Output
1
6
题目大意：
二位直角坐标系中有 n 条水平或竖直的线段
问能组成多少个矩形（相同方向的线段不交）
题解：
把所有的 (y) 坐标离散化
把所有的竖线按 (x) 排序
先 (O(n)) 枚举一条竖边，然后枚举与其相交的横边，把它的 (y) 坐标加入树状数组（在树状数组中的位置 (+1) ）。预处理完毕
枚举另一条竖边，先判断是否有横边的最右端的 (x) 坐标已经小于当前竖边的 (x) 坐标，找到这条边在树状数组中的位置，删去（在树状数组中的位置 (-1)
然后树状数组做区间查询， (ans) 用数学方法累加
~~然后 (AC) ~~ 妈的调了这么久
（树状数组单点修改，区间查询）
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int n,num,tmp,cnt,cnt1,cnt2,L,R,mid,res,id1,id2;
ll x1,y1,x2,y2,ans,up,down;
int c[5005],to[5005];
ll a[5005];
struct node1{
ll x,l,r;
}ver[5005];
struct node2{
ll y,l,r;
}tra[5005];
bool cmp1(node1 a,node1 b){
if(a.x<b.x)return 1;
else return 0;
}
bool cmp2(node2 a,node2 b){
if(a.r<b.r)return 1;
else return 0;
}
void add(int k,int tot){
for(int i=k;i<=tmp;i+=i&(-i))
c[i]+=tot;
}
int query(int k){
int res=0;
for(int i=k;i>0;i-=i&(-i))
res+=c[i];
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
if(x1==x2){
ver[++cnt1].x=x1;
ver[cnt1].l=min(y1,y2);
ver[cnt1].r=max(y1,y2);
a[++num]=y1;
a[++num]=y2;
}
if(y1==y2){
tra[++cnt2].y=y1;
tra[cnt2].l=min(x1,x2);
tra[cnt2].r=max(x1,x2);
a[++num]=y1;
}
}
sort(ver+1,ver+cnt1+1,cmp1);
sort(tra+1,tra+cnt2+1,cmp2);
sort(a+1,a+num+1);
tmp=1;
for(int i=2;i<=num;i++)
if(a[i]!=a[i-1])
a[++tmp]=a[i];
for(int i=1;i<=cnt1;i++){
memset(c,0,sizeof(c));
memset(to,0,sizeof(to));
cnt=0;
for(int j=1;j<=cnt2;j++)
if(tra[j].l<=ver[i].x && ver[i].x<=tra[j].r && ver[i].l<=tra[j].y && tra[j].y<=ver[i].r){
res=lower_bound(a+1,a+tmp+1,tra[j].y)-a;
to[++cnt]=j;
add(res,1);
}
int p=1;
for(int j=i+1;j<=cnt1;j++){
while(p<=cnt && ver[j].x>tra[to[p]].r){
res=lower_bound(a+1,a+tmp+1,tra[to[p]].y)-a;
p++;
add(res,-1);
}
if(p>cnt)break;
up=min(ver[i].r,ver[j].r);
down=max(ver[i].l,ver[j].l);
res=lower_bound(a+1,a+tmp+1,up)-a;
id1=res;
res=lower_bound(a+1,a+tmp+1,down)-a;
id2=res;
ll tot=query(id1)-query(id2-1);
if(tot>1)ans+=tot*(tot-1)/2;
}
}
printf("%lld
",ans);
return 0;
}