10pts求助，悬赏一关

Tjaweiof @ 2024-02-16 16:52:55

#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[2000001], t[2000001], belong[2000001], d[2001], sz[2001], st[2001], ed[2001];
void init(){
    int num = sqrt(n) + 1;
    for (int i = 1; i <= num; i++){
        st[i] = n / num * (i - 1) + 1;
        ed[i] = n / num * i;
    }
    ed[num] = n;
    for (int i = 1; i <= num; i++){
        for (int j = st[i]; j <= ed[i]; j++){
            belong[j] = i;
        }
        sz[i] = ed[i] - st[i] + 1;
    }
    return;
}
void change(int l, int r, long long v){
    if (belong[l] == belong[r]){
        for (int i = l; i <= r; i++){
            a[i] += v;
        }
        for (int i = st[belong[l]]; i <= ed[belong[l]]; i++){
            t[i] = a[i];
        }
        sort(t + st[belong[l]] + 1, t + ed[belong[l]] + 1);
        return;
    }
    for (int i = l; i <= ed[belong[l]]; i++){
        a[i] += v;
    }
    for (int i = st[belong[r]]; i <= r; i++){
        a[i] += v;
    }
    for (int i = belong[l] + 1; i <= belong[r] - 1; i++){
        d[i] += v;
    }
    for (int i = st[belong[l]]; i = ed[belong[l]]; i++){
        t[i] = a[i];
    }
    sort(t + st[belong[l]] + 1, t + ed[belong[l]] + 1);
    for (int i = st[belong[r]]; i = ed[belong[r]]; i++){
        t[i] = a[i];
    }
    sort(t + st[belong[r]] + 1, t + ed[belong[r]] + 1);
    return;
}
int query(int l, int r, long long v){
    if (belong[l] == belong[r]){
        int res = 0;
        for (int i = l; i <= r; i++){
            if (a[i] + d[belong[l]] >= v){
                res++;
            }
        }
        return res;
    }
    int res = 0;
    for (int i = l; i <= ed[belong[l]]; i++){
        if (a[i] + d[belong[l]] >= v){
            res++;
        }
    }
    for (int i = st[belong[r]]; i <= r; i++){
        if (a[i] + d[belong[r]] >= v){
            res++;
        }
    }
    for (int i = belong[l] + 1; i <= belong[r] - 1; i++){
        res += ed[i] - (lower_bound(t + st[i], t + ed[i] + 1, v - d[i]) - t) + 1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    char op;
    int l, r;
    long long w, c;
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    init();
    while (q--){
        cin >> op;
        if (op == 'M'){
            cin >> l >> r >> w;
            change(l, r, w);
        } else {
            cin >> l >> r >> c;
            cout << query(l, r, c) << endl;
        }
    }
    return 0;
}

by sherry_lover @ 2024-02-16 17:09:50

orz

by zhengpie @ 2024-02-17 11:38:33

@Tjaweiof 悬赏哪关？

by Tjaweiof @ 2024-02-17 13:21:42

@zhengpie 。。。关注。。。还有我已经关注你了

by Stonkin @ 2024-02-18 10:52:13

@Tjaweiof 帮你改好了，你的问题全部写在代码的注释里面

#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[2000001], t[2000001], belong[2000001], d[2001], sz[2001], st[2001], ed[2001];
void init(){
    int num = sqrt(n) + 1;
    for (int i = 1; i <= num; i++){
        st[i] = n / num * (i - 1) + 1;
        ed[i] = n / num * i;
    }
    ed[num] = n;
    for (int i = 1; i <= num; i++){
        for (int j = st[i]; j <= ed[i]; j++){
            belong[j] = i;
        }
        sz[i] = ed[i] - st[i] + 1;
    }
    for (int i = 1; i <= n; i++){
        t[i] = a[i];
    }
    for (int i = 1; i <= num; i++){
        sort(t + st[i], t + ed[i] + 1);
    }//读入完就要处理t, 防止第一个操作就是询问 
    return;
}
void change(int l, int r, long long v){
    if (belong[l] == belong[r]){
        for (int i = l; i <= r; i++){
            a[i] += v;
        }
        for (int i = st[belong[l]]; i <= ed[belong[l]]; i++){
            t[i] = a[i];
        }
        sort(t + st[belong[l]], t + ed[belong[l]] + 1);//每个块的第一个数也要纳入排序，排序是左闭右开的
        return;
    }
    for (int i = l; i <= ed[belong[l]]; i++){
        a[i] += v;
    }
    for (int i = st[belong[r]]; i <= r; i++){
        a[i] += v;
    }
    for (int i = belong[l] + 1; i <= belong[r] - 1; i++){
        d[i] += v;
    }
    for (int i = st[belong[l]]; i <= ed[belong[l]]; i++){//= -> <= 你估计手瓢了 
        t[i] = a[i];
    }
    sort(t + st[belong[l]], t + ed[belong[l]] + 1);//每个块的第一个数也要纳入排序，排序是左闭右开的
    for (int i = st[belong[r]]; i <= ed[belong[r]]; i++){//= -> <= 你估计手瓢了 
        t[i] = a[i];
    }
    sort(t + st[belong[r]], t + ed[belong[r]] + 1);//每个块的第一个数也要纳入排序，排序是左闭右开的
    return;
}
int query(int l, int r, long long v){
    if (belong[l] == belong[r]){
        int res = 0;
        for (int i = l; i <= r; i++){
            if (a[i] + d[belong[l]] >= v){
                res++;
            }
        }
        return res;
    }
    int res = 0;
    for (int i = l; i <= ed[belong[l]]; i++){
        if (a[i] + d[belong[l]] >= v){
            res++;
        }
    }
    for (int i = st[belong[r]]; i <= r; i++){
        if (a[i] + d[belong[r]] >= v){
            res++;
        }
    }
    for (int i = belong[l] + 1; i <= belong[r] - 1; i++){
        res += ed[i] - (lower_bound(t + st[i], t + ed[i] + 1, v - d[i]) - t) + 1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    char op;
    int l, r;
    long long w, c;
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    init();
    while (q--){
        cin >> op;
        if (op == 'M'){
            cin >> l >> r >> w;
            change(l, r, w);
        } else {
            cin >> l >> r >> c;
            cout << query(l, r, c) << endl;
        }
    }
    return 0;
}

by Tjaweiof @ 2024-02-18 14:01:06

@Stonkin 感谢 & 已关 & 膜拜orz%%%