[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$ 所以要特殊处理。

 //It is made by Awson on 2018.1.5

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define lowbit(x) ((x)&(-(x)))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 using namespace std;

 const int N = ;

 const int INF = ~0u>>;

 int n, q;

 struct bit_tree {

     int c[N+];

     void add(int x, int val) {for (; x <= n; x += lowbit(x)) c[x] += val; }

     int count(int x) {

     int sum = ;

     for (; x; x -= lowbit(x)) sum += c[x];

     return sum;

     }

 }L, R;

 struct seq {

     int l, r, k, id;

     bool operator < (const seq &b) const {

     return k < b.k;

     }

 }a[N+], b[(N<<)+];

 int cnt[(N<<)+];

 void work() {

     scanf("%d%d", &n, &q);

     for (int i = ; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].k = a[i].r-a[i].l;

     for (int i = , tot = ; i <= q; i++) {

     ++tot, scanf("%d%d%d", &b[tot].l, &b[tot].r, &b[tot].k), --b[tot].k, b[tot].id = tot;

     ++tot, b[tot].l = b[tot-].l, b[tot].r = b[tot-].r, b[tot].k = b[tot].r-b[tot].l, b[tot].id = tot;

     }

     sort(a+, a+n+), sort(b+, b+(q<<)+);

     int loc = ;

     for (int i = ; i <= (q<<); i++) {

     while (loc <= n && a[loc].k <= b[i].k) L.add(a[loc].l, ), R.add(a[loc].r, ), ++loc;

     if (b[i].k <= b[i].r-b[i].l) cnt[b[i].id] = R.count(b[i].r)-L.count(b[i].l-);

     else cnt[b[i].id] = INF;

     }

     for (int i = ; i <= q; i++) printf("%d\n", Max(cnt[*i]-cnt[*i-], ));

 }

 int main() {

     work();

     return ;

 }