线段树+主席树WA80pts求调

WA #9 #10

#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
#include<vector>
#include <algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<iomanip>
#include<iterator>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ri register int 
typedef long long ll;
typedef long double ld;
const int N = 1e6 + 5, M = 2e5 + 5;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int n, m;
int root[N], cnt, siz;
int a[N], b[N];
struct Node {
    int L, R, sum;
}tree[N * 10];

int tag[N << 2];
bool vis[N << 2];

int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void push_down(int p) {
    if (tag[p]) {
        tag[ls(p)] += tag[p];
        tag[rs(p)] += tag[p];
        vis[ls(p)] = vis[rs(p)] = 1;
        tag[p] = 0;
    }
}
void addtag(int L, int R, int p, int pl, int pr, int x) {
    vis[p] = 1;
    if (L <= pl && pr <= R) {
        tag[p] += x;
        return;
    }
    push_down(p);
    int mid = (pl + pr) >> 1;
    if (L <= mid) addtag(L, R, ls(p), pl, mid, x);
    if (R > mid) addtag(L, R, rs(p), mid + 1, pr, x);
}
int update(int pre, int pl, int pr, int x) {
    int rt = ++cnt;
    tree[rt].L = tree[pre].L;
    tree[rt].R = tree[pre].R;
    tree[rt].sum = tree[pre].sum + 1;
    int mid = (pl + pr) >> 1;
    if (pl < pr) {
        if (x <= mid) tree[rt].L = update(tree[pre].L, pl, mid, x);
        else tree[rt].R = update(tree[pre].R, mid + 1, pr, x);
    }
    return rt;
}
int ask(int u, int v, int pl, int pr, int k) {
    int x = tree[tree[v].L].sum - tree[tree[u].L].sum;
    int mid = (pl + pr) >> 1;
    int ans = 0;
    if (pl < pr) {
        if (k <= mid) ans += ask(tree[u].L, tree[v].L, pl, mid, k);
        else ans += ask(tree[u].R, tree[v].R, mid + 1, pr, k) + x;
    }
    return ans;
}
int query(int L, int R, int p, int pl, int pr, int x) {
    int ans = 0;
    if (L <= pl && pr <= R) {
        if (tag[p]) {
            int k = lower_bound(b + 1, b + 1 + siz, x - tag[p]) - b;
            ans += (tree[root[pr]].sum - tree[root[pl - 1]].sum) - ask(root[pl - 1], root[pr], 1, siz, k);
            return ans;
        }
        else if (!vis[p]) {
            int k = lower_bound(b + 1, b + 1 + siz, x) - b;
            ans += (tree[root[pr]].sum - tree[root[pl - 1]].sum) - ask(root[pl - 1], root[pr], 1, siz, k);
            return ans;
        }
    }
    push_down(p);
    int mid = (pl + pr) >> 1;
    if (L <= mid) ans += query(L, R, ls(p), pl, mid, x);
    if (R > mid) ans += query(L, R, rs(p), mid + 1, pr, x);
    return ans;
}
int main() {
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    siz = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b + 1, b + 1 + siz, a[i]) - b;
        root[i] = update(root[i - 1], 1, siz, x);
    }
    for (int i = 1; i <= m; i++) {
        char op;
        cin >> op;
        if (op == 'M') {
            int L, R, x;
            cin >> L >> R >> x;
            addtag(L, R, 1, 1, n, x);
        }
        else {
            int L, R, v;
            cin >> L >> R >> v;
            cout << query(L, R, 1, 1, n, v) << endl;
        }
    }

    return 0;
}