有域名自己做网站吗,c 做网站怎么截取前面的字符,网站开发软件设计文档模板,wordpress移动端缓存一、题目
1、题目描述 有 n 个区间#xff0c;第 i 个区间是 [l_i,r_i]#xff0c;它的长度是 r_i-l_i。 有 q 个询问#xff0c;每个询问给定 L,R,K#xff0c;询问被 [L,R] 包含的且长度不小于 K 的区间数量。 你想#xff0c;像这种板子题#xff0c;你随手写#x…一、题目
1、题目描述 有 n 个区间第 i 个区间是 [l_i,r_i]它的长度是 r_i-l_i。 有 q 个询问每个询问给定 L,R,K询问被 [L,R] 包含的且长度不小于 K 的区间数量。 你想像这种板子题你随手写不到十分钟就能 AC。 2、输入输出
2.1输入 第一行两个空格隔开的正整数 n,q。 接下来 n 行第 i 行有两个空格隔开的正整数 l_i,r_i。 接下来 q 行每行三个空格隔开的正整数 L,R,K表示一个询问。 2.2输出 共 q 行每行一个非负整数表示询问的答案。 3、原题链接
#6270. 数据结构板子题 - 题目 - LibreOJ (loj.ac) 二、解题报告
1、思路分析
看到这种区间问题不难想到应该要用分治
我们考虑[l, r]内长度不小于k的区间数目 [l, r]内总区间数目 - [l, r]内小于k的区间数目
那么我们先读入区间
然后读入询问我们把每个询问[l, r, k]拆成两个一个是[l, r, k - 1]一个是[l, r, r - l]
后者减去前者就是答案
具体操作时我们把区间和询问都按照区间长度升序排序然后开两个树状数组一个维护左端点左边的区间数目一个维护右端点左边的区间数目
然后双指针归并计算贡献即可
2、复杂度 时间复杂度O(nlog^2 n) 空间复杂度O(n) 3、代码详解
#include iostream
#include cstring
#include cstdio
#include algorithm
using namespace std;
const int N 5e5 10, inf 1e9 7;struct line
{int l, r, len;bool operator(const line x) const{return len x.len;}
} lines[N];
struct query
{int l, r, len, id;bool operator(const query x) const{return len x.len;}
} query[N 1];
int tot 0, n, m, ans[N 1], trR[N], trL[N];void addR(int x, int v)
{for (; x n; x (x -x))trR[x] v;
}
void addL(int x, int v)
{for (; x n; x (x -x))trL[x] v;
}
int askR(int x)
{int res 0;for (; x 0; x (x - 1))res trR[x];return res;
}
int askL(int x)
{int res 0;for (; x 0; x (x - 1))res trL[x];return res;
}int main()
{//freopen(in.txt, r, stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin n m;for (int i 1, l, r; i n; i)cin l r, lines[i] {l, r, r - l};for (int i 1, l, r, k; i m; i){cin l r k;tot, query[tot] {l, r, k - 1, tot};tot, query[tot] {l, r, r - l, tot};}sort(lines 1, lines 1 n), sort(query 1, query 1 tot);for (int i 1, p 1; i tot; i){while (p n lines[p].len query[i].len)addL(lines[p].l, 1), addR(lines[p].r, 1), p;if (query[i].len query[i].r - query[i].l)ans[query[i].id] askR(query[i].r) - askL(query[i].l - 1);elseans[query[i].id] inf;}for (int i 1; i m; i)cout max(0, ans[i 1] - ans[(i 1) - 1]) \n;return 0;
}
