AcWing 243. 一个简单的整数问题2    原题链接    困难

作者： 作者的头像   妙WA种子_ ,  2021-02-14 09:48:46 ,  所有人可见 ,  阅读 402

2


题目描述

分块写法。蓝书P224。
对于整段的修改用标记add记录，对于不足整段的修改采取朴素算法。
分块思想可以用“大段维护，局部朴素”来形容。

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;

const int N=1e5+10;

typedef long long LL;

LL a[N],sum[N],add[N];
int L[N],R[N];
int pos[N];
int n,m,t;

void change(int l,int r,LL d)
{
    int p=pos[l],q=pos[r];
    if(p==q)
    {
        for(int i=l;i<=r;i++) a[i]+=d;
        sum[p]+=d*(r-l+1);
    }
    else
    {
        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]+=d*(R[p]-l+1);
        for(int i=L[q];i<=r;i++) a[i]+=d;
        sum[q]+=d*(r-L[q]+1);
    }
}

LL ask(int l,int r)
{
    int p=pos[l],q=pos[r];
    LL ans=0;
    if(p==q)
    {
        for(int i=l;i<=r;i++) ans+=a[i];
        ans+=add[p]*(r-l+1);
    }
    else
    {
        for(int i=p+1;i<=q-1;i++) ans+= sum[i] + add[i] * (R[i] - L[i] + 1);
        for(int i=l;i<=R[p];i++) ans+=a[i];
        ans+=add[p]*(R[p]-l+1);
        for(int i=L[q];i<=r;i++) ans+=a[i];
        ans+=add[q]*(r-L[q]+1);
    }
    return ans;
}

int main()
{
    cin>>n>>m;

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

    t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        L[i]=(i-1)*sqrt(n)+1;
        R[i]=i*sqrt(n);
    }
    if(R[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++)
        {
            pos[j]=i;
            sum[i]+=a[j];
        }
    }

    while(m--){
        char op[3];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='C'){
            scanf("%d",&d);
            change(l,r,d);
        }
        else printf("%lld\n",ask(l,r));
    }



    return 0;
}

1 评论

用户头像
dys   2021-02-15 21:16         踩      回复

可持久化的情况

//1 t l r x
//2 t l r
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e2 + 10,M = 1000 * N;
struct node{
    int l,r;
    int s;
    int add;
}tr[M];
int lson[M],rson[M];
int root[N],idx;
int w[N];
void pushup(int u){
    tr[u].s = tr[lson[u]].s + tr[rson[u]].s;
}
void pushdown(int u){
    if(tr[u].add){
        int ls,rs;
        tr[ls = ++idx] = tr[lson[u]];
        tr[rs = ++idx] = tr[rson[u]];
        tr[ls].add += tr[u].add;
        tr[rs].add += tr[u].add;
        tr[ls].s += tr[u].add * (tr[u].r - tr[u].l + 1);
        tr[rs].s += tr[u].add * (tr[u].r - tr[u].l + 1);
        tr[u].add = 0;
        return;
    }
}
void build(int &u,int l,int r){
    u = ++idx;
    tr[u] = {l,r};
    if(l == r){
        tr[u].s = w[l];
        return;
    }
    int mid = l + r >> 1;
    build(lson[u],l,mid);
    build(rson[u],mid+1,r);
    pushup(u);
}
void change(int k,int &nk,int x,int y,int z){
    nk = ++idx;
    tr[nk] = tr[k];
    lson[nk] = lson[k];
    rson[nk] = rson[k];
    if(tr[nk].l >= x && tr[nk].r <= y){
        tr[nk].s = tr[k].s + (tr[nk].r - tr[nk].l + 1) * z;
        tr[nk].add = tr[k].add;
        tr[nk].add += z;
    }else{
        pushdown(nk);
        int mid = tr[nk].l + tr[nk].r >> 1;
        if(x <= mid) change(lson[k],lson[nk],x,y,z);
        if(y > mid) change(rson[k],rson[nk],x,y,z);
        pushup(nk);
    }
}
int query(int nk,int x,int y){
    if(tr[nk].l >= x && tr[nk].r <= y) return tr[nk].s;
    pushdown(nk);
    int mid = tr[nk].l + tr[nk].r >> 1;
    int sum = 0;
    if(x <= mid) sum += query(lson[nk],x,y);
    if(y > mid) sum += query(rson[nk],x,y);
    return sum;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> w[i];
    build(root[0],1,n);
    int op,t,l,r,x;
    for(int i=1;i<=m;i++){
        cin >> op >> t >> l >> r;
        if(op == 1){
            cin >> x;
            change(root[t],root[i],l,r,x);
        }else{
            root[i] = root[t];
            cout << query(root[t],l,r) << endl;
        }
    }
    return 0;
}
//2 3 6 4 1
//3 4 7 5 2