蓝桥杯 17110抓娃娃

问题描述

小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上，第 i 条线段的左端点在 li，右端点在 ri​。小明用 m 个区间去框这些线段，第 i个区间的范围是 [Li​, Ri​]。如果一个线段有 至少一半 的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?

输入格式

输入共 n+m+1 行。 第一行为两个正整数 n, m。 后面 n 行，每行两个整数 li​, ri​。 后面 m 行，每行两个整数Li​, Ri​。

输出格式

输出共 m 行，每行一个整数。

样例输入

3 2 1 2 1 3 3 4 1 4 2 4

样例输出

3 2

评测用例规模与约定

对于 20%20% 的数据，保证 n,m≤。 对于 100%100% 的数据，保证 n,m≤，li​ using namespace std; const int N = 2e6+10; int n, m; //n条线段 m个区间 int mp[N]; int main() { cin»n»m; int l, r; for(int i=1; i<=n; ++i) { cin»l»r; mp[l+r]++; //记录每条线段中点的位置 } for(int i=1; i>l»r; l *= 2; r *= 2; //一段区间包含了多少个中点就覆盖了多少条线段 cout«mp[r] - mp[l-1]«endl; //l-1:线段的中点恰好在 L 上 } return 0; }