---
title: "合格数"
created: 2025-11-28
tags:
  - 算法
---

# 合格数

## 题目 [合格数](https://www.acwing.com/problem/content/description/5270/)

![[image-c8359c17.png]]

## 思路分析

![[image-e8e662a9.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;
int n,k,q;
int b[N],s[N];

int main()
{
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        b[l]++;
        b[r+1]--;
    }

    b[1]-=k;

    for(int i=1;i<=N;i++)
        b[i]+=b[i-1];

    for(int i=1;i<=N;i++)
        if(b[i]>=0)
            b[i]=1;
        else
            b[i]=0;

    // for(int i=1;i<=N;i++)
    //     if(b[i]<k)
    //         b[i]=0;
    //     else
    //         b[i]=1;

    for(int i=1;i<=N;i++)
        s[i]=s[i-1]+b[i];

    while(q--)
    {
        int l,r;
        cin>>l>>r;

        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}
```

## 同类题型

## 视频讲解


---
⬅️ [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/差分/借教室|借教室]] 🏠 [[00-刷题理模型]] ➡️ [[增减序列|增减序列]]