球调

Porridge_Dust @ 2024-07-28 18:26:03

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 1e6 + 100, sqN = 1e4 + 100;

int n, q;
int id[N], tag[sqN], len, ls[sqN], rs[sqN];
char c;

struct node {
    int x, p;
}a[N];

bool cmp1 (const node &x, const node &y) {
    return x.x > y.x;
}

bool cmp2 (const node &x, const node &y) {
    return x.p < y.p;
}

int erfen (int l, int r, int w) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (a[mid].x < w) r = mid - 1;
        else l = mid; 
    }
    return l;
}

void change (int l, int r, int w) {
    if (id[l] == id[r]) {
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        for (int i = l; i <= r; i ++ ) a[i].x += w;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
    }
    else {
        int kl = id[l] + 1, kr = id[r] - 1;
        for (int i = kl; i <= kr; i ++ ) tag[i] += w;
        int lr = ls[kl] - 1, rl = rs[kr] + 1;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp2);
        for (int i = l; i <= lr; i ++ ) a[i].x += w;
        for (int i = rl; i <= r; i ++ ) a[i].x += w;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp1);
    }
}

int query (int l, int r, int w) {
    int ans = 0;
    if (id[l] == id[r]) {
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        for (int i = l; i <= r; i ++ ) if (a[i].x >= w) ans ++ ;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
    }
    else {
        int kl = id[l] + 1, kr = id[r] - 1;
        for (int i = kl; i <= kr; i ++ ) {
            int ll = erfen(ls[i] - 1, rs[i], w);
            ans += ll - ls[i] + 1;
        }
        int lr = ls[kl] - 1, rl = rs[kr] + 1;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp2);
        for (int i = l; i <= lr; i ++ ) if (a[i].x >= w) ans ++ ;
        for (int i = rl; i <= r; i ++ ) if (a[i].x >= w) ans ++ ;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp1);
    }
    return ans;
}

int main () {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++ ) cin >> a[i].x, a[i].p = i;
    len = pow(n, 0.5); 
    for (int i = 1; i <= n; i ++ ) {
        id[i] = (i - 1) / len + 1;
        if (id[i] != id[i - 1]) rs[id[i - 1]] = i - 1, ls[id[i]] = i;
    }
    rs[id[n]] = n;

    for (int i = 1; i <= rs[id[n]]; i ++ ) sort(a + ls[i], a + rs[i] + 1, cmp1);

    int l, r, w;
    while (q -- ) {
        cin >> c >> l >> r >> w;
        if (c == 'M') change(l, r, w);
        else cout << query(l, r, w) << '\n';
    }
    return 0;
}

by Porridge_Dust @ 2024-07-28 18:27:10

两个端点在同一块内的代码应该没问题

by Porridge_Dust @ 2024-07-28 18:57:23

发现了一个问题，tle没了，除了两个ac剩下都wa

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 1e6 + 100, sqN = 1e4 + 100;

int n, q;
int id[N], tag[sqN], len, ls[sqN], rs[sqN];
char c;

struct node {
    int x, p;
}a[N];

bool cmp1 (const node &x, const node &y) {
    return x.x > y.x;
}

bool cmp2 (const node &x, const node &y) {
    return x.p < y.p;
}

int erfen (int l, int r, int w) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (a[mid].x < w) r = mid - 1;
        else l = mid; 
    }
    return l;
}

void change (int l, int r, int w) {
    if (id[l] == id[r]) {
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        for (int i = l; i <= r; i ++ ) a[i].x += w;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
    }
    else {
        int kl = id[l] + 1, kr = id[r] - 1;
        for (int i = kl; i <= kr; i ++ ) tag[i] += w;
        int lr = ls[kl] - 1, rl = rs[kr] + 1;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp2);
        for (int i = l; i <= lr; i ++ ) a[i].x += w;
        for (int i = rl; i <= r; i ++ ) a[i].x += w;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp1);
    }
}

int query (int l, int r, int w) {
    int ans = 0;
    if (id[l] == id[r]) {
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        for (int i = l; i <= r; i ++ ) if (a[i].x >= w) ans ++ ;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
    }
    else {
        int kl = id[l] + 1, kr = id[r] - 1;
        for (int i = kl; i <= kr; i ++ ) {
            int ll = erfen(ls[i] - 1, rs[i], w);
            ans += ll - ls[i] + 1;
        }
        int lr = ls[kl] - 1, rl = rs[kr] + 1;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp2);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp2);
        for (int i = l; i <= lr; i ++ ) if (a[i].x >= w) ans ++ ;
        for (int i = rl; i <= r; i ++ ) if (a[i].x >= w) ans ++ ;
        sort (a + ls[id[l]], a + rs[id[l]] + 1, cmp1);
        sort (a + ls[id[r]], a + rs[id[r]] + 1, cmp1);
    }
    return ans;
}

int main () {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++ ) cin >> a[i].x, a[i].p = i;
    len = pow(n, 0.5); 
    for (int i = 1; i <= n; i ++ ) {
        id[i] = (i - 1) / len + 1;
        if (id[i] != id[i - 1]) rs[id[i - 1]] = i - 1, ls[id[i]] = i;
    }
    rs[id[n]] = n;

    for (int i = 1; i <= id[n]; i ++ ) sort(a + ls[i], a + rs[i] + 1, cmp1);

    int l, r, w;
    while (q -- ) {
        cin >> c >> l >> r >> w;
        if (c == 'M') change(l, r, w);
        else cout << query(l, r, w) << '\n';
    }
    return 0;
}

by CandaaGoose_imkdldw @ 2024-07-28 20:19:29

HL队爷666