P1438 无聊的数列
题目背景
无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的 YYB 想出了一道无聊的题：无聊的数列。。。
题目描述
维护一个数列aia_iai，支持两种操作：
1 l r K D：给出一个长度等于r−l+1r-l+1r−l+1的等差数列，首项为KKK，公差为DDD，并将它对应加到[l,r][l,r][l,r]范围中的每一个数上。即：令al=al+K,al+1=al+1+K+D…ar=ar+K+(r−l)×Da_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times Dal=al+K,al+1=al+1+K+D…ar=ar+K+(r−l)×D。2 p：询问序列的第ppp个数的值apa_pap。
输入格式
第一行两个整数n,mn,mn,m表示数列长度和操作个数。
第二行nnn个整数，第iii个数表示aia_iai。
接下来的mmm行，每行先输入一个整数optoptopt。
若opt=1opt=1opt=1则再输入四个整数l r K Dl\ r\ K\ DlrKD；
若opt=2opt=2opt=2则再输入一个整数ppp。
输出格式
对于每个询问，一行一个整数表示答案。
输入输出样例 #1
输入 #1
5 2 1 2 3 4 5 1 2 4 1 2 2 3输出 #1
6说明/提示
数据规模与约定
对于100%100\%100%数据，0≤n,m≤105,−200≤ai,K,D≤200,1≤l≤r≤n,1≤p≤n0\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 n0≤n,m≤105,−200≤ai,K,D≤200,1≤l≤r≤n,1≤p≤n。
图解
代码+注释
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongintll;constintN=1e5+5;structnode{//线段树各节点(表示原数列的不同区间)intl,r,//该区间在原数列的区间左右边界c,//懒标记1,区间内单元素关于等差数列增量的“基础部分 ”d;//懒标记2,用于计算区间等差数列和的因pos递增的部分/* 原数列下标 1 2 3 4 5 6 7 8 9 10 原数列数值 8 2 5 4 9 7 3 10 6 1 在原数列的L=4、R=7区间间增加等差数列 等差数列下标 1 2 3 4 等差数列数值 13 16 19 22 区间:l=1,r=4,len=r-l+1=4 区间和：13+16+19+22=70 区间和：等差数列任意连续区间的和 = 区间平均项值 × 区间项数 区间和：len*(d(l)+d(r))/2=4*(13+22)/2=70 ———————————————— 首项k=13，公差d=3 等差数列各元素下标pos 等差数列pos下标处的值：k+(pos-l)*d=k+pos*d-l*d=(k-l*d)+pos*d=c+pos*d 懒标记1:c=k-l*d=13-4*3=1 懒标记2:d=3 区间和：pos从1到4该等差数列元素(c+pos*d)的和=len*c+len原序列序号*d 其中，len和=len*(l+r)/2=4*(4+7)/2=22 ———————————————— 懒标记1部分=len*c=4*1=4 + 懒标记2部分=len长原序列序号和*d=和(4,5,6,7)*d=len*(l+r)/2=4*(4+7)/2=22*3=66 =70 */ll val;//区间值}tree[4*N];//数组存储线段树各节点，每节点表示原数列的不同区间。左子=父*2，右子=父*2+1intn,q,arr[N];//原数列voidbuild(intf,intl,intr){//构建线段树tree[f].l=l,tree[f].r=r,tree[f].c=tree[f].d=0;//初始化线段树每节点对应原数列区间的左右边界和双懒标记if(l==r){tree[f].val=arr[l];return;}//细分到区间左右边界重合，最小区间，对应原数列某元素intm=l+((r-l)>>1);//区间中点build(f<<1,l,m);//递归，左半区间构建线段树build(f<<1|1,m+1,r);//右半区间tree[f].val=tree[f<<1].val+tree[f<<1|1].val;//更新区间值=左子区间区间值+右子区间区间值}voidpushdown(intf){//下传双懒标记node&root=tree[f],&l=tree[f<<1],&r=tree[f<<1|1];//建立区间和区间左右子区间的引用if(root.c==0&&root.d==0)return;//该区间没有双懒标记，则停止下传intllen=l.r-l.l+1;//左子区间宽度l.val+=root.c*llen+(ll)root.d*llen*(l.l+l.r)/2;//增加左子区间区间值。llen*(l.l+l.r)/2该区间等差数列和l.c+=root.c;l.d+=root.d;//左子区间下传双懒标记intrlen=r.r-r.l+1;//右子区间宽度r.val+=root.c*rlen+(ll)root.d*rlen*(r.l+r.r)/2;//增加右子区间区间值r.c+=root.c;r.d+=root.d;//往右子区间下传双懒标记root.c=root.d=0;//清空该区间双懒标记}voidadd(intf,ints,inte,intc,intd){//增加区间区间值intl=tree[f].l,r=tree[f].r,len=r-l+1,m=l+((r-l)>>1);//区间左右边界，区间宽度，区间中点if(s<=l&&r<=e){//该区间完全在操作区间内tree[f].val+=c*len+(ll)d*len*(l+r)/2;//计算出整个区间的区间增加值tree[f].c+=c,tree[f].d+=d;//放置双懒标记，以备往后提到该节点时下传双懒标记return;//递归基，是递和归间的转换点，往后就得归}pushdown(f);//下传此前得到的双懒标记if(s<=m)add(f<<1,s,e,c,d);//递归，在左区间增加区间增加值if(m<e)add(f<<1|1,s,e,c,d);//递归，右子区间tree[f].val=tree[f<<1].val+tree[f<<1|1].val;//更新该节点的区间值=左右子区间区间值的和}llquery(intf,intx){//查找原数组某下标的新值intl=tree[f].l,r=tree[f].r,m=l+((r-l)>>1);if(l==r)returntree[f].val;//左右边界重叠，说明找到了pushdown(f);//下传以前得到的双懒标记if(x<=m)returnquery(f<<1,x);//在左区间找elsereturnquery(f<<1|1,x);//在右区间找}intmain(){//freopen("data.cpp","r",stdin);cin>>n>>q;for(inti=1;i<=n;i++)cin>>arr[i];build(1,1,n);//建立线段树while(q--){//操作次数intop;cin>>op;//操作类型if(op==1){intl,r,k,d,c;cin>>l>>r>>k>>d;c=k-l*d;add(1,l,r,c,d);//给l到r区间增加k开始公差为d的公差数列}else{intx;cin>>x;cout<<query(1,x)<<endl;//查询原数组x位置在线段树中的新值}}return0;}小结
- 原数组是原始数据载体，所有区间操作的目标，都是面向「原数组」的指定区间进行的。
- 线段树数组，是对原数组的区间重构与分层存储，所有区间操作的计算、标记、结果，最终都体现在线段树数组的节点中。
- 线段树的父子节点下标关系固定：左子节点下标 = 2父节点下标，右子节点下标 = 2父节点下标+1。
- 线段树的每个节点都维护区间边界 tree[f].l 和 tree[f].r，该边界就是映射「原数组」的一段连续区间范围。
- 本题线段树的核心功能：实现「原数组指定区间」加等差数列，并支持单点查询，核心计算是求【区间等差数列的总增量和】。
- 对原数组的操作区间[l,r][l, r][l,r]，加首项为kkk、公差为ddd的等差数列 → 原数组中任意位置pos\boldsymbol{pos}pos（l≤pos≤rl\le pos\le rl≤pos≤r）的增量值 =k+(pos−l)∗d\boldsymbol{k + (pos-l)*d}k+(pos−l)∗d；其中lll是本次区间操作的左边界。
- 操作区间lll到rrr的等差数列总增量和=len×c+(区间下标和)×d\boldsymbol{len\times c + (区间下标和) \times d}len×c+(区间下标和)×d；
其中：c=k−l×dc = k - l\times dc=k−l×d，len=r−l+1len = r-l+1len=r−l+1（区间长度），区间下标和 =len×(l+r)2\frac{len\times(l+r)}{2}2len×(l+r)；
补充：区间下标和 → 就是原数组操作区间[l,r][l,r][l,r]内所有位置pos的总和（pos从l到r连续）。
