LOJ#6277. 数列分块入门 1-白红宇

LOJ#6277. 数列分块入门 1

阅读量：4605 次

发布时间：2019-06-09

本文共 4052 字，大约阅读时间需要 13 分钟。

给出一个长为

第一行输入一个数字

第二行输入

接下来输入

若

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

样例输入

41 2 2 30 1 3 11 0 1 00 1 2 21 0 2 0

样例输出

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

/*    分块做法 复杂度O(n*sqrt(n))*/#include 
         
          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\n",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\n",ans);//点查询            }        }    }    return 0;}

分块差分思路

/*    树状数组做法 复杂度O(nlogn)*/#include 
         
          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\n",query(r));//单点查询        }    }    return 0;}

树状数组

/*    线段树做法 复杂度O(nlogn)    直接用区间修改区间查询的板子就好了*/#include 
         
          #define lchild (o<<1)#define rchild (o<<1|1)#define ll long longconst 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\n",query(1,n,1,r,r));            }    }    return 0;}

线段树

转载于:https://www.cnblogs.com/bryce02/p/9888238.html

你可能感兴趣的文章

{Nodejs} request URL 中文乱码