1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

形式化题意:给定 mmm 个区间,若删除一个区间后总覆盖面积不变,求出可以被删除的区间数量。

前缀和+差分思想,计算 1∼n1 \sim n1∼n 中每个位置被覆盖的次数,进而求出被覆盖多次的位置。

最后扫一遍所有区间,若该区间内所有位置都被覆盖多次则计入答案。

c++

#include <bits/stdc++.h>

P1895.2024.8.17-第二题-种树

    1000ms Tried: 89 Accepted: 36 Difficulty: 5 所属公司 : 米哈游
    算法与标签>差分数组

题目内容

一条长度为n n n的公路上, 米小游站着 mm m名博物工, 其中第i i i位工人会给 [li,ri][l_i,r_i] [li​,ri​]这一段区间中的每个点都种上一棵树。

但由于每个点最多种一颗, 因此如果某些位工人发现自己要种的地方已经有树, 自己就会跳过这个点不管。

米小游为了节约成本,现在要恰好少雇佣一名工人,但同时他不希望少了此人会影响最终种树的结果,现在请你帮他算算有多少名工人都可以成为恰好少雇佣的这一名呢。

输入描述

第一行输入两个整数 n,m(1≤n≤2×105;1≤m≤105n, m (1 ≤n≤ 2 × 10^5; 1 ≤ m ≤ 10^5n,m(1≤n≤2×105;1≤m≤105) 代表公路长度和植树工人数量。

接下来输入m mm行, 每行输入两个正整数li,ri(1≤li≤ri≤n) l_i, r_i (1 ≤ l_i ≤ r_i ≤ n) li​,ri​(1≤li​≤ri​≤n)代表第i ii 位工人负责种树的区域。

输出描述

在一行上输出一个整数,代表有多少名工人可以被解雇。

5 3
1 4
1 2
3 4
3

说明

三名工人都可以成为被解雇的那一个。 最终的结果是: [1,1,1,1,0] (1表示有物, 0表示没有.) 解雇第一位工人, 神秘结果依然为 [1,1,1,1,0] : 不会影响结果。 解雇第二位工人, 依然不会影响结。 解雇第三位工人, 依然不会影响结果。

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 2, 30ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?