求一份分块的代码

WsW_ @ 2023-07-09 19:03:20

by FuckYouJinhai @ 2023-07-09 19:13:30

#include<cstdio>
#include<cmath>
#define ull unsigned long long 

ull st[350],ed[350],sum[350],add[350];
ull arr[100010],bln[100010];

int n,m,o,x,y,k;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%llu",&arr[i]);
    const int bl=sqrt(n);
    for(int i=1;i<=bl;++i){
        st[i]=n/bl*(i-1)+1;
        ed[i]=n/bl*i;
    }
    ed[bl]=n;
    for(int i=1;i<=bl;++i)
        for(int j=st[i];j<=ed[i];++j)
            bln[j]=i;
    for(int i=1;i<=bl;++i)
        for(int j=st[i];j<=ed[i];++j)
            sum[i]+=arr[j];
    while(m--){
        scanf("%d%d%d",&o,&x,&y);
        if(o==1){
            scanf("%d",&k);
            if(bln[x]==bln[y])
                for(int i=x;i<=y;++i){
                    arr[i]+=k;
                    sum[bln[i]]+=k;
                }
            else{
                for(int i=x;i<=ed[bln[x]];++i){
                    arr[i]+=k;
                    sum[bln[i]]+=k;
                }
                for(int i=st[bln[y]];i<=y;++i){
                    arr[i]+=k;
                    sum[bln[i]]+=k;
                }
                for(int i=bln[x]+1;i<bln[y];++i)
                    add[i]+=k;
            }
        }else{
            ull s=0;
            if(bln[x]==bln[y])
                for(int i=x;i<=y;++i)
                    s+=arr[i]+add[bln[i]];
            else{
                for(int i=x;i<=ed[bln[x]];++i)
                    s+=arr[i]+add[bln[i]];
                for(int i=st[bln[y]];i<=y;++i)
                    s+=arr[i]+add[bln[i]];
                for(int i=bln[x]+1;i<bln[y];++i)
                    s+=sum[i]+add[i]*(ed[i]-st[i]+1);
            }
            printf("%llu\n",s);
        }
    }
    return 0;
}

by mori_ @ 2023-07-09 19:33:45

//
// Created by Mori on 2023/6/18.
//

#include <bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
using namespace std;

int read() {
    int res = 0, f = 1;
    char temp = getchar();
    for (; !isdigit(temp); temp = getchar()) f = temp == '-' ? -1 : 1;
    for (; isdigit(temp); temp = getchar()) res = res * 10 + temp - '0';
    return res * f;
}

char gc() {
    char temp = getchar();
    while (temp == '\n' || temp == ' ') temp = getchar();
    return temp;
}

constexpr int maxn = 50005;
long long a[maxn], n, len, id[maxn], sum[maxn >> 1], add[maxn >> 1];

void build() {
    for (int i = 1; i <= n; i++)
        a[i] = read(), id[i] = (i - 1) / len + 1, sum[id[i]] += a[i];
}

void modify(int l, int r, int x) {
    int lid = id[l], rid = id[r];
    if (lid == rid) {
        sum[lid] += (r - l + 1) * x;
        while (l <= r) a[l++] += x;
    } else {
        for (int i = l; lid == id[i]; i++) a[i] += x, sum[lid] += x;
        for (int i = lid + 1; i < rid; i++) sum[i] += len * x, add[i] += x;
        for (int i = r; rid == id[i]; i--) a[i] += x, sum[rid] += x;
    }
}

long long query(int l, int r) {
    long long res = 0;
    int lid = id[l], rid = id[r];
    if (lid == rid) {
        res = (r - l + 1) * add[lid];
        for (int i = l; i <= r; i++) res += a[i];
    } else {
        for (int i = l; lid == id[i]; i++) res += a[i] + add[lid];
        for (int i = lid + 1; i < rid; i++) res += sum[i];
        for (int i = r; rid == id[i]; i--) res += a[i] + add[rid];
    }
    return res;
}

int main() {

    n = read(), len = (int) sqrt(n) * 0.7;

    build();

    for (int i = 1; i <= n; i++) {
        int opt = read(), l = read(), r = read(), c = read();
        if (opt) printf("%lld\n", query(l, r) % (c + 1));
        else modify(l, r, c);
    }

    return 0;
}

by Twiter_ln @ 2024-01-04 21:39:45

#include<bits/stdc++.h> // P[i] = t;

using namespace std;
const int N = 100037;
typedef long long lli;

int n, m, a[N];
int L[N], R[N], P[N];
lli sum[N], add[N];

int x, y, z, d;

inline void change(int l, int r, int d) {
    int p = P[l];
    int q = P[r];

    if(p == q) {
        for(int i=l;i<=r;++i) a[i] += d;
        sum[p] += (r - l + 1) * d;
        return ;
    }

    for(int i=p+1;i<=q-1;++i) add[i] += d;
    for(int i=l;i<=R[p];++i) a[i] += d;
    sum[p] += (R[p] - l + 1) * d;
    for(int i=L[q];i<=r;++i) a[i] += d;
    sum[q] += (r - L[q] + 1) * d;
}

inline lli ask(int l, int r) {
    lli ans = 0;

    int p = P[l];
    int q = P[r];
    if(p == q) {
        for(int i=l;i<=r;++i) ans += a[i];
        ans += (r - l + 1) * add[p];
        return ans;
    }

    for(int i=p+1;i<=q-1;++i) ans += sum[i] + (R[i] - L[i] + 1) * add[i];
    for(int i=l;i<=R[p];++i) ans += a[i];
    ans += (R[p] - l + 1) * add[p];
    for(int i=L[q];i<=r;++i) ans += a[i];
    ans += (r - L[q] + 1) * add[q];
    return ans;
}

int main() {
//  freopen("P3372_8.in","r",stdin);
//  freopen("Fuck.txt","w",stdout);

    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;++i) scanf("%d", &a[i]);

    int t = sqrt(n);

    for(int i=1;i<=t;++i) {
        L[i] = (i - 1) * t + 1;
        R[i] = i * t;
//      L[i] = n / t * (i-1) + 1;
//      R[i] = n / t * i;
    }
    if(t * t < n) ++ t, L[t] = R[t-1] + 1, R[t] = n;

    for(int i=1;i<=t;++i) {  
        for(int j=L[i];j<=R[i];++j) {
            P[j] = i;
            sum[i] += a[j];
        }
    }

//  cout<<t<<endl;
//  for(int i=1;i<=n;++i) cout<<P[i]<<" ";
//  putchar('\n');
//  for(int i=1;i<=t;++i) cout<<sum[i]<<" ";
//  putchar('\n');
//  for(int i=1;i<=t;++i) cout<<L[i]<<" "<<R[i]<<endl;

    for(int i=1;i<=m;++i) {
        scanf("%d%d%d", &x, &y, &z);
        if(x == 1) {
            scanf("%d", &d);
            change(y, z, d);
        } else if(x == 2) printf("%lld\n", ask(y, z));
    }

    return 0;
}
/*

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
:11 \n 8 \n 20

8 10
640 591 141 307 942 58 775 133 
2 1 5
2 3 8
2 3 6
2 5 8
2 4 8
1 4 8 60
2 1 6
2 5 8
1 3 7 15
1 2 6 86
:
2621
2356
1448
1908
2215
2859
2148

8 100
1 1 1 1 1 1 1 1
2 3 8

*/