【EDU68 E】 Count The Rectangles 数据结构算几何

CF

 # 题意

总共有5000条线段，这些线段要么水平，要么垂直，问这些线段组成了多少矩形。

# 思路

这是一个n*n*（log）的思路

自己一开始想着枚举两条垂直边，想着怎么把水平的边插入，再进行冗斥等数出与两边都相交的数量。但是做不出来。

后来学习了如图的思路。

我们枚举垂直边，对于i 来说，因为三条红线与i 有交点，我们就标记三条红线。然后枚举剩下垂直边j ，k。如果这些垂直边与红线相交，就把对答案的贡献算进去。

具体实现可以用树状数组优化：算垂直边与红线交点个数。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr<<#x << " := " << x << endl;
#define bug cerr<<"-----------------------"<<endl;
#define FOR(a, b, c) for(int a = b; a <= c; ++ a)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
 
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(ll &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
 
 
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
 
const int inf = 0x3f3f3f3f;
 
const int mod = 1e9+7;
 
/**********showtime************/
            const int maxm = 6250009;
            const int maxn = 5009;
            struct Q{
                int le,ri;
                int up,down;
            } qujian[maxm];
            struct VER{     //垂直
                int x;
                int y1,y2;
            }ver[maxn];
            struct HOR{     //水平
                int y;
                int x1,x2;
            }hor[maxn];
            bool cmpv(VER a, VER b){
                return a.x < b.x;
            }
            bool cmph(HOR a, HOR b){
                return a.x2 < b.x2;
            }
            const int N = 2 * maxn;
            ll sum[N];
            int lowbit(int x) {
                return x & (-x);
            }
            void update(int x, int val) {
                while(x <= N){
                    sum[x] += val;
                    x += lowbit(x);
                }
            }
            ll getsum(int x) {
                ll res = 0;
                while(x > 0) {
                    res += sum[x];
                    x -= lowbit(x);
                }
                return res;
            }
            ll C(ll v) {
                return (v * (v-1)/ 2);
            }
int main(){
            int n;  scanf("%d", &n);
            int totv = 0, toth = 0;
            for(int i=1; i<=n; i++) {
                int x1,x2,y1,y2;
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                x1 += 5001; y1 += 5001; x2 += 5001; y2 += 5001;
                if(x1 == x2) {
                    ver[++totv].x = x1;
                    ver[totv].y1 = min(y1, y2);
                    ver[totv].y2 = max(y1, y2);
                }
                else {
                    hor[++toth].y = y1;
                    hor[toth].x1 = min(x1, x2);
                    hor[toth].x2 = max(x1, x2);
                }
            }
 
            sort(ver+1, ver+1+totv, cmpv);
            sort(hor+1, hor+1+toth, cmph);
 
            ll ans = 0;
            for(int i=1; i<=totv; i++) {
                queue<int>que;
                memset(sum, 0, sizeof(sum));
                for(int j=1; j<=toth; j++) {
                    if(hor[j].y <= ver[i].y2 && hor[j].y >= ver[i].y1) {
                        if(hor[j].x1 <= ver[i].x) {
                            que.push(j);
                            update(hor[j].y, 1);
                        }
                    }
                }
 
                for(int j=i+1; j<=totv; j++) {
                    while(!que.empty() && hor[que.front()].x2 < ver[j].x) {
                        update(hor[que.front()].y, -1);
                        que.pop();
                    }
                    ans += C(getsum(ver[j].y2) - getsum(ver[j].y1-1));
                }
            }
            printf("%lld
", ans);
            return 0;
}

（感想：自己对n^2枚举的理解过于简单。这道题中第一层n遍历中 其实套了两个n的遍历。值得学习）