LOJ#6277. 数列分块入门 1

给出一个长为

第一行输入一个数字

第二行输入

接下来输入

若

对于每次询问，输出一行一个数字表示答案。

样例输入

样例输出

2
5

对于 $的数据，1≤n≤50000,−2^31≤others、ans≤2^31−1。$

/*
    分块做法 复杂度O(n*sqrt(n))
*/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4+5;

int a[maxn],c[maxn];
int n,size,now,last;

int getBlock(int x){
    return (x - 1)/size + 1;//获得x在哪个块
}
int getStart(int x){
    return (x - 1) * size + 1;//获取第x块的开头元素
}

int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%d",&now);
        a[i] = now - last;
        last = now;//差分
    }
    size = sqrt(n);//每个块大小为sqrt(n)最优
    for(int i = 1;i <= n;i++){
        c[getBlock(i)] += a[i];//预处理每一个块
    }
    while(n--){
        int opt,l,r,p;
        scanf("%d%d%d%d",&opt,&l,&r,&p);
        if(opt == 0){
            a[l] += p;c[getBlock(l)] += p;
            a[r+1] -= p;c[getBlock(r+1)] -= p;//区间加
        }else{
            if(getBlock(r) == 1){//分r在第一个块和不在第一个块讨论
                int ans = 0;
                for(int i = 1;i <= r;i++){
                    ans += a[i];//如果在同一个块，直接暴力加
                }
                printf("%d
",ans);
            }else{
                int ans = 0;
                for(int i = 1;i <= getBlock(r) - 1;i++){//枚举每一个完整的块
                    ans += c[i];//累加
                }
                for(int i = getStart(getBlock(r));i <= r;i++){//枚举单个元素
                    ans += a[i];//累加
                }
                printf("%d
",ans);//点查询
            }
        }
    }
    return 0;
}

分块差分思路

/*
    树状数组做法 复杂度O(nlogn)
*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4+5;

int c[maxn],n,now,last;

int lowbit(int x){
    return x & -x;
}

void add(int x,int y){
    for(;x <= n;x += lowbit(x)) c[x] += y;
}

int query(int x){
    int res = 0;
    for(;x >= 1;x -= lowbit(x)) res += c[x];
    return res;
}//树状数组板子

int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%d",&now);
        add(i,now-last);
        last = now;//求差分
    }
    for(int i = 1;i <= n;i++){
        int opt,l,r,p;
        scanf("%d%d%d%d",&opt,&l,&r,&p);
        if(opt == 0){
            add(l,p);add(r+1,-p);//区间修改
        }else{
            printf("%d
",query(r));//单点查询
        }
    }
    return 0;
}

树状数组

/*
    线段树做法 复杂度O(nlogn)
    直接用区间修改区间查询的板子就好了
*/

#include <cstdio>

#define lchild (o<<1)
#define rchild (o<<1|1)
#define ll long long

const int MAXN = 100000;

ll a[MAXN],sumv[MAXN<<2],addv[MAXN<<2];

inline void pushup(ll o)
{
    sumv[o] = sumv[lchild] + sumv[rchild];
}

inline void pushdown(ll o,ll l,ll r)
{
    ll mid=(l+r) >> 1;
    addv[lchild] += addv[o];addv[rchild] += addv[o];
    sumv[lchild] += addv[o] * (mid-l+1);sumv[rchild] += addv[o] * (r-mid);
    addv[o] = 0;
}

inline void build(ll o,ll l,ll r)
{
    addv[o] = 0;
    if(l == r) {sumv[o] = a[l];return;}
    int mid = (l+r) >> 1;
    build(lchild,l,mid);
    build(rchild,mid+1,r);
    pushup(o);
}

inline void adds(ll l,ll r,ll o,ll lli,ll rri,ll v)
{
    if(lli <= l && rri >= r)
    {
        sumv[o] += v*(r-l+1);addv[o] += v;return ;
    }
    int mid = (l+r) >> 1;
    pushdown(o,l,r);
    if(lli <= mid) adds(l,mid,lchild,lli,rri,v);
    if(rri > mid) adds(mid+1,r,rchild,lli,rri,v);
    pushup(o);
}

inline ll query(ll l,ll r,ll o,ll lli,ll rri)
{
    if(lli <= l && rri >= r)
    {
        return sumv[o];
    }
    ll mid = (l+r) >> 1,ans = 0;
    pushdown(o,l,r);
    if(lli <= mid) ans += query(l,mid,lchild,lli,rri);
    if(rri > mid) ans += query(mid+1,r,rchild,lli,rri);
    return ans;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i = 1;i <= n;i++)
    {
        int opt,l,r,p;
        scanf("%d%d%d%d",&opt,&l,&r,&p);
        if(opt == 0){
                adds(1,n,1,l,r,p);
            }
            else{
                printf("%lld
",query(1,n,1,r,r));
            }
    }
    return 0;
}

线段树

LOJ#6277. 数列分块入门 1

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示