题目
https://cn.vjudge.net/problem/Kattis-pieceofcake
题意
给你n个矩形 问是否存在相交
思路
扫描线，从左向右扫，树状数组维护竖线有哪些横坐标，左边竖线先查询在添加，右边竖线先减去在查询
代码
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 100005;
int tree[4*maxn];
struct node
{int up,down,x,f;node(){};node(int a,int b,int c,int d){up = a;down = b;x = c;f = d;}bool operator<(node b) const{return x < b.x;}
}a[4*maxn];
int lb(int x)
{return x&-x;
}
int qur(int x)
{int ans = 0;while(x > 0){ans += tree[x];x -= lb(x);}return ans;
}
void add(int x,int data)
{while(x<=4*maxn){tree[x] += data;x += lb(x);}
}
int n;
int main()
{scanf("%d",&n);vector<int> v;for(int i = 1;i <= n;i++){int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);a[i] = node(y2,y1,x1,1);a[i+n] = node(y2,y1,x2,0);v.push_back(x1);v.push_back(y1);v.push_back(x2);v.push_back(y2);}sort(a+1,a+2*n+1);sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());ll ans = 0;for(int i = 1;i <= 2*n;i++){int up = lower_bound(v.begin(),v.end(),a[i].up) - v.begin() + 1;int down = lower_bound(v.begin(),v.end(),a[i].down) - v.begin() + 1;if(a[i].f){ans += qur(up) - qur(down);add(up,1);add(down,1);}else{add(up,-1);add(down,-1);ans += qur(up) - qur(down);}}if(ans > 0) printf("1\n");else printf("0\n");return 0;
}