无聊的数列

无聊的数列

题目描述

维护一个数列{a[i]}，支持两种操作：

1、1 L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。即：令a[L]=a[L]+K，a[L+1]=a[L+1]+K+D，

a[L+2]=a[L+2]+K+2D……a[R]=a[R]+K+(R-L)D。

2、2 P：询问序列的第P个数的值a[P]。

输入格式

第一行两个整数数n，m，表示数列长度和操作个数。

第二行n个整数，第i个数表示a[i]（i=1,2,3…,n）。

接下来的m行，表示m个操作，有两种形式：

1 L R K D

2 P 字母意义见描述（L≤R）。

输出格式

对于每个询问，输出答案，每个答案占一行。

输入样例
5 2
1 2 3 4 5
1 2 4 1 2
2 3　
输出样例
6
说明/提示
数据规模：

0≤n，m≤100000

|a[i]|，|K|，|D|≤200

我们考虑，对于一段区间 $[l, r]$

QwQ哇，那可以只使用这个线段树进行一个标记下传了（所以没有up函数）

这里展示一下pushdown的部分
$f [r o o t] . d$

因为，等差数列相加依然是等差数列，所以对于公差和首相，可以直接加

对一个区间的话 $[l, r]$
#include <bits/stdc++.h>
using namespace std;

const int maxn=100010;

struct node
{
    int d,first;
} tree[maxn*4];

int a[maxn],n,m;

void pushdown(int rt,int l,int r)
{
    if (tree[rt].d||tree[rt].first)
    {
        int mid=(l+r)>>1;
        tree[rt<<1].d+=tree[rt].d;
        tree[rt<<1|1].d+=tree[rt].d;
        tree[rt<<1].first+=tree[rt].first;
        tree[rt<<1|1].first+=(tree[rt].first+(mid-l+1)*tree[rt].d);
        tree[rt].d=tree[rt].first=0;
    }
}

void update(int rt,int l,int r,int x,int y,int first,int d)
{
    if (x<=l&&r<=y)
    {
        tree[rt].d+=d;
        tree[rt].first+=(l-x)*d+first;
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if (x<=mid)
    {
        update(rt<<1,l,mid,x,y,first,d);
    }
    if (y>mid)
    {
        update(rt<<1|1,mid+1,r,x,y,first,d);
    }
}
int query(int rt,int l,int r,int pos)
{
    if (l==r)
    {
        return a[l]+tree[rt].first;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if (pos<=mid)
    {
        return query(rt<<1,l,mid,pos);
    }
    else
    {
        return query(rt<<1|1,mid+1,r,pos);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    while (m--)
    {
        int flag;
        scanf("%d",&flag);
        if (flag==1)
        {
            int l,r,k,d;
            scanf("%d%d%d%d",&l,&r,&k,&d);
            update(1,1,n,l,r,k,d);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d
",query(1,1,n,x));
        }
    }
    return 0;
}
　　