我自己想了一个思路,但是样例三WA了
就是这样
一个东西
其中中间黑线和绿色线围成的,高度不超过上面绿线的红线是对答案有贡献的
代码如下:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define int long long
#define pii pair<int , int>
#define pb emplace_back
#define pair(x , y) make_pair(x , y)
#define fi first
#define se second
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid (l + r >> 1)
using namespace std;
using namespace __gnu_pbds;
constexpr int N = 200005 , M = 100005;
int v , n , m;
struct L { int l , r; } l[N] , q[M];
int ans[M];
struct BIT {
#define lowbit(x) (x&-x)
int tr[N];
void U(int x , int y) { for (; x <= v; x += lowbit(x)) tr[x] += y; }
int _Q(int x) { int res = 0; for (; x; x -= lowbit(x)) res += tr[x]; return res; }
int Q(int x , int y) { return _Q(y) - _Q(x - 1); }
} tr;
void solve() {
cin >> v >> n >> m;
for (int i = 1; i <= n; i++) cin >> l[i].l >> l[i].r;
sort(l + 1 , l + n + 1 , [](const L &x , const L &y) {
return x.l < y.l;
});
for (int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r;
for (int i = m , pos = n + 1; i >= 1; i--) {
while(pos > 1 && l[pos - 1].l >= q[i].l) {
--pos;
tr.U(l[pos].r , 1);
}
ans[i] = tr.Q(1 , q[i].r);
}
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
return;
}
signed main() {
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
int T = 1;
while(T--) solve();
return 0;
}