2018.2.26

1517460958dyc · 2018-03-01 22:14:08 · 个人记录

Accepted 模板代码 832mS/8097kB

开O2后 592mS/8195kB

开O3后 484mS/8187kB

#include<iostream>
//#pragma GCC optimize()
using namespace std;
struct node
{
    int l,r;
    long long val,lazy;
};
node tree[400010];
int n,m;
inline void build(int root,int l,int r)
{
    tree[root].l=l;
    tree[root].r=r;
    if (l==r)
    {
        cin>>tree[root].val;
        return ;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    tree[root].val=tree[root*2].val+tree[root*2+1].val;
}
inline void pushdown(int root)
{
    if (tree[root].lazy)
    {
        tree[root*2].lazy+=tree[root].lazy;
        tree[root*2+1].lazy+=tree[root].lazy;
        tree[root*2].val+=(tree[root*2].r-tree[root*2].l+1)*tree[root].lazy;
        tree[root*2+1].val+=(tree[root*2+1].r-tree[root*2+1].l+1)*tree[root].lazy;
        tree[root].lazy=0;
    }
}
inline void update(int root,int l,int r,long long add)
{
    if (tree[root].l>=l&&tree[root].r<=r)
    {
        tree[root].lazy+=add;
        tree[root].val+=(tree[root].r-tree[root].l+1)*add;
        return ;
    }
    if (tree[root].l>r||tree[root].r<l)
        return ;
    if (tree[root].lazy)
        pushdown(root);
    update(root*2,l,r,add);
    update(root*2+1,l,r,add);
    tree[root].val=tree[root*2].val+tree[root*2+1].val;
}
inline long long query(int root,int l,int r)
{
    if (tree[root].l>=l&&tree[root].r<=r)
        return tree[root].val;
    if (tree[root].l>r||tree[root].r<l)
        return 0;
    if (tree[root].lazy)
        pushdown(root);
    return query(root*2,l,r)+query(root*2+1,l,r);
}
int main()
{
    cin.sync_with_stdio(false);
    cin>>n>>m;
    build(1,1,n);
    int code,x,y;
    long long add;
    for (int i=1;i<=m;i++)
    {
        cin>>code>>x>>y;
        if (code-1)
            cout<<query(1,x,y)<<endl;
        else
        {
            cin>>add;
            update(1,x,y,add);
        }
    }
    return 0;
}