本文共 5755 字，大约阅读时间需要 19 分钟。

生命曲线

时间限制: 2 Sec 内存限制: 128 MB

题目描述

Mr.L最近得了妄想症，他对自己生命的历史和未来产生了一些幻觉。

他的眼前浮现出了自己的生命价值曲线。这条生命线不断地变化，使他不断怀疑着自己存在的意义…… Mr.L的生命价值曲线可以被简化为一个代表着Mr.L的每个阶段的生命价值的序列。其中第i个阶段的生命价值为vi。 当他预感自己成功或失败时，他的生命线上会递增或递减地增加或减少一些价值。他认为这些价值的变化量是形成等差数列的。 还有时候，他预感到自己的大起大落，此时他一段时间的生命价值会发生反转。 具体来说，若[l,r]时间内的生命价值发生了反转，则其中的每个价值都会变成 它原先价值的相反数。 他对自己在某段时间内的生命价值很感兴趣，所以还想求出某些时间段内的生命价值总和。 输入 第一行两个整数n和m。 第二行n个数，表示初始序列v。 以下m行每行3或5个数，表示每个操作。 1 l r a1 d：将第l个到第r个元素加上一个等差数列。 具体来说，对于i∈[l,r],vi=vi+ai-l+1 ，其中ai=a1+(i - 1)d 2 l r：求第l个到第r个数的和。 3 l r：第l个到第r个数反转（意义见上）。 输出 对于每个2操作输出一行一个数即第l个到第r个数的和。 样例输入 Copy 5 5 2 4 4 3 5 1 3 5 2 1 2 2 4 1 2 4 3 2 3 2 5 2 1 4 样例输出 Copy 16 -29 提示 样例解释： 初始生命价值为2 4 4 3 5 1 3 5 2 1操作后价值为2 4 6 6 9 2 2 4输出4+6+6=16 1 2 4 3 2操作后价值为2 7 11 13 9 3 2 5操作后价值为2-7-11-13-9 2 1 4输出2-7-11-13=-29

对于100%的数据，n,m≤5×10^5,vi,|a1|,|d|≤1000

注意答案可能不在[-2 ^ 31,2 ^ 31-1]的范围内

一个算是比较裸的 线段树+区间修改 的题了，然鹅太菜了，知道怎么做了还是调了半小时，细节处理的实在不是很好。

题中分为三个操作: (1)把 l ~ r 区间加上一个等差数列 (2)把 l ~ r 区间的数取反 (3)求 l ~ r 的区间数的总和 很明显结构体中需要存一个总和 sum，以及一个lazy标记 fz 用来表示将数反转。 第二个和第三个比较简单，直接lazy往下传就行了，主要是在于处理第一个加等差数列上。 对于操作 (1) 1.首先要知道等差数列+等差数列=等差数列 2.当修改时候区间不需要进行分裂的时候，直接把 a d sum 加到对应的结点上即可。 3.当区间需要进行分裂的时候，可以把它看成两部分，第一部分就是首项为a，公差为d的等差数列。而第二部分的公差仍然为d，首项就需要a+len*d，len为前面一部分的长度，具体可以看代码。 pushdown的时候要先看fz是否标记，之后再把 a d sum 传给下面的结点。 再就是注意一下算等差数列的和的时候要仔细点即可。。

代码还是分开看吧，全部代码在最后。

1.定义

int n,m;int w[N];struct Node{
   	int l,r;	LL fz,a,d,sum;}tr[N*4];

2.pushdown + pushup + 建树

个人感觉起的名字还是比较能看懂的吧。。

void pushup(int u){
   	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}void pushdown(int u){
   	if(tr[u].fz)	{
   		tr[u].fz=0;		tr[u<<1].fz^=1,tr[u<<1|1].fz^=1;		tr[u<<1].a=-tr[u<<1].a,tr[u<<1|1].a=-tr[u<<1|1].a;		tr[u<<1].d=-tr[u<<1].d,tr[u<<1|1].d=-tr[u<<1|1].d;		tr[u<<1].sum=-tr[u<<1].sum,tr[u<<1|1].sum=-tr[u<<1|1].sum;	}	if(tr[u].a!=0||tr[u].d!=0)	{
   		LL mid=tr[u].l+tr[u].r>>1;		LL llen=(tr[u<<1].r-tr[u<<1].l+1);		LL rlen=(tr[u<<1|1].r-tr[u<<1|1].l+1);		LL la=tr[u].a,ld=tr[u].d;		LL ra=la+llen*ld,rd=ld;		LL lsum=llen*(la*2+(llen-1)*ld)/2,rsum=rlen*(ra*2+(rlen-1)*rd)/2;					tr[u<<1].a+=la,tr[u<<1].d+=ld,tr[u<<1].sum+=lsum;		tr[u<<1|1].a+=ra,tr[u<<1|1].d+=rd,tr[u<<1|1].sum+=rsum;		tr[u].a=0,tr[u].d=0;	}}void build(int u,int l,int r){
   	if(l==r)	{
   		tr[u]={
   l,r,0,0,0,w[l]};		return;	}		tr[u]={
   l,r};	int mid=tr[u].l+tr[u].r>>1;	build(u<<1,l,mid),build(u<<1|1,mid+1,r);		pushup(u);}

3.区间加等差数列

这里注意一下求 t1 的时候 取max( tr[u].l , l ) ，这俩的位置不确定，手画一下图就可以看出来了。

void modify1(int u,int l,int r,LL a,LL d){
   	if(tr[u].l>=l&&tr[u].r<=r)	{
   		tr[u].a+=a,tr[u].d+=d;		LL len=tr[u].r-tr[u].l+1;		tr[u].sum+=len*(a*2+(len-1)*d)/2;		return;	}		pushdown(u);		int mid=tr[u].l+tr[u].r>>1;	if(r<=mid) modify1(u<<1,l,r,a,d);	else if(l>mid) modify1(u<<1|1,l,r,a,d);	else 	{
   		LL t1=a+(mid-max(l,tr[u].l)+1)*d;		modify1(u<<1,l,r,a,d);		modify1(u<<1|1,l,r,t1,d);	}		pushup(u);}

4.区间数反转

void modify2(int u,int l,int r){
   	if(tr[u].l>=l&&tr[u].r<=r)	{
   		tr[u].fz^=1;		tr[u].a=-tr[u].a,tr[u].d=-tr[u].d;		tr[u].sum=-tr[u].sum;		return;	}		pushdown(u);		int mid=tr[u].l+tr[u].r>>1;	if(l<=mid) modify2(u<<1,l,r);	if(r>mid) modify2(u<<1|1,l,r);		pushup(u); }

5.查询区间和

LL query(int u,int l,int r){
   	if(tr[u].l>=l&&tr[u].r<=r)		return tr[u].sum;			int mid=tr[u].l+tr[u].r>>1;	pushdown(u);	LL ans=0;	if(l<=mid) ans+=query(u<<1,l,r);	if(r>mid) ans+=query(u<<1|1,l,r);	pushup(u);		return ans; 	}

全部代码:

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105569282 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！