首页 > 其他分享 >P1438 无聊的数列

P1438 无聊的数列

时间:2023-07-12 13:34:34浏览次数:35  
标签:数列 无聊 tr int && cr 等差数列 P1438

原题链接戳这里

考试的时候打的这道题 硬是想了半天想不出来 回来一看觉得自己真的智慧

等差数列的意思是什么? 在一个数列的第二项及以后 所有的项与前一项的差值相同

将这一点反应到差分数组中去

原数列:   0 0 0 0 0 0
等差数列: 1 3 5 7 9
现数列:   1 3 5 7 9 0
现等差数列 1 2 2 2 2 -9

那么如果我要对一个数列的 [l,r] 加上首项为 k 公差为 d 的等差数列
大概就像这样

l r r+1
k d d d d -((r-l)*d+k)

观察一下这样的操作 发现需要频繁的维护一段区间的同时也需要查询一段区间 因此考虑线段树

因为所有操作只涉及到加法,普通线段树即可解决

点击查看代码
#include<bits/stdc++.h>
using namespace std;

#define N 100005
#define int long long

int n,m;
int a[N];
int l,r,k,d;

struct node{
	int val=0,addt=0;
}tr[N<<2];

inline int read()
{
	int x=0;
	bool f=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())
		if(ch=='-')
			f=0;
	for(;isdigit(ch);ch=getchar())
		x=(x<<1)+(x<<3)+ch-'0';
	return f?x:(~(x-1));
}

void pushup(int x)
{
	tr[x].val=tr[x<<1].val+tr[x<<1|1].val;
}

void pushdown(int x,int cl,int cr)
{
	int cmid=(cl+cr)>>1;
	tr[x<<1].val+=tr[x].addt*(cmid-cl+1);
	tr[x<<1|1].val+=tr[x].addt*(cr-cmid);
	tr[x<<1].addt+=tr[x].addt;
	tr[x<<1|1].addt+=tr[x].addt;
	tr[x].addt=0;
}

void update(int l,int r,int val,int x=1,int cl=1,int cr=n)
{
	if(cl>=l&&cr<=r)
	{
		tr[x].val+=val*(cr-cl+1);
		tr[x].addt+=val;
		return ;
	}
	int cmid=(cl+cr)>>1;
	pushdown(x,cl,cr);//经过了x点 顺便把它下放了
	if(l<=cmid)
	{
		update(l,r,val,x<<1,cl,cmid);
	} 
	if(r>cmid)
	{
		update(l,r,val,x<<1|1,cmid+1,cr);
	}
	pushup(x);//!!!!!!!!!!!!!!
}

int query(int l,int r,int x=1,int cl=1,int cr=n)
{
	if(cl>=l&&cr<=r)
	{
		return tr[x].val;
	}
	int cmid=(cl+cr)>>1;
	pushdown(x,cl,cr);//经过了x点 顺便把它下放了
	if(l>cmid)
	{
		return query(l,r,x<<1|1,cmid+1,cr);
	}
	else if(r<=cmid)
	{
		return query(l,r,x<<1,cl,cmid);
	}
	else
		return query(l,r,x<<1,cl,cmid)+query(l,r,x<<1|1,cmid+1,cr);
}

void build(int x,int cl,int cr)
{
	if(cl==cr)//到达了叶子结点
	{
		tr[x].val=a[cl];
		return ;
	} 
	int cmid=(cl+cr)>>1;
	build(x<<1,cl,cmid);
	build(x<<1|1,cmid+1,cr);
	pushup(x);//'递 '完成后开始'归 '(上传) 
}

main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=n-1;i>0;i--)a[i+1]-=a[i];//构建差分数组 
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		l=read();
		if(l==1)
		{
			l=read();r=read();k=read();d=read();
			update(l,l,k);
			if(l+1<=r)update(l+1,r,d);
			if(r<n)update(r+1,r+1,-(k+(r-l)*d));
		}
		else
		{
			l=read();
			cout<<query(1,l)<<endl;
		}
	}
	return 0;
}

标签:数列,无聊,tr,int,&&,cr,等差数列,P1438
From: https://www.cnblogs.com/pigAlg/p/17547262.html

相关文章

  • P5550 Chino的数列
    很想模拟,但是数据太大啦(悲。然后我想着用\(map\)映射来做,想着模拟几轮发现周期,然后映射求解。但是不知道为什么写崩了。勉强贴贴,反正不是正解(#include<bits/stdc++.h>#definelllonglong#definereregisterusingnamespacestd;constintN=80+10,INF=0x3f3f3f3f;lln,......
  • 无聊摘抄写写
    howcanwestartlearningPeopleoftenwonderhowothersbecomehackers(securityconsultants)ordefenders(securityanalystsfightingcybercrime),andtheanswerissimple.Breakitdown,learnanareaofcybersecurityyou'reinterestedin,andre......
  • 高等数学——数列的极限
    数列的极限定义数列:\(x_{1},x_{2},\dots,x_{n},\dots\)是一个从小到大的序列,称为数列,记为\(\{x_{n}\}\)其中\(x_{1}\)叫做项,\(x_{n}\)称为通项(一般项)。数列极限:设\(\{x_{n}\}\)是一个数列,\(\forall\varepsilon>0,\existsN\),使当\(n>N\)时,$|x_{n}-a|<\varepsilon$......
  • 快速等比数列求和
    快速等比数列求和1.等比数列求和公式要求给定的取余的数是质数,能求出逆元2.递归分解如果有偶数个,那么分解成两半,左边就为\(a_0+a_0q+a_0q^2...+a_0q^{n/2}\),另一半为\(a_0q^{n/2+1}+a_0q^{n/2+2}+a_0q^{n/2+3}...+a_0q^{n}\),令等比数列求和为一个函数\(f(n)\),就有\(f(n)=f......
  • 「学习笔记」数列分块入门 1 ~ 9
    一天多一点的时间,做完了这\(9\)道题,除了最后一道题之外,都感觉良好.这里是黄学长的博客.数列分块入门1区间加法,单点查值.很入门的题目了.暴力处理两边不完整的块,完整的块维护一个tag加法标记./*Thecodewaswrittenbyyifan,andyifanisneutral!!!......
  • 数列分块入门
    1.数列分块入门1区间修改,单点查询点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintMAXN=5e4+5;intn,len,cnt;inta[MAXN],tag[MAXN];intpos[MAXN],l[MAXN],r[MAXN];inlinevoidadd(intx,inty,intk){if(x>y)retu......
  • js 实现斐波那契数列
    O2^N算法,常规写法,递归实现functionfib(n){if(n==0||n===1)return1;returnfib(n-1)+fib(n-2);};console.log(fib(3));//5console.log(fib(5));//8O(N)算法,动态规划,重叠子问题functionfibonacci(n){if(n<=1)returnn;......
  • 数列分段 Section II
    数列分段SectionII题目描述对于给定的一个长度为N的正整数数列\(A_{1\simN}\),现要将其分成\(M\)(\(M\leqN\))段,并要求每段连续,且每段和的最大值最小。关于最大值最小:例如一数列\(4\2\4\5\1\)要分成\(3\)段。将其如下分段:\[[4\2][4\5][1]\]第一段和为\(6\),第......
  • 关于实数列上下极限一个定理的注解分析
    Ayumu的数学分析第18课讲到如下一个定理:这个定理没有什么问题.但是随后的注解部分是有问题的,摘录如下:在注解的扩展定义中,E可以涵盖上极限是-∞的情形,但不能涵盖上极限是+∞的情形;同样,F可以涵盖下极限是+∞的情形,但不能涵盖下极限是-∞的情形.具体看几个例子.......
  • 题解 P4108【[HEOI2015]公约数数列】
    看到这种奇怪的操作,首先想到分块。以下记值域为\(w\),块长为\(B\)。前缀\(\gcd\)显然单调不增,而且后一个必须是前一个的因数,如果变化至少要减半。因此,我们知道,共有\(\mathcalO(\logw)\)个不同的前缀\(\gcd\)。我们可以接受对这些块暴力,只需要对前缀\(\gcd\)都相同的块......