[JSOI2009]等差数列

2021-04-21 16:29

阅读：663

标签：void oid while 线段树 for val 维护 struct 第一篇

第一篇博客哒

题目链接

首先看到区间加等差数列我们可以首先想到使用差分数组

就是记一个\(b_i\)=\(a_{i+1}\)-\(a_i\)

然后每次修改\(a_l\) 到\(a_r\)就只用将\(b_{l-1}\),\(b_r\)单点修改,\(b_l\)至\(b_{r-1}\)区间修改就可以了

区间修改？我们首先想到了线段树

线段树可以维护是否为等差数列吗？？？

可以！

每个结点维护上啥线段树必要的l,r,lazy标记什么的在多维护一个结构体val

val 里面有什么呢？

首先为了下面转移方便维护区间最左边lv，最右边的点的值rv

然后维护ls,rs,nos,lrs

分别表示[l,r) (l,r] (l,r) [l,r] 区间的答案

开始转移我们考虑合并区间a,和区间b

考虑\(a_r\) \(b_l\)这两个点

有以下三种情况

1.可以直接合并。如果两者的差值相同，则可以将原来的等差数列合并为一个

2.a两侧都不选，左边的右端点作为一个等差数列的首项(所以不选)，b就要选择左端点(因为他不用考虑做首项了)

3.a选右端点，b的左端点作为一个等差数列的首项，所以b两边都不选

如何操作，看代码吧

#include
inline int min(int a,int b){return avoid read(T &x){
    x=0;int f=0;char ch=getchar();
    while(ch'9') {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch>1;
  build(pos>1;
  if(ymid) modify(pos>1;
  pushdown(pos);
  if(ymid) return query(pos

[JSOI2009]等差数列

标签：void oid while 线段树 for val 维护 struct 第一篇

原文地址：https://www.cnblogs.com/Phoenix41/p/12248244.html

上一篇：tensorflow 2.0 学习（十一）卷积神经网络（一）MNIST数据集训练与预测 LeNet-5网络

下一篇：关于WebSocket学习记录（一）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[JSOI2009]等差数列
文章链接：http://soscw.com/essay/77689.html

亲，登录后才可以留言！

[JSOI2009]等差数列

题目链接

1.可以直接合并。如果两者的差值相同，则可以将原来的等差数列合并为一个

2.a两侧都不选，左边的右端点作为一个等差数列的首项(所以不选)，b就要选择左端点(因为他不用考虑做首项了)

3.a选右端点，b的左端点作为一个等差数列的首项，所以b两边都不选

评论

热门文章

推荐文章

最新文章

置顶文章