分块感觉也没必要讲多了,人家hzwer讲得多好……%%hzw%%orz。
传送门

再贴个我写的分块区间增减、区间求和。
题目:洛谷P3372【模板】线段树 1 传送门

思想:把大小为n的数组分成√n块,每块含√n个元素。(因为把大小为n的数组分成√n块是最好的分法,具体怎么证我不知道~= ̄ω ̄=)然后对于每次修改区间[l,r],先单独处理l~l所在的块的末尾元素和r所在的块的开始元素~r,最坏情况复杂度使2×√n,然后中间的都是整块整块的块了,所以我们把每个块都做上懒惰标记就行了。(懒惰标记不知道的去看我的那篇线段树入门!)中间最多有√n块,所以整个操作的复杂度不会超过3×√n。查询也是一个套路,只不过要每次加上懒惰标记值。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,sqn,bl[100005];
ll v[100005],d[405],atag[405],x;
void update(int l,int r,ll k)
{
    int lim=min(bl[l]*sqn,r);
    for(int i=l;i<=lim;i++)v[i]+=k,d[bl[i]]+=k;
    if(bl[l]!=bl[r])for(int i=(bl[r]-1)*sqn+1;i<=r;i++)v[i]+=k,d[bl[i]]+=k;
    for(int i=bl[l]+1;i<bl[r];i++)atag[i]+=k;
}
ll getsum(int l,int r)
{
    int lim=min(bl[l]*sqn,r);ll sum=0;
    for(int i=l;i<=lim;i++)sum+=v[i]+atag[bl[i]];
    if(bl[l]!=bl[r])for(int i=(bl[r]-1)*sqn+1;i<=r;i++)sum+=v[i]+atag[bl[i]];
    for(int i=bl[l]+1;i<bl[r];i++)sum+=d[i]+sqn*atag[i];
    return sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m,sqn=(int)(sqrt(n));
    for(int i=1;i<=n;i++)cin>>v[i],bl[i]=(i-1)/sqn+1,d[bl[i]]+=v[i];
    for(int i=1,a,b,c;i<=m;i++)
    {
        cin>>a>>b>>c;
        if(a==1)cin>>x,update(b,c,x);
        else cout<<getsum(b,c)<<endl;
    }
    return 0;
}

分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

piano · 2017年7月2日 2:56 下午

大佬强啊,orzXZYshenben

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *