【搬运于 2026-4-26】【原文写于 2025-5-12】
更 luogu 的体验
题外话，因为做过类似题目又忘记了数据范围，赛时用莫队导致超过了时限。
本题考虑使用树状数组。
对于一条线段，如果它的左端点或右端点在某一线段内，但两端点并不同时出现在这条线段内，则两个线段相交。
拆环为链，从左到右处理。将 \(M\) 条线按左端点排序，每条线段的右端点加入树状数组。
先不考虑两端点同时出现在某一条线段内的情况。设某条要查询线段区间为 \([l,r]\)，处理到 \(l\) 的时候，对答案有贡献的为在 \(l\) 右侧的树状数组种的右端点，因为其左端点一定小于 \(l\)。对于 \(r\) 同理。
现在考虑两端点同时出现在某一条线段内的情况。在处理到 \(l\) 的时候，对于 \(r\) 右侧的树状数组内的右端点是非合法情况，可以顺便处理掉。因为处理到 \(l\) 和 \(r\) 时这些非合法情况都算进去了，因此要减去两次。
#include <bits/stdc++.h>
using namespace std;
struct dat{int y,z,id;
};
vector<dat> v[2000010];
int tr[2000010],que[200010];
int n,m;
void add(int x,int y){for(; x <= 2 * n; x += (x & -x))tr[x] += y;
}
int sum(int x){int res = 0;for(; x; x -= (x & -x))res += tr[x];return res;
}
int main(){scanf("%d%d",&n,&m);for(int i = 1; i <= m; i++){int x,y;scanf("%d%d",&x,&y);v[x].push_back({y,0,0});}int q;scanf("%d",&q);for(int i = 1; i <= q; i++){int x,y;scanf("%d%d",&x,&y);v[x].push_back({x,1,i});v[x].push_back({y,-2,i});v[y].push_back({y,1,i});}int tot = 0;for(int i = 1; i <= 2 * n; i++){if(i % 2){for(int j = 0; j < v[i].size(); j++){int y = v[i][j].y,z = v[i][j].z,id = v[i][j].id;que[id] += z * (tot - sum(y));//tot是已经加入的总点数，sum(y)是在y左侧的点数，tot-sum(y)就是在y右侧的点数。}}else{for(int j = 0; j < v[i].size(); j++){int y = v[i][j].y,z = v[i][j].z,id = v[i][j].id;tot++;add(y,1);}}}for(int i = 1; i <= q; i++){printf("%d\n",que[i]);}return 0;
}