P1438 无聊的数列


区间加等差数列模板,维护a的差分数组c,对于$l-r$的首项为k公差为d的等差数列,只要对c进行3个操作$c[l]+k$ , $c[l+1-r]+d$ , $c[r+1]-(k+(r-l)*d)$,直接线段树维护c的区间加 区间查询即可,注意在更新时候要特判$l=r$与$r=n$的情况

#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,m,a[maxn],c[maxn];
struct node{
    int l,r,add,sum;
}tree[maxn<<2];
void build(int id,int l,int r)
{
    tree[id].l=l,tree[id].r=r;
    if(l==r)
    {
        tree[id].sum=c[l];
        return;
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
}
void putdown(int id)
{
    if(tree[id].add)
    {
        tree[id<<1].sum+=tree[id].add*(tree[id<<1].r-tree[id<<1].l+1);
        tree[id<<1|1].sum+=tree[id].add*(tree[id<<1|1].r-tree[id<<1|1].l+1);
        tree[id<<1].add+=tree[id].add;
        tree[id<<1|1].add+=tree[id].add;
        tree[id].add=0;
    }
}
void change(int id,int l,int r,int k)
{
    if(l<=tree[id].l&&r>=tree[id].r)
    {
        tree[id].sum+=k*(tree[id].r-tree[id].l+1);
        tree[id].add+=k;
        return;
    }
    putdown(id);
    int mid=(tree[id].l+tree[id].r)>>1;
    if(l<=mid) change(id<<1,l,r,k);
    if(r>mid) change(id<<1|1,l,r,k);
    tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
}
int query(int id,int l,int r)
{
    if(l<=tree[id].l&&r>=tree[id].r) return tree[id].sum;
    putdown(id);
    int mid=(tree[id].l+tree[id].r)>>1;
    int res=0;
    if(l<=mid) res+=query(id<<1,l,r);
    if(r>mid) res+=query(id<<1|1,l,r);
    return res;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) c[i]=a[i]-a[i-1];
    build(1,1,n);
    while(m--)
    {
        int p,x,y,z,q;
        p=read();
        if(p==1)
        {
            x=read(),y=read(),z=read(),q=read();
            change(1,x,x,z);
            if(x<y) change(1,x+1,y,q);
            if(y<n) change(1,y+1,y+1,-(z+(y-x)*q));
        }
        else
        {
            x=read();
            printf("%d\n",query(1,1,x));
        }
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P1073 最优贸易 P1073 最优贸易
似乎题解里都是两遍spfa,加堆优化的dijkstra也能过,这道题其实求出两个点a b要b-a最大,而且b的遍历顺序要在a后面,可以考虑两次dijkstra来维护d与v两数组处理,d表示走到这个节点前面能买到的最便宜的货,f表示这个节点往
2019-07-06
下一篇 
P2024 食物链 P2024 食物链
带权并查集题解PS:题解参考了许多dalao的文章所以难免有既视感,请见谅 一般普通的并查集只能确定节点与父节点的关系,但比如像是食物链这种类型的题目,给定了ABC的关系,这个时候就需要给并查集加权,这个权一般用来表示两个节点之间的关系,由
2019-07-06
  目录