无聊的数列

题目背景

无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的 YYB 想出了一道无聊的题：无聊的数列。。。

题目描述

维护一个数列 $a_i$，支持两种操作：

• 1 l r K D：给出一个长度等于 $r-l+1$ 的等差数列，首项为 $K$，公差为 $D$，并将它对应加到 $[l,r]$ 范围中的每一个数上。即：令 $a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D$。
• 2 p：询问序列的第 $p$ 个数的值 $a_p$。

输入格式

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

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

接下来的 $m$ 行，每行先输入一个整数 $opt$。

若 $opt=1$ 则再输入四个整数 $l\ r\ K\ D$；

若 $opt=2$ 则再输入一个整数 $p$。

输出格式

对于每个询问，一行一个整数表示答案。

样例 #1

样例输入 #1

5 2
1 2 3 4 5
1 2 4 1 2
2 3

样例输出 #1

6

提示

数据规模与约定

对于 $100\%$ 数据，$0\le n,m \le 10^5,-200\le a_i,K,D\le 200, 1 \leq l \leq r \leq n, 1 \leq p \leq n$。

代码

#include <Bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 3;
ll w[4 * maxn],lzy[4 * maxn],lzx[4 * maxn];
int a[maxn];
//lzx首项延迟标记，lzy公差延迟标记
int n,m;
void pushup(const int u) {
  w[u] = w[2 * u] + w[2 * u + 1];
}
void build(const int u,int L,int R) {
  if (L == R) {
    w[u] = a[L];
    return;
  }
  int mid = (L + R) / 2;
  build(2 * u,L,mid),build(2 * u + 1,mid + 1,R);
  pushup(u);
}
bool InRange(int L,int R,int l,int r) {
  return (L >= l) && (R <= r);
}
bool OutofRange(int L,int R,int l,int r) {
  return (L > r) || (R < l);
}
ll S(int ax,int ay,int len) {
  int an = ax + ay * (len - 1ll);
  return 1ll * (an + ax) * len / 2;
}
void maketag(int u,int L,int R,int add_x,int add_y) {
  lzx[u] += add_x,lzy[u] += add_y;
  w[u] += S(add_x,add_y,R - L + 1);
//  cout << u << " " << L << " " << R << " " << add_x << " " << 
//  add_y << " " << w[u] << " " << lzx[u] << " " << lzy[u] << endl;
}
void pushdown(int u,int L,int R) {
  int mid = (L + R) / 2;
  maketag(2 * u,L,mid,lzx[u],lzy[u]);
  maketag(2 * u + 1,mid + 1,R,lzx[u],lzy[u]);
  lzx[u] = lzy[u] = 0;
}
ll query(int u,int L,int R,int l,int r) {
  if (InRange(L,R,l,r)) return w[u];
  else if (!OutofRange(L,R,l,r)) {
    int mid = (L + R) / 2;
    pushdown(u,L,R);
    return query(2 * u,L,mid,l,r) 
    + query(2 * u + 1,mid + 1,R,l,r);
  }
  return 0;
}
void update(int u,int L,int R,int l,int r,int add_x,int add_y) {
  //cout << u << " " << L << " " << R << " " 
  //<< l << " " << r << " " << add_x << " " << add_y << endl;
  if (InRange(L,R,l,r)) maketag(u,L,R,add_x,add_y);
  else if (!OutofRange(L,R,l,r)) {
    int mid = (L + R) / 2;
    pushdown(u,L,R);
    update(2 * u,L,mid,l,r,add_x,add_y);
    update(2 * u + 1,mid + 1,R,l,r,add_x,add_y);
    pushup(u);
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build(1,1,n);
  for (int i = 1; i <= m; i++) {
    int opt;
    cin >> opt;
    if (opt == 1) {
      int l,r,K,D;
      cin >> l >> r >> K >> D;
      update(1,1,n,l,r,K,D);
    }
    if (opt == 2) {
      int p;
      cin >> p;
      cout << query(1,1,n,p,p) << endl;
    }
  }
  return 0;
}