题意：给定n个区间和q组询问区间，每次询问某个区间内有多少个数字被k个或k个以上的重叠区间覆盖。 解法：因为这一题的数字值域范围很小，很清晰的可以想到应该是要统计每个数字有多少个区间覆盖，这一步可以使用差分实现，而最最关键的是后面这步，现在对于每个数字我们都能知道它被多少个区间覆盖，但是询问的是一个区间内>=k的数字有多少个，知道分块可以做，但是时间可能卡不过去？毕竟2e5，其实能过，常数较小 ，转念一想，觉得这肯定是某数据结构，于是就去百度“询问一个区间内大于等于k的数字有多少个” ，看到了熟悉的某可持久化数据结构，这可是div2的B题啊，重来没见过这个地方考分块或者主席树（主席树还要加二分）的，其实就套个前缀和就好了，每个>=k的数字标记为1，其他是0，做一次前缀和…是不是秒懂…人傻了…经历了一场从南到北的思想风暴，一个好的思维真的能大大减少代码量。 代码：
#include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <cstdio> #include <queue> #include <cmath> #include <set> #include <map> #include<bitset> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define PI acos(-1) #define eps 1e-9 #define rint register int #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long LL; typedef pair<LL, int> pli; typedef pair<int, int> pii; typedef pair<double, int> pdi; typedef pair<LL, LL> pll; typedef pair<double, double> pdd; typedef map<int, int> mii; typedef map<LL, int> mli; typedef map<char, int> mci; typedef map<string, int> msi; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1}; const int INF = 0x3f3f3f3f; const int N = 2e5+10; const LL Mod = 1e9+7; const int M = 3e5+10; int n, k, q; int sum[N]; int main() { scanf("%d %d %d", &n, &k, &q); int l, r; _rep(1, n, i) { scanf("%d %d", &l, &r); ++sum[l]; --sum[r+1]; } //第一次前缀和 _for(1, N, i) { sum[i] += sum[i-1]; if(sum[i-1] >= k) sum[i-1] = 1; else sum[i-1] = 0; } //第二次前缀和 _for(1, N, i) sum[i] += sum[i-1]; while(q--) { scanf("%d %d", &l, &r); printf("%d\n", sum[r] - sum[l-1]); } return 0; }