Codeforces 1197E Count The Rectangles(树状数组+扫描线)

题意：

给你n条平行于坐标轴的线，问你能组成多少个矩形，坐标绝对值均小于5000

保证线之间不会重合或者退化

思路：

从下到上扫描每一条纵坐标为y的水平的线，然后扫描所有竖直的线并标记与它相交的线，保证上端至少多出1

并用树状数组维护它们

然后从y+1网上扫描纵坐标为yy的水平的线，查询y到yy中同时与他们相交的竖直的线的条数算贡献即可

每查询完一个yy后，要在树状数组内删除上端点为yy的竖直的线，因为以后的yy与它不会再相交了

代码：

几乎是照着官方题解来的。。

#include<iostream>

#include<cstdio>

#include<algorithm>

//#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 1e4+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

//const db pi = acos(-1.0);

int n;

struct node{

    int l,r;

    int x;

    node(){}

    node(int a,int b,int c):l(a),r(b),x(c){}

};

vector<node>vt[maxn],hr[maxn];

vector<int>tmp[maxn];

int tree[maxn*];

int lowbit(int x){

    return x&-x;

}

void add(int x,int C){

    for(int i=x;i<maxn-;i+=lowbit(i)){

        tree[i]+=C;

    }

}

int sum(int x){

    int ans=;

    for(int i=x;i;i-=lowbit(i)){

        ans+=tree[i];

    }

    return ans;

}

int main(){

    scanf("%d", &n);

    for(int i = ; i <= n; i++){

        int x1,y1,x2,y2;

        scanf("%d %d %d %d" ,&x1, &y1, &x2, &y2);

        x1+=;x2+=;

        y1+=;y2+=;

        if(x1==x2){

            vt[x1].pb(node(min(y1,y2),max(y1,y2),x1));

        }

        else{

            hr[y1].pb(node(min(x1,x2),max(x1,x2),y1));

            //printf("===%d\n",y1-5000);

        }

    }

    ll ans = ;

    for(int y = ; y < maxn-; y++){

        for(int i = ; i < hr[y].size(); i++){

            //for(int j = 0; j < maxn-10; j++)tmp[j].clear();

            //mem(tree,0);

            node lne = hr[y][i];

            int l = lne.l, r = lne.r;

            for(int x = l; x <= r; x++){

                for(int j = ; j < (int)vt[x].size(); j++){

                    if(vt[x][j].l<=y&&vt[x][j].r>=y+){

                        add(x,);

                        tmp[vt[x][j].r].pb(x);

                    }

                }

            }

            for(int yy = y+; yy < maxn-; yy++){

                for(int j = ; j < (int)hr[yy].size(); j++){

                    ll res = sum(hr[yy][j].r)-sum(hr[yy][j].l-);

                    ans+=res*(res-)/;

                }

                for(int j = ; j < (int)tmp[yy].size(); j++){

                    add(tmp[yy][j],-);

                }

                tmp[yy].clear();

            }

        }

    }

    printf("%lld",ans);

    return ;

}

/*

 */

巴特西

Codeforces 1197E Count The Rectangles(树状数组+扫描线)

最新文章

热门文章