CSES 薪资查询超出时间限制 (TLE) [已关闭]

Question

这是问题链接 文字

我尝试实现线段树，但它为大型测试用例提供了问题。

我也尝试过惰性传播，但它没有产生正确的结果。

我知道我们可以在这里使用有序集，但好像现在我热衷于使用线段树本身来实现这个解决方案。

这是我的代码

#include<iostream>
#include<vector>

typedef long long ll;

const ll INF = 10000000000;
const ll NINF = 0;

void buildTree(ll si, ll ss, ll se, std::vector<ll> &arr, std::vector<std::pair<ll, ll>> &tree) {
    if(ss == se) {
        tree[si] = {arr[ss], arr[ss]};
        return;
    }
 
    ll mid = (ss + se)/2;
    buildTree(2*si, ss, mid, arr, tree);
    buildTree(2*si + 1, mid+1, se, arr, tree);
 
    tree[si].first = std::min(tree[2*si].first, tree[2*si + 1].first);
    tree[si].second = std::max(tree[2*si].second, tree[2*si + 1].second);
}
 
void update(ll si, ll ss, ll se, ll q, std::vector<std::pair<ll, ll>> &tree, ll up, ll del) {
    if(si >= tree.size()) {
        return;
    }
 
    if(ss > q || se < q) {
        return;
    }
 
    if(ss == se && ss == q) {
        tree[si] = {up, up};
        return;
    }
 
    ll mid = (ss + se)/2;
    update(2*si, ss, mid, q, tree, up, del);
    update(2*si + 1, mid+1, se, q, tree, up, del);
 
    tree[si].first = std::min(tree[2*si].first, tree[2*si + 1].first);
    tree[si].second = std::max(tree[2*si].second, tree[2*si + 1].second);
}
 
ll solve(ll si, ll ss, ll se, ll qs, ll qe, std::vector<std::pair<ll, ll>> &tree) {
    if(tree[si].first > qe || tree[si].second < qs) {
        return 0;
    }
 
    if(tree[si].first >= qs && tree[si].second <= qe) {
        return se - ss + 1;
    }
 
    ll mid = (ss + se)/2;
 
    ll l = solve(2*si, ss, mid, qs, qe, tree);
    ll r = solve(2*si + 1, mid+1, se, qs, qe, tree);
 
    return l + r;
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
 
    ll n, q;
    std::cin >> n >> q;
 
    std::vector<ll> arr(n+1);
    for(ll i=1; i<=n; i++) {
        std::cin >> arr[i];
    }
 
    std::vector<std::pair<ll, ll>> tree(4*n, {INF, NINF});
 
    buildTree(1, 1, n, arr, tree);
 
    while(q--) {
        char ch;
        std::cin >> ch;
 
        if(ch == '!') {
            ll k, x;
            std::cin >> k >> x;
 
            ll up = x;
            ll del = arr[k];
            update(1, 1, n, k, tree, up, del);
        }
        else {
            ll a, b;
            std::cin >> a >> b;
 
            std::cout << solve(1, 1, n, a, b, tree) << std::endl;
        }
    }
}