题意分析

问题背景

现代建筑的屋顶垂直剖面由若干倾斜线段构成，下雨时雨滴垂直落下，需计算每条线段承接的雨水量。雨水会从线段较低端点流走，若流到其他线段端点，对应线段收集这部分雨水，最终要得出每条线段在1秒内承接的雨水量（因每秒每平方米落1升雨，雨水量等于承接雨水的水平投影面积）。

输入输出理解

• 输入：第一行是线段数量n（范围(1 \leq n \leq 40000) ），后续n行每行是线段端点坐标x1, y1, x2, y2，满足0 ≤ x1, y1, x2, y2 ≤ 1000000，x1 < x2，y1 ≠ y2，且线段间无交点、无水平线段。
• 输出：n行，每行对应线段1秒内承接的雨水量（单位：升 ）。

核心需求

确定每条线段被上方线段的遮挡情况，计算其实际承接雨水的水平投影面积，以此得到雨水量。

解题思路

1. 离散化处理：由于线段端点的x坐标范围大（最大到(10^6) ），收集所有线段的x1和x2，排序去重后映射到小索引范围，降低后续线段树操作的空间和时间复杂度。
2. 线段排序：依据线段在垂直方向的覆盖关系排序，让更可能遮挡下方线段的线段优先处理。通过复杂比较逻辑，判断线段x坐标交叉情况、计算交叉点高度等，确定排序顺序，保证处理顺序能正确模拟遮挡关系。
3. 线段树维护：利用线段树维护两个关键信息，sum1记录未被遮挡区域的水平长度，sum2记录已分配雨水的区域长度。通过覆盖（标记遮挡区域）、更新（记录雨水分配情况 ）、查询（获取特定区间的长度信息 ）操作，模拟雨水承接的过程。
4. 逐线段处理：对每条线段，先查询其水平区间内可承接雨水的面积（sum1与sum2查询结果之和 ），标记该区间被遮挡，再根据线段高低端点，将承接的雨水量更新到线段树对应位置，供后续线段计算时使用。

标程

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int Max = 100000;

typedef long long LL;

typedef struct node
{
    LL x1,y1;

    LL x2,y2;

    int Id;

    bool operator < (const node &b)const
    {
        if(b.x1>=x1&&b.x1<=x2)
        {
            double y = (double)((y2-y1)*(b.x1- x1))/(x2-x1)+y1;

            return y>(double)b.y1;
        }

        if(b.x2>=x1&&b.x2<=x2)
        {
            double y = (double)((y2-y1)*(b.x2-x1))/(x2-x1)+y1;

            return y>(double)b.y2;
        }
        return min(y1,y2)==min(b.y1,b.y2)?x2<b.x1:min(y1,y2)>min(b.y1,b.y2);
    }

}Point ;

Point P[Max];

typedef struct Node
{
    LL sum1;

    LL sum2;

    bool flag1,flag2;
}Tree;

Tree Tr[Max*8];

int n;

LL a[Max*3];

int Hash[Max*3];

int num ;

int Bound(int l,int r,int d)
{
    while(l<=r)
    {

        int mid = (l+r)>>1;

        if(Hash[mid]==d)
        {
            return mid;
        }

        if(Hash[mid]>d)
        {
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    return 0;
}


void PushUp(int st)
{
    Tr[st].sum1 = Tr[st<<1].sum1+Tr[st<<1|1].sum1;

    Tr[st].sum2 = Tr[st<<1].sum2+Tr[st<<1|1].sum2;
}

void PushDown(int st)
{
    if(Tr[st].flag1)
    {
        Tr[st<<1].sum1 = Tr[st<<1|1].sum1 = Tr[st].sum1;

        Tr[st<<1].flag1 = Tr[st<<1|1].flag1 = true;

        Tr[st].flag1 = false;
    }

    if(Tr[st].flag2)
    {
        Tr[st<<1].sum2 = Tr[st<<1|1].sum2 =Tr[st].sum2;

        Tr[st<<1].flag2 = Tr[st<<1|1].flag2 = true;

        Tr[st].flag2= false;
    }
}

void BuildTree(int L,int R,int st)
{
    Tr[st].flag1 = false;

    Tr[st].flag2 = false;

    if(L == R)
    {
        Tr[st].sum1 = Hash[L]-Hash[L-1];

        Tr[st].sum2 = 0;

        return ;
    }
    int mid = (L+R)>>1;

    BuildTree(L,mid,st<<1);

    BuildTree(mid+1,R,st<<1|1);

    PushUp(st);
}

void Cover1(int L,int R,int st,int l,int r)
{

    if(l==L&&r==R) 
    {
        Tr[st].flag1= true;

        Tr[st].sum1 = 0 ;

        return ;
    }

    PushDown(st);

    int mid = (L+R) >> 1;

    if(r<=mid) Cover1(L,mid,st<<1,l,r);

    else if(l>mid) Cover1(mid+1,R,st<<1|1,l,r);

    else
    {
        Cover1(L,mid,st<<1,l,mid);

        Cover1(mid+1,R,st<<1|1,mid+1,r);
    }
    PushUp(st);
}
void Cover2(int L,int R,int st,int l,int r)
{

    if(l==L&&r==R) 
    {
        Tr[st].flag2 = true;

        Tr[st].sum2 = 0 ;

        return ;
    }

    PushDown(st);

    int mid = (L+R) >> 1;

    if(r<=mid) Cover2(L,mid,st<<1,l,r);

    else if(l>mid) Cover2(mid+1,R,st<<1|1,l,r);

    else
    {
        Cover2(L,mid,st<<1,l,mid);

        Cover2(mid+1,R,st<<1|1,mid+1,r);
    }
    PushUp(st);
}

void Update(int L,int R,int st,int x,int d)
{
    if(L == R) 
    {
        Tr[st].sum2 = d;

        return ;
    }

    PushDown(st);

    int mid = (L+R)>>1;

    if(x<=mid) Update(L,mid,st<<1,x,d);

    else Update(mid+1,R,st<<1|1,x,d);

    PushUp(st);
}

LL Query1(int L,int R,int st,int l,int r)
{
    if(l==L&&r==R) return Tr[st].sum1;

    PushDown(st);

    int mid = (L+R)>>1;

    if(r<=mid) return Query1(L,mid,st<<1,l,r);

    else if(l>mid) return Query1(mid+1,R,st<<1|1,l,r);

    else return Query1(L,mid,st<<1,l,mid)+Query1(mid+1,R,st<<1|1,mid+1,r);
}


LL Query2(int L,int R,int st,int l,int r)
{
    if(l==L&&r==R) return Tr[st].sum2;

    PushDown(st);

    int mid = (L+R)>>1;

    if(r<=mid) return Query2(L,mid,st<<1,l,r);

    else if(l>mid) return Query2(mid+1,R,st<<1|1,l,r);

    else return Query2(L,mid,st<<1,l,mid)+Query2(mid+1,R,st<<1|1,mid+1,r);
}
int main()
{
    while(~scanf("%d",&n))
    {
        num = 0;

        for(int i = 0; i<n;i++)
        {
            scanf("%lld %lld %lld %lld",&P[i].x1,&P[i].y1,&P[i].x2,&P[i].y2);

            a[num++] = P[i].x1; a[num++] = P[i].x2;

            P[i].Id = i;
        }

        sort(P,P+n);

        sort(a,a+num);

        int ant = 1;

        Hash[1]=a[0];

        Hash[0]=a[0];

        for(int i = 1;i<num;i++)
        {
            if(a[i]!=a[i-1])
            {
                Hash[++ant] = a[i];
            }
        }

        BuildTree(1,ant,1);

        for(int i = 0;i<n;i++)
        {
            int L = Bound(1,ant,P[i].x1);

            int R = Bound(1,ant,P[i].x2);


            a[P[i].Id] = Query1(1,ant,1,L+1,R)+Query2(1,ant,1,L,R);

            Cover1(1,ant,1,L+1,R);

            Cover2(1,ant,1,L,R);

            if(P[i].y1>P[i].y2)
            {
                Update(1,ant,1,R,a[P[i].Id]);
            }
            else
            {
                Update(1,ant,1,L,a[P[i].Id]);
            } 
        }
        for(int i = 0;i<n;i++)
        {
            printf("%lld\n",a[i]);
        }
    }
    return 0;
}

代码通过randInt函数生成指定范围的随机整数，先随机生成线段数量n，再循环生成n条线段的端点坐标，满足题目输入要求，可用于验证解题代码的正确性，可根据实际需求调整坐标范围和测试用例数量。