75pts分块求调

xzh_2013 @ 2024-12-30 20:32:12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n , m , op , x , y;
ll a[100005] , k;
int bl , p[100005] , len[1005];
ll sum[1005] , tg[1005];
inline ll read(){
    ll f = 1 , x = 0;
    char c = getchar_unlocked();
    while(!isdigit(c)){
        if(c == '-')f = -1;
        c = getchar_unlocked();
    }
    while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48) , c = getchar_unlocked();
    return f * x;
}
inline void write(ll x){
    if(x < 0)x = -x , putchar('-');
    if(x > 10)write(x / 10);
    putchar(x % 10 + '0');
}
void init(){
    bl = sqrt(n);
    for(int i = 1;i <= n;i++)p[i] = (i - 1) / bl + 1 , len[p[i]]++;
}
void update(int l , int r , ll x){
    int lk = p[l] , rk = p[r];
    if(lk == rk){
        for(int i = l;i <= r;i++)a[i] += x , sum[lk] += x;
    }else{
        for(int i = l;p[i] == lk;i++)a[i] += x , sum[lk] += x;
        for(int i = lk + 1;i < rk;i++)tg[lk] += x , sum[lk] += bl * x;
        for(int i = r;p[i] == rk;i--)a[i] += x , sum[rk] += x;
    }
}
ll query(int l , int r){
    ll ans = 0;
    int lk = p[l] , rk = p[r];
    if(lk == rk){
        for(int i = l;i <= r;i++)ans += tg[p[i]] + a[i];
    }else{
        for(int i = l;p[i] == lk;i++)ans += tg[lk] + a[i];
        for(int i = lk + 1;i < rk;i++)ans += sum[i];
        for(int i = r;p[i] == rk;i--)ans += tg[rk] + a[i];
    }
    return ans;
}
int main(){
    n = read() , m = read();
    for(int i = 1;i <= n;i++)a[i] = read();
    while(m--){
        op = read() , x = read() , y = read();
        if(op == 1){
            k = read();
            update(x , y , k);
        }else cout << query(x , y) << '\n';
    }
    return 0;
}

by xzh_2013 @ 2024-12-30 20:48:29

改动后0ptsWA：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n , m , op , x , y;
ll a[100005] , k;
int bl , p[100005] , len[1005];
ll sum[1005] , tg[1005];
inline ll read(){
    ll f = 1 , x = 0;
    char c = getchar_unlocked();
    while(!isdigit(c)){
        if(c == '-')f = -1;
        c = getchar_unlocked();
    }
    while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48) , c = getchar_unlocked();
    return f * x;
}
inline void write(ll x){
    if(x < 0)x = -x , putchar('-');
    if(x > 10)write(x / 10);
    putchar(x % 10 + '0');
}
void init(){
    bl = sqrt(n);
    for(int i = 1;i <= n;i++)p[i] = (i - 1) / bl + 1 , len[p[i]]++;
}
void update(int l , int r , ll x){
    int lk = p[l] , rk = p[r];
    if(lk == rk){
        for(int i = l;i <= r;i++)a[i] += x , sum[lk] += x;
    }else{
        for(int i = l;p[i] == lk;i++)a[i] += x , sum[lk] += x;
        for(int i = lk + 1;i < rk;i++)tg[i] += x , sum[i] += len[i] * x;
        for(int i = r;p[i] == rk;i--)a[i] += x , sum[rk] += x;
    }
}
ll query(int l , int r){
    ll ans = 0;
    int lk = p[l] , rk = p[r];
    if(lk == rk){
        for(int i = l;i <= r;i++)ans += tg[lk] + a[i];
    }else{
        for(int i = l;p[i] == lk;i++)ans += tg[lk] + a[i];
        for(int i = lk + 1;i < rk;i++)ans += sum[i];
        for(int i = r;p[i] == rk;i--)ans += tg[rk] + a[i];
    }
    return ans;
}
int main(){
    n = read() , m = read();
    init();
    for(int i = 1;i <= n;i++)a[i] = read();
    while(m--){
        op = read() , x = read() , y = read();
        if(op == 1){
            k = read();
            update(x , y , k);
        }else cout << query(x , y) << '\n';
    }
    return 0;
}

by xzh_2013 @ 2024-12-31 21:04:49

已调出，本帖毕