[LOJ 6270]数据结构板子题

Description

有n个区间，第i个区间是[li,ri]，它的长度是ri−li。

有q个询问，每个询问给定L,R,K，询问被[L,R]包含的且长度不小于K的区间数量。

你想，像这种板子题，你随手写，不到十分钟就能AC。

Input

第一行，两个空格隔开的正整数n,q。

接下来n行，第i行有两个空格隔开的正整数li,ri。

接下来q行，每行三个空格隔开的正整数L,R,K，表示一个询问。

Output

共q行，每行一个非负整数，表示询问的答案。

Sample Input

Sample Output

HINT

对于30%的数据，n,q≤5,000；

对于60%的数据，n,q≤50,000；

对于所有数据，n,q≤500,000，li,ri,L,R,K≤n，li<ri，L<R。

题解

我们考虑这样一个问题，在基于所有区间长度都不大于询问区间的条件下。被询问区间包含的区间个数 = 总个数-（区间左端点在询问区间左端点左端的个数 + 区间右端点在询问区间右端点右端的个数）。

那么我们考虑从小到大插入这些区间。在插入区间大小为询问区间的 $K_i-1$ 时，我们统计下答案。同时，在大小为 $R_i-L_i$ 时也统计一次答案。最终答案两次作差即可。

同时注意的是由于题目数据存在 $K_i > R_i-L_i$ 所以要特殊处理。

 1 //It is made by Awson on 2018.1.5
 2 #include <set>
 3 #include <map>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <queue>
 7 #include <stack>
 8 #include <cstdio>
 9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define lowbit(x) ((x)&(-(x)))
17 #define Max(a, b) ((a) > (b) ? (a) : (b))
18 #define Min(a, b) ((a) < (b) ? (a) : (b))
19 using namespace std;
20 const int N = 500000;
21 const int INF = ~0u>>1;
22 
23 int n, q;
24 struct bit_tree {
25     int c[N+5];
26     void add(int x, int val) {for (; x <= n; x += lowbit(x)) c[x] += val; }
27     int count(int x) {
28     int sum = 0;
29     for (; x; x -= lowbit(x)) sum += c[x];
30     return sum;
31     }
32 }L, R;
33 struct seq {
34     int l, r, k, id;
35     bool operator < (const seq &b) const {
36     return k < b.k;
37     }
38 }a[N+5], b[(N<<1)+5];
39 int cnt[(N<<1)+5];
40 
41 void work() {
42     scanf("%d%d", &n, &q);
43     for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].k = a[i].r-a[i].l;
44     for (int i = 1, tot = 0; i <= q; i++) {
45     ++tot, scanf("%d%d%d", &b[tot].l, &b[tot].r, &b[tot].k), --b[tot].k, b[tot].id = tot;
46     ++tot, b[tot].l = b[tot-1].l, b[tot].r = b[tot-1].r, b[tot].k = b[tot].r-b[tot].l, b[tot].id = tot;
47     }
48     sort(a+1, a+n+1), sort(b+1, b+(q<<1)+1);
49     int loc = 1;
50     for (int i = 1; i <= (q<<1); i++) {
51     while (loc <= n && a[loc].k <= b[i].k) L.add(a[loc].l, 1), R.add(a[loc].r, 1), ++loc;
52     if (b[i].k <= b[i].r-b[i].l) cnt[b[i].id] = R.count(b[i].r)-L.count(b[i].l-1);
53     else cnt[b[i].id] = INF;
54     }
55     for (int i = 1; i <= q; i++) printf("%d
", Max(cnt[2*i]-cnt[2*i-1], 0));
56 }
57 int main() {
58     work();
59     return 0;
60 }