萌新求调

P2801 教主的魔法

FailureC0der @ 2023-02-12 21:25:21

我知道我确实不该没过样例就来发帖。

但是确实不知道哪里错了。

已经调了 1h。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int now=0,nev=1; char c=getchar();
    while(!isdigit(c)) { if(c=='-') nev=-1; c=getchar();}
    while(isdigit(c)) { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
    return now*nev;
}

const int N = 1e6 + 5;
int pos[N], l[N], r[N], add[N], S;
int a[N], b[N], n, m;

void init(){
    for (int i = 1; i <= n; i ++) b[i] = read();
    S = sqrt(n);
    for (int i = 1; i <= S; i ++){
        l[i] = (i - 1) * S + 1;
        r[i] = i * S;
    }
    if (r[S] < n) l[S + 1] = r[S] + 1, r[++ S] = n;
    for (int i = 1; i <= S; i ++){
        sort(b + l[i], b + r[i] + 1);
        for (int j = l[i]; j <= r[i]; j ++)
            pos[j] = i;
    }
}

void update(int L, int R, int k){
    int p = pos[L], q = pos[R];
    if (p == q){
        for (int i = L; i <= R; i ++)
            a[i] += k;
        for (int i = l[p]; i <= r[p]; i ++)
            b[i] = a[i]; 
        sort(b + l[p], b + r[p] + 1);
        return ;
    }
    for (int i = p + 1; i <= q - 1; i ++)
        add[i] += k;
    for (int i = L; i <= r[p]; i ++)
        a[i] += k;
    for (int i = l[p]; i <= r[p]; i ++)
        b[i] = a[i];
    for (int i = l[q]; i <= R; i ++)
        a[i] += k;
    for (int i = l[q]; i <= r[q]; i ++)
        b[i] = a[i];
    sort(b + l[p], b + r[p] + 1);
    sort(b + l[q], b + r[q] + 1);
}

int query(int L, int R, int c){
    int p = pos[L], q = pos[R];
    int cnt = 0;
    if (p == q){
        for (int i = L; i <= R; i ++)
            if (a[i] + add[p] >= c) cnt ++;
        return cnt;
    }
    for (int i = L; i <= r[p]; i ++)
        if (a[i] + add[p] >= c) cnt ++;
    for (int i = l[q]; i <= R; i ++)
        if (a[i] + add[q] >= c) cnt ++;
    for (int i = p + 1; i <= q - 1; i ++){
        int sb1 = l[i], sb2 = r[i];
        while (sb1 < sb2){
            int mid = (sb1 + sb2) >> 1;
            if (b[mid] + add[i] >= c) sb2 = mid;
            else sb1 = mid + 1;
        }
        cnt += r[i] - sb1 + 1;
    }
    return cnt;
}

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    init();
    while (m --){
        char op; cin >> op;
        if (op == 'M') update(read(), read(), read());
        else cout << query(read(), read(), read()) << "\n";
    }
    return 0;
}

by FailureC0der @ 2023-02-12 21:25:55

对了，如果是弱智问题我就独立宣言。

by Madsome @ 2023-02-12 21:33:16

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int now=0,nev=1; char c=getchar();
    while(!isdigit(c)) { if(c=='-') nev=-1; c=getchar();}
    while(isdigit(c)) { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
    return now*nev;
}

const int N = 1e6 + 5;
int pos[N], l[N], r[N], add[N], S;
int a[N], b[N], n, m;

void init(){
   // for (int i = 1; i <= n; i ++) b[i] = read();
    S = sqrt(n);
    for (int i = 1; i <= S; i ++){
        l[i] = (i - 1) * S + 1;
        r[i] = i * S;
    }
    if (r[S] < n) l[S + 1] = r[S] + 1, r[++ S] = n;
    for (int i = 1; i <= S; i ++){
        sort(b + l[i], b + r[i] + 1);
        for (int j = l[i]; j <= r[i]; j ++)
            pos[j] = i;
    }
}

void update(int L, int R, int k){
    int p = pos[L], q = pos[R];
    if (p == q){
        for (int i = L; i <= R; i ++)
            a[i] += k;
        for (int i = l[p]; i <= r[p]; i ++)
            b[i] = a[i]; 
        sort(b + l[p], b + r[p] + 1);
        return ;
    }
    for (int i = p + 1; i <= q - 1; i ++)
        add[i] += k;
    for (int i = L; i <= r[p]; i ++)
        a[i] += k;
    for (int i = l[p]; i <= r[p]; i ++)
        b[i] = a[i];
    for (int i = l[q]; i <= R; i ++)
        a[i] += k;
    for (int i = l[q]; i <= r[q]; i ++)
        b[i] = a[i];
    sort(b + l[p], b + r[p] + 1);
    sort(b + l[q], b + r[q] + 1);
}

int query(int L, int R, int c){
    int p = pos[L], q = pos[R];
    int cnt = 0;
    if (p == q){
        for (int i = L; i <= R; i ++)
            if (a[i] + add[p] >= c) cnt ++;
        return cnt;
    }
    for (int i = L; i <= r[p]; i ++)
        if (a[i] + add[p] >= c) cnt ++;
    for (int i = l[q]; i <= R; i ++)
        if (a[i] + add[q] >= c) cnt ++;
    for (int i = p + 1; i <= q - 1; i ++){
        int sb1 = l[i], sb2 = r[i];
        while (sb1 < sb2){
            int mid = (sb1 + sb2) >> 1;
            if (b[mid] + add[i] >= c) sb2 = mid;
            else sb1 = mid + 1;
        }
        cnt += r[i] - sb1 + 1;
    }
    return cnt;
}

signed main()
{
    n = read(), m = read();
   // for (int i = 1; i <= n; i ++) a[i] = read();
    init();
    while (m --){
        char op; cin >> op;
       // if (op == 'M') update(read(), read(), read());
       // else cout << query(read(), read(), read()) << "\n";
    }
    return 0;
}

by Madsome @ 2023-02-12 21:34:05

@haimo

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int now=0,nev=1; char c=getchar();
    while(!isdigit(c)) { if(c=='-') nev=-1; c=getchar();}
    while(isdigit(c)) { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
    return now*nev;
}

const int N = 1e6 + 5;
int pos[N], l[N], r[N], add[N], S;
int a[N], b[N], n, m;

void init(){
    for (int i = 1; i <= n; i ++)cin>>b[i],a[i]=b[i];
    S = sqrt(n);
    for (int i = 1; i <= S; i ++){
        l[i] = (i - 1) * S + 1;
        r[i] = i * S;
    }
    if (r[S] < n) l[S + 1] = r[S] + 1, r[++ S] = n;
    for (int i = 1; i <= S; i ++){
        sort(b + l[i], b + r[i] + 1);
        for (int j = l[i]; j <= r[i]; j ++)
            pos[j] = i;
    }
}

void update(int L, int R, int k){
    int p = pos[L], q = pos[R];
    if (p == q){
        for (int i = L; i <= R; i ++)
            a[i] += k;
        for (int i = l[p]; i <= r[p]; i ++)
            b[i] = a[i]; 
        sort(b + l[p], b + r[p] + 1);
        return ;
    }
    for (int i = p + 1; i <= q - 1; i ++)
        add[i] += k;
    for (int i = L; i <= r[p]; i ++)
        a[i] += k;
    for (int i = l[p]; i <= r[p]; i ++)
        b[i] = a[i];
    for (int i = l[q]; i <= R; i ++)
        a[i] += k;
    for (int i = l[q]; i <= r[q]; i ++)
        b[i] = a[i];
    sort(b + l[p], b + r[p] + 1);
    sort(b + l[q], b + r[q] + 1);
}

int query(int L, int R, int c){
    int p = pos[L], q = pos[R];
    int cnt = 0;
    if (p == q){
        for (int i = L; i <= R; i ++)
            if (a[i] + add[p] >= c) cnt ++;
        return cnt;
    }
    for (int i = L; i <= r[p]; i ++)
        if (a[i] + add[p] >= c) cnt ++;
    for (int i = l[q]; i <= R; i ++)
        if (a[i] + add[q] >= c) cnt ++;
    for (int i = p + 1; i <= q - 1; i ++){
        int sb1 = l[i], sb2 = r[i];
        while (sb1 < sb2){
            int mid = (sb1 + sb2) >> 1;
            if (b[mid] + add[i] >= c) sb2 = mid;
            else sb1 = mid + 1;
        }
        cnt += r[i] - sb1 + 1;
    }
    return cnt;
}

signed main()
{
   cin>>n>>m;
    init();
    while (m --){
        char op; 
        cin >> op;
        int A,B,C;
        cin>>A>>B>>C;
        if (op == 'M') update(A, B, C);
        else cout << query(A, B, C) << "\n";
    }
    return 0;
}

这样90

by FailureC0der @ 2023-02-12 21:34:09

艹。我是傻逼。

by 20275418wang @ 2023-02-12 21:35:26

真.独立宣言

by FailureC0der @ 2023-02-12 21:45:41

改 lower_bound AC，此贴完结。