109徐守佳

用户名：dotcpp0787174

访问量：995

签　名：

想AC的我戴上了WA面具

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

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1547-区间和]-分块写法
浏览：15

你可能喜欢

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

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

　　作者: 109徐守佳　　　　发表时间：2024-10-09 00:39:31 浏览：40　|　评论：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语言程序设计教程（第三版）课后习题7.4 （C语言代码）

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

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

【绝对值排序】（C++代码）

关于C语言变量位置的问题

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

评论区

精彩推荐

DNA （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

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

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

简单的a+b （C语言代码）

采药（C语言代码）

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

数字统计（C语言代码）

永远的丰碑（C++代码）

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

109徐守佳

TA的其他文章

你可能喜欢

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

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

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

【绝对值排序】 （C++代码）

关于C语言变量位置的问题

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

评论区

精彩推荐

DNA （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

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

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

简单的a+b （C语言代码）

采药 （C语言代码）

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

数字统计 （C语言代码）

永远的丰碑 （C++代码）

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

【绝对值排序】（C++代码）

　　评论区

采药（C语言代码）

数字统计（C语言代码）

永远的丰碑（C++代码）

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