【洛谷】【线段树】P1438 无聊的数列

题目背景

无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）

题目描述

维护一个数列{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）。

输出格式：

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

输入输出样例

输入样例#1： 

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

输出样例#1： 

6

说明

数据规模：

0≤n，m≤100000

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

【题意】：

这个题目就是  区域更新+单点询问。但是这个区域更新是按照等差数列来更新的。

【题解】：

第一次写线段树的题解，我认为这个博客很有必要写，中石油做的那个题一样，这个题目维护的就是a[i]，a[i] = 第i个元素 和 第(i-1)个元素 的差值，然后如果想表示第i个值，那么就是  [1,i] 区间求和得到。

这样就是维护一个差分数组即可，

区间更新：[L,R] 相当于 update( L, L, 首相) + update (L+1,R,公差) + update( R+1,R+1,首相+(len-1)*公差) 

区域更新需要写 pushdown + Add ()

但是这个题目有两个小坑，

1、L==R

2、R+1 == n

只要加以特判就不用更新这两个位置了。

#include 
using namespace std;
typedef long long ll;
const int N=1e6+1010;
ll a[N<<2],lazy[N<<2],b[N<<2],n,m;void Add(int No,int L,int R,ll w){lazy[No]+=w;a[No]+=(R-L+1ll)*w;return ;
}void pushdown(int No,int L,int R){if(lazy[No]==0) return;int Mid=(L+R)>>1;Add(No*2,L,Mid,lazy[No]);Add(No*2+1,Mid+1,R,lazy[No]);lazy[No]=0;
}void update(int No,int L,int R,int x,int y,ll v){if( y>1;if( x<=Mid)update(No*2,L,Mid,x,y,v);if( Mid>1;ll res = 0;if( x<= Mid) res+=query(No<<1,L,Mid,x,y);if( Mid>1;Build(No*2,L,Mid);Build(No*2+1,Mid+1,R);a[No] = a[No*2] + a[No*2+1];
}int main(){scanf("%lld%lld",&n,&m);memset(a,0,sizeof(a));memset(lazy,0,sizeof(lazy));for(int i=1; i<=n; i++)scanf("%lld",&b[i]);for(int i=n; i>=1; i--)b[i] = b[i] - b[i-1];Build(1,1,n);ll D,d,S,len,R,L,ins;while(m--){scanf("%lld",&ins);if(ins==1){scanf("%lld%lld%lld%lld",&L,&R,&D,&d);len = (R-L+1ll);update(1,1,n,L,L,D);if( L

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！