CF-816B Karen and Coffee 题解

题目大意

给你n个范围，给你q个能力值范围，问在能力值范围中，有多少个能力是满足至少满足k个范围的。

解题思路

首先用差分，求出每个能力能够满足多少个范围。

之后刚开始用的暴力写的，直接超时了。。。

后面发现可以在遍历一遍，将满足条件的点用1标记，再跑一遍前缀和即可。

之前还真没写过跑两遍前缀和的题目。

学到了。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 5;
int sum[N], ans[N];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int m, k, q; cin >> m >> k >> q;
	int L = 1e9, R = -1e9;
	rep(i, 1, m) {
		int l, r; cin >> l >> r;
		sum[l]++, sum[r + 1]--;
		L = min(L, l), R = max(R, r);
	}
	rep(i, 1, 2e5+5) {
		sum[i] += sum[i - 1];
		if (sum[i] >= k)	ans[i]++;
	}
	rep(i, 1, 2e5+5) {
		ans[i] += ans[i - 1];
	}
	rep(i, 1, q) {
		int l, r; cin >> l >> r;
		cout << ans[r] - ans[l - 1] << endl;
	}
	return 0;
}