网站建设和程序开发哪个好,东莞企业网站推广技巧,做网站去什么公司好,seo主要做什么一、题目
1、题目描述
在一维数轴上#xff0c;小蓝画了 n n n 个闭区间线段#xff0c;小桥会多次询问你#xff0c;每次给定两个点 a , b a, b a,b#xff0c;问有多少个区间包含 a a a 点#xff0c;但是不包含 b b b 点。
输入格式
第一行输入两个整数 n , q…一、题目
1、题目描述
在一维数轴上小蓝画了 n n n 个闭区间线段小桥会多次询问你每次给定两个点 a , b a, b a,b问有多少个区间包含 a a a 点但是不包含 b b b 点。
输入格式
第一行输入两个整数 n , q n, q n,q n n n 代表区间个数 q q q 代表询问个数。
接下来 n n n 行每行两个整数 l i , r i l_i, r_i li,ri代表一个左右端点为 l i , r i l_i, r_i li,ri 的闭区间。
接下来 q q q 行每行两个整数 a i , b i a_i, b_i ai,bi代表询问存在多少个区间包含 a i a_i ai 点但不包含 b i b_i bi 点。
输出格式
输出 q q q第 i i i 行代表第 i i i 个询问的答案。
样例输入
4 3
1 3
2 5
3 7
4 8
1 5
2 9
5 1样例输出
1
2
3评测数据范围 1 ≤ n ≤ 2 × 1 0 5 1 \le n \le 2 \times 10^5 1≤n≤2×105 1 ≤ q ≤ 2 × 1 0 5 1 \le q \le 2 \times 10^5 1≤q≤2×105 1 ≤ l i r i ≤ 2 × 1 0 5 1 \le l_i \lt r_i \le 2 \times 10^5 1≤liri≤2×105 1 ≤ a i , b i ≤ 2 × 1 0 5 1 \le a_i,b_i \le 2 \times 10^5 1≤ai,bi≤2×105
2、基础框架
#include iostream
using namespace std;
int main()
{// 请在此输入您的代码return 0;
}3、原题链接
奇怪的线段
二、解题报告
1、思路分析
先思考弱化版本如果只有一个点即仅仅考虑覆盖 a a a 点的区间有多少个。
考虑离线算法我们对于每一个区间的左端点维护一个 vector 容器装下对应的右端点同时维护一个全局的线段树从左向右扫描扫描到一个区间的左端点时将对应的右端点加入到线段树中当扫描到一个右端点时将右端点从线段树中移除到扫描到一个 a a a 时查询线段树中节点数量即为答案。
那么此题相似只不过查询的不是全局区间和而是局部区间和。
具体如下总共分为三种情况 如果 a b a b ab 答案为 0 0 0。 如果 a b a \lt b ab 对区间按照左区间排序从左向右扫描并且维护一个区间和线段树扫描到一个区间的左端点时将对应的右端点加入到线段树中当扫描到一个右端点时将右端点从线段树中移除到扫描到一个 a a a 时查询线段树中 [ a , b ) [a, b) [a,b) 的区间和即为答案。 如果 a b a \gt b ab 对区间按照右区间排序从右向左扫描并且维护一个区间和线段树扫描到一个区间的右端点时将对应的左端点加入到线段树中当扫描到一个左端点时将左端点从线段树中移除到扫描到一个 a a a 时查询线段树中 ( b , a ] (b,a] (b,a] 的区间和即为答案。
实际上需要维护的是动态区间和代码中用树状数组来代替维护区间和。
相关知识点
Index Tree树状数组线段树讲解
2、时间复杂度 O ( l o g N ) O(logN) O(logN)
3、代码详解
暴力超时
#include iostream
#include vector
#include algorithm
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;int q;cin n q;vectorvectorint ranges(n, vectorint(2));for (int i 0; i n; i) {cin ranges[i][0];cin ranges[i][1];}sort(ranges.begin(), ranges.end());int a, b;for (int i 0; i q; i) {cin a b;if (a b) {cout 0 endl;continue;}int cnt 0;for (vectorint range : ranges) {int l range[0];int r range[1];if ((a l || a r) || (l b b r)) {continue;}cnt;}cout cnt endl;}return 0;
}树状数组
#include iostream
#include vector
#include cstring
#include algorithmusing namespace std;typedef long long ll;
const int N 2e5 100;vectorint posL[N], posR[N];
int n, q;
vectorpairint, int query[N]; //要查询的信息
int ans[N];//获取最右侧的1
#define lowbit(x) ((x) (-(x)))int tree[N];//1~x范围的前缀和
int get_sum(int x) {int sum 0;while (x) {sum tree[x];x - lowbit(x);}return sum;
}//单点更新——pos位置更新val
void update(int pos, int val) {while (pos N) {tree[pos] val;pos lowbit(pos); //受影响的位置}
}//从左向右扫描
void L_to_R() {memset(tree, 0, sizeof(tree));for (int i 1; i N; i) {for (int r : posL[i]) { //范围的右端点update(r, 1);}for (auto [b, id] : query[i]) {if (b i) {ans[id] get_sum(b - 1);}}update(i, -posR[i].size());}
}//从右向左扫描
void R_to_L() {memset(tree, 0, sizeof(tree));for (int i N - 1; i 0; --i) {for (int l : posR[i]) { //范围的左端点update(l, 1);}for (auto [b, id] : query[i]) {if (b i) {ans[id] get_sum(N - 1) - get_sum(b);}}update(i, -posL[i].size());}
}void sol() {int l, r, a, b;cin n q;for (int i 1; i n; i) {cin l r;posL[l].push_back(r);posR[r].push_back(l);} for (int i 1; i q; i) {cin a b;query[a].push_back({b, i});}L_to_R();R_to_L();for (int i 1; i q; i) {cout ans[i] \n;}
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T 1;while (T--) {sol();}exit(0);
}
