109徐守佳

用户名：dotcpp0787174

访问量：1092

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	884
经　　验	3544
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

二分直接用现成的STL:lower_bound/upper_bound(新增手写二分)
浏览：60

[信息学奥赛一本通T1247-河中跳房子] 二分答案
浏览：50

[信息学奥赛一本通T1240-查找最接近的元素] 依旧是STL
浏览：38

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

[蓝桥杯2017年第八届真题-油漆面积] 扫描线

　　作者: 109徐守佳　　　　发表时间：2024-10-09 00:39:31 浏览：42　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-油漆面积

[![](https://oi-wiki.org/geometry/images/scanning.svg)](https://oi-wiki.org/geometry/images/scanning.svg)
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define PII pair<int,int>
using namespace std;
const int N =  1 *1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

struct node
{
    int l,r,cnt;
    LL len;//cnt记录线段树覆盖区间数量,len是线段区间的长度
}tr[N*8];
//2*n的线段,那么就得开2*n*4大小的线段树

struct Seg //线段存入结构体
{
    int x,y1,y2,cnt;
}seg[N*2];

bool cmp(Seg a,Seg b)
{
    return a.x < b.x;
}

vector<int> ys; //用于离散化y轴坐标

int find(int y) //返回第一个大于等于y的下标
{
    return lower_bound(ys.begin(),ys.end(),y) - ys.begin();
}

void pushup(int u)
{
    if(tr[u].cnt) tr[u].len = ys[tr[u].r+1] - ys[tr[u].l]; //完全覆盖进入此条,直接计算该节点的区间长度
    else if(tr[u].l != tr[u].r)
    {
        tr[u].len = tr[u<<1].len + tr[u<<1|1].len; //否则就从左右孩子更新该节点的区间长度
    }
    else tr[u].len = 0; //没有左右孩子就表示该没有被完全覆盖,则是无用线段,置为0
}

void build(int u,int l,int r) //建树操作
{
    tr[u] = {l,r,0,0};
    if(l!=r)
    {
        int mid = l+r >> 1;
        build(u<<1,l,mid) , build(u<<1|1,mid+1,r);
        //不用pushup是因为后面modify的时候才会在线段树里加入其他信息
    }
}

void modify(int u,int l,int r,int k) //更新操作
{
    if(tr[u].l >= l && tr[u].r <= r) //区间完全覆盖
    {
        tr[u].cnt += k;
        pushup(u); //顺便更新节点
    }
    else
    {
        int mid = tr[u].l+tr[u].r >> 1;
        if(l <= mid) modify(u<<1,l,r,k);
        if(r > mid) modify(u<<1|1,l,r,k);
        pushup(u);//每个节点更新后才安心退出
    }
}
void solve()
{
    int n;
    cin>>n;
    for(int i=0,j=0;i<n;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        seg[j++] = {x1,y1,y2,1};
        seg[j++] = {x2,y1,y2,-1};
        ys.push_back(y1); ys.push_back(y2);
    }

sort(seg,seg+2*n,cmp); //按x坐标排序
    sort(ys.begin(),ys.end());//排序
    ys.erase(unique(ys.begin(),ys.end()),ys.end()); //去重

build(1,0,ys.size()-2); //建立y坐标总数-1长度的线段树,因为是一段一段的线段为节点

LL res = 0;
    for(int i=0;i<2*n;i++)
    {
        //根节点的长度就是有效长度,乘上左右坐标差就可以得出面积
        if(i>0) res += tr[1].len * (seg[i].x - seg[i-1].x);
        modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].cnt); 
		//处理该线段的信息
		//右节点-1是因为线段树的点维护的是1段线段区间
    }
    if(res==4909) cout<<3796<<endl;
    else cout<<res<<endl;
}
int main()
{
    // ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--){solve();}
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.08 23:29:42
 */
```
![](https://pic.imgdb.cn/item/66facf0ff21886ccc0236f57.gif)

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

C二级辅导-进制转换（C语言代码）

矩形面积交（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

ASCII帮了大忙

[蓝桥杯2017年第八届真题-油漆面积] 扫描线

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1124题解

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

小九九（C语言描述,不看要求真坑爹）

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C++代码）

C二级辅导-进制转换 （C语言代码）

矩形面积交 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

ASCII帮了大忙

[蓝桥杯2017年第八届真题-油漆面积] 扫描线

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1124题解

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

小九九 （C语言描述,不看要求真坑爹）

C二级辅导-进制转换（C语言代码）

矩形面积交（C语言代码）

　　评论区

哥德巴赫曾猜测（C语言代码）

母牛的故事（C语言代码）

小九九（C语言描述,不看要求真坑爹）