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

P1438 无聊的数列 题解

时间:2024-01-29 16:23:11浏览次数:23  
标签:rt 数列 rs int 题解 tr ls op P1438

背景

看到题解都是差分,竟然还有建两颗线段树和二阶差分的大佬。

我感到不理解,很不理解。

题目正解

本题正解很明显就是:线段树

是的,你没有看错,就只有线段树。

很显然我们直接按照线段树板题写就可以了,维护题目需要维护的,注意到只有单点查询,所以我们根本不需要维护区间和,对于区间来讲,我们只用维护修改操作,修改操作只需要 \(k,d\) (首项和公差)。

考虑该操作如何向下传递(pushdown):

  1. 对于左区间来讲,\(k,d\) 没有改变,直接赋值。
  2. 对于右区间来讲,只有 \(k_{right}=k_{father}+len*d\),其中 \(len\) 是左区间长度。

此外我们发现:对于同一段区间,修改操作是可以叠加的。

好的,我们做完了,甚至不需要 pushup 操作。

是的,就是这么简单,当区间变成一个点时,我们发现对于这个点的修改就是加上 \(k\)。

AC 代码:

#include<bits/stdc++.h>
using namespace std;
#define N 500000
#define ls rt<<1
#define rs rt<<1|1
int n,m,a[N];

struct tree{
	long long l,r,w,op,k,d;
}tr[N];

void build(int rt,int l,int r){
	tr[rt]={l,r,0,0,0,0};
	if(l==r){
		tr[rt].w=a[l];return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r); 
}

void pushdown(int rt){
	if(tr[rt].op){
		tr[ls].k+=tr[rt].k;
		tr[ls].d+=tr[rt].d;
		tr[ls].op=1;
		tr[rs].k+=tr[rt].k+(tr[rs].l-tr[ls].l)*tr[rt].d;
		tr[rs].d+=tr[rt].d;
		tr[rs].op=1;
	}
	tr[rt].op=0;
	tr[rt].d=tr[rt].k=0;
}

void update(int rt,int cl,int cr,int k,int d){
	int l=tr[rt].l,r=tr[rt].r;
	if(cl<=l&&r<=cr){
		tr[rt].op=1;
		tr[rt].k+=k+(l-cl)*d;
		tr[rt].d+=d;
		return ;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(cl<=mid) update(ls,cl,cr,k,d);
	if(cr>mid) update(rs,cl,cr,k,d);
}

long long query(int rt,int p){
	int l=tr[rt].l,r=tr[rt].r;
//	printf("|%d %d %d %d %d\n",l,r,tr[rt].d,tr[rt].k,tr[rt].w);
	if(l==r){
		tr[rt].w+=tr[rt].k;
		tr[rt].k=0;tr[rt].d=0;
		return tr[rt].w;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(p<=mid) return query(ls,p);
	else return query(rs,p); 
} 

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	while(m--){
		int t,l,r,k,d,p;
		scanf("%d",&t);
		if(t==1){
			scanf("%d%d%d%d",&l,&r,&k,&d);
			update(1,l,r,k,d);
		}else{
			scanf("%d",&p);
			printf("%lld\n",query(1,p));
		}
	}
	return 0;
}

标签:rt,数列,rs,int,题解,tr,ls,op,P1438
From: https://www.cnblogs.com/alloverzyt/p/17994776

相关文章

  • 洛谷P10114题解
    题意简述给定一个长度为\(n\)的序列,求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}{((d_i\oplusd_j)+(d_i\otimesd_j))}\)。思维路径观察数据范围可以发现\(n\le2\times10^6\)而\(\sum\limitsd_i\le5\times10^7\),这说明\(d\)数组中的重复值较多,直接枚举数值可......
  • 洛谷题解-[ABC325E] Our clients, please wait a moment
    https://www.luogu.com.cn/problem/AT_abc325_e题目描述ある国には都市がNNN個あります。あなたは、都市111にある営業所から000個以上の都市を経由して都市NNNにある訪問先へ移動しようとしています。移動手段は社用車と電車の222種類があります。都市......
  • 洛谷P10115题解
    题意简述给定一个括号序列,求整个序列的美丽值最大。思维路径见到序列和权值,很容易想到需要用DP。我们定义\(f[i][j]\)表示第\(1\)到\(i\)个括号产生的美丽值最大值,其中\(j=0\)表示第\(i\)个括号本身不参与美丽值贡献,\(j=1\)表示第\(i\)个括号本身参与美丽值贡献......
  • B3929 [GESP202312 五级] 小杨的幸运数 题解
    因为一些众所周知的原因,不放代码。分享一种考场思路:\(a\le10^7\),顺序查找肯定会废,所以可以用一种类似埃氏筛的方法将所有满足条件的数标记一下,并将其加入一个答案数组\(a\)当中。然后每次查询只需要用lower_bound函数二分查找一下,假如找到了第\(i\)个:\(a_i=x\),直接......
  • P7324 [WC2021] 表达式求值 题解
    题目链接点击打开链接题目解法不错的题首先建出表达式树说实话我一开始不知道怎么建,但看了代码之后就懂了这里简单说一下:假如要对区间\([l,r]\)建树,分\(E_r=)\)和\(E_r\neq)\)的情况\(E_r=)\),找到匹配的左括号,递归下去建树\(E_r\neq)\),\(r\)可以作为单独的一个......
  • ABC338D 题解
    赛时怎么连这题都不会。再不练练思维真的就连普及题都不会做了啊。Solution题目来源:ABC338D(inAtcoder|in洛谷)。不妨先考虑应该断掉哪条边。首先我们发现,仅断掉一条边并不会让两个结点不可达,只会让我们从一个结点绕更远的路到达目标结点。如果我们要从结点\(u\)前往结点......
  • CF1070H 题解
    思路我们第一眼看题就发现每个字符串的长度在只有\(8\)。我们需要判断的是某个字符串是不是前面字符串的子串,因为长度太小,所以可以把字符串的每一个子串放到map里,再用一个map判断一个子串是否在当前字符串出现过,出现过就不能重复记。最后在用一个map记录一下每个子串对应......
  • CF1472F 题解
    前言只要题目给了图,你就要画图。思路首先,我们要明确一点:一个矩形,如果里面不存在任何被覆盖的方格,那么这个矩形是绝对可以被覆盖的。如果现在有一个点被覆盖了。那么必定要有一个长方形从这个点下方往后。然后继续在上方接长方形继续往后。直到出现了一个新节点被覆盖。......
  • 第一周题解
    第一周周报这一周是寒假训练的第一周,训练内容主要就是做牛客上的题单还有比赛,牛客上的题单还是比较痛苦的,因为牛客压根看不了测试用例,导致我事后想知道错的例子是什么都看不了。做第一题第二题还有倒数第三题有一两个例子一直都过不去。检查了很久的代码,一直是差一两个例子,就老是......
  • P4145 上帝造题的七分钟 2 / 花神游历各国 题解
    题目链接:上帝造题的七分钟2/花神游历各国差不多的题:[YnoiEasyRound2023]TEST_69注意到对某个点来说暴力单点即为反复的:\(x=\sqrt{x}\),最终为\(1\),根据\(master\)主定理可知,跟\(veb\)树分析差不多的,复杂度为:\(O(\log{\log{V_{max}}})\)。不懂的可以去学学这篇文章。那......