HDU 5862Counting Intersections (思维+树状数组）

57 阅读 0 评论 38 点赞

我是靠谱客的博主优美小霸王，最近开发中收集的这篇文章主要介绍HDU 5862Counting Intersections (思维+树状数组），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实际上这种在左端点+1，右端点的下一个-1的题目已经见过很多了。适用于它的查询也是一个区间的。+1，-1相当于维护了一个区间的“高度”，因为查询也是区间的，只要这个区间某一个点的高度被+1了，那这个区间之前的更新就被“捕捉”到了，所以每次对这个区间求和就知道有多少个“交点”。

在这题，可以淡化横向线段的“线”，只保留两个端点，在y轴上，左端点（相当于开始）+1，右端点的下一个-1（结束）；遇到竖向的，就查询[y1,y2]之间有多少个1。这个更新查询很自然的想到用树状数组来做，因为y可以达到1<<32，而n只有1e5，所以要离散化。

网上看到写的特别好的代码，我也是仿照他写的

【代码】

/* ***********************************************
Author        :angon

************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define showtime fprintf(stderr,"time = %.15fn",clock() / (double)CLOCKS_PER_SEC)
#define lld %I64d
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scanl(d) scanf("%I64d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define scannl(n,m) scanf("%I64d%I64d",&n,&m)
#define mst(a,k)  memset(a,k,sizeof(a))
#define LL long long
#define N 100005
#define mod 1000000007
inline int read(){int s=0;char ch=getchar();for(; ch<'0'||ch>'9'; ch=getchar());for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';return s;}

struct node
{
    int type,x,y1,y2;
}t[N*2];  //点
int a[N*2];  
bool cmp(node n1,node n2)
{
    if(n1.x==n2.x) return n1.type<n2.type;
    return n1.x<n2.x;  //按x排序
}
int lowbit(int x)
{
    return x & (-x);
}
int Maxn;
int c[N*2];
void modify (int x,int add) {   //在x位置加上add，要修改所有祖先
    while(x<=Maxn)
    {
        c[x]+=add;
        x+=lowbit(x);
    }
}
int get_sum(int x)  //统计前x项的和
{
    int ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
map<int,int>mp;


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T; scan(T);
    while(T--)
    {
        int n,x1,y1,x2,y2;
        scan(n);
        int tot=0,all=0;
        while(n--)
        {
            scann(x1,y1);scann(x2,y2);
            if(x1==x2)  //竖
            {
                if(y1>y2) swap(y1,y2);
                t[tot++] = {1,x1,y1,y2};  //x1实际上没什么用
                a[all++] = y1;
                a[all++] = y2;
            }
            else //横
            {
                if(x1>x2) swap(x1,x2);
                t[tot++] = {0,x1,y1,1};  //左端点+1
                t[tot++] = {0,x2+1,y2,-1};  //右端点的下一个-1
                a[all++] = y1;
            }
        }
        sort(a,a+all);
        mp.clear();
        Maxn=1;
        for(int i=0;i<all;i++)  //树状数组是在y轴上操作的，对y离散化
        {
            if(!mp[a[i]]) mp[a[i]]=Maxn++;
        }
        sort(t,t+tot,cmp);
        mst(c,0);
        LL ans=0;
        for(int i=0;i<tot;i++)   //之前巧妙的把y2设为1和-1，可以少写很多判断
        {
            if(t[i].type==0)
            {
                modify(mp[t[i].y1],t[i].y2);
            }
            else
            {
                ans += get_sum(mp[t[i].y2])-get_sum(mp[t[i].y1]-1);
            }
        }
        printf("%lldn",ans);
    }
    return 0;
}