(悬1关)请问这个思路有什么不对的地方吗
查看原帖
(悬1关)请问这个思路有什么不对的地方吗
774258
mm1214楼主2024/10/24 17:25

我自己想了一个思路,但是样例三WAWA

就是这样一个东西

其中中间黑线和绿色线围成的,高度不超过上面绿线的红线是对答案有贡献的

代码如下:

#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;
}
2024/10/24 17:25
加载中...