我是靠谱客的博主 专一黑裤,最近开发中收集的这篇文章主要介绍HDU 5862 Counting Intersections(树状数组),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题意:给你n条平行x或y轴的线段,保证没有公共端点 没有覆盖,问有多少交点。


思路:对所有线段按x坐标排序,将y坐标离散化,将水平线段拆成两部分,左端点一个,右端点+1一个, 枚举所有线段遇到水平线段的左端点,对应y坐标在树状数组中的值+1,遇到水平线段的(右端点+1)时,将其对应y坐标在树状数组中的值-1.遇到竖直线段时,查询其纵坐标区间的和,也就是条竖直线段能产生的交点的个数.


代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
struct node
{
    int type, x, y1, y2;
    node() {}
    node(int tt, int xx, int yy1, int yy2): type(tt), x(xx), y1(yy1), y2(yy2) {}
    bool operator < (const node &a) const
    {
        if(x == a.x) return type < a.type;
        else return x < a.x;
    }
}a[maxn];

int Hash[maxn], tree[maxn];

int lowbit(int x)
{
    return x&(-x);
}

void update(int pos, int val)
{
    while(pos < maxn)
    {
        tree[pos] += val;
        pos += lowbit(pos);
    }
}

int query(int pos)
{
    int res = 0;
    while(pos)
    {
        res += tree[pos];
        pos -= lowbit(pos);
    }
    return res;
}

int main(void)
{
    int _, n, cnt, hash_cnt;
    cin >> _;
    while(_--)
    {
        cnt = hash_cnt = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if(y1 == y2)
            {
                if(x1 > x2) swap(x1, x2);
                a[cnt++] = node(0, x1, y1, 1);
                a[cnt++] = node(0, x2+1, y1, -1);
                Hash[hash_cnt++] = y1;
            }
            else
            {
                if(y1 > y2) swap(y1, y2);
                a[cnt++] = node(1, x1, y1, y2);
                Hash[hash_cnt++] = y1;
                Hash[hash_cnt++] = y2;
            }
        }
        sort(Hash, Hash+hash_cnt);
        int id = 1;
        map<int, int> m;
        for(int i = 0; i < hash_cnt; i++)
            if(!m[Hash[i]])
                m[Hash[i]] = id++;
        sort(a, a+cnt);
        memset(tree, 0, sizeof(tree));
        ll ans = 0;
        for(int i = 0; i < cnt; i++)
        {
            if(a[i].type)
                ans += query(m[a[i].y2])-query(m[a[i].y1]-1);
            else
                update(m[a[i].y1], a[i].y2);
        }
        printf("%lldn", ans);
    }
    return 0;
}


最后

以上就是专一黑裤为你收集整理的HDU 5862 Counting Intersections(树状数组)的全部内容,希望文章能够帮你解决HDU 5862 Counting Intersections(树状数组)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(50)

评论列表共有 0 条评论

立即
投稿
返回
顶部