题目背景

辰辰和小北刚刚学习了线段树，他们感觉很有收获。有一天小北问辰辰线段树空间复杂度，辰辰当然一口说出是 $O(n)$，小北又问具体有多少，辰辰说不出来了$......$

题目描述

有一个 $n$ 个元素的序列，问如果用它构造一棵线段树，有多少个节点。

输入输出

输入

一个正整数，表示 $n$。

输出

一个正整数，表示答案。

样例

27

53

数据范围

$n<10^{12}$

如果你不会线段树，那你可以看一下这道题：

和 $AC$ 代码：

#include<bits/stdc++.h>

#define int long long
#define ls(x) ((x)<<1)     //左节点 
#define rs(x) ((x)<<1|1)   //右节点 
#define fa(x) ((x)>>1)     //父节点 

using namespace std;

const int N = 100005;

struct node {
	int l, r, sum, add_tag, mul_tag;  //分别是[l,r]左闭右闭区间，区间和，加法懒标记和乘法懒标记（即 lazy_tag） 
};

node t[4 * N];              //线段树不开四倍空间见祖宗 
int a[N], n, q, m;

inline void push_up (int p) {    //上传数值 
	t[p].sum = (t[ls(p)].sum + t[rs(p)].sum) % m;
	return;
}

inline void build (int l, int r, int p) {    //建树 
	t[p].l = l;
	t[p].r = r;
	t[p].mul_tag = 1;
	if (l == r) {
		t[p].sum = a[l] % m;
		return;
	}
	int mid = l + r >> 1;
	build (l, mid, ls(p));
	build (mid + 1, r, rs(p));
	push_up(p);
	return;
}

inline void lazy_tag (int p, int mul, int add) {     //打懒标记 
	t[p].sum = t[p].sum * mul % m;         //先乘 
	t[p].mul_tag = t[p].mul_tag * mul % m;
	t[p].add_tag = t[p].add_tag * mul % m;
	
	t[p].sum = (t[p].sum + add * (t[p].r - t[p].l + 1) % m) % m;    //再加 
	t[p].add_tag = (t[p].add_tag + add) % m;
	return;
}

inline void push_down (int p) {            //下传懒标记 
	lazy_tag (ls(p), t[p].mul_tag, t[p].add_tag);    //给左节点打上懒标记 
	lazy_tag (rs(p), t[p].mul_tag, t[p].add_tag);    //给右节点打上懒标记 
	t[p].add_tag = 0;          //清空加法懒标记 
	t[p].mul_tag = 1;          //清空乘法懒标记 
	return;
}

inline void update (int l, int r, int p, int mul, int add) {     //区间修改[l,r]，先乘上mul，再加上add 
	if (l <= t[p].l && t[p].r <= r) {          //区间完全覆盖 
		lazy_tag (p, mul, add);                //打上懒标记 
		return;
	}
	push_down (p);             //先下传懒标记，让下一层有正确答案 
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) update (l, r, ls(p), mul, add);      //修改左子树 
	if (r > mid) update (l, r, rs(p), mul, add);       //修改右子树 
	push_up (p);               //修改完后上传数值 
	return;
}

inline int query (int l, int r, int p) {     //区间查询[l,r] 
	if (l <= t[p].l && t[p].r <= r) {     //区间完全覆盖 
		return t[p].sum;             
	}
	push_down (p);              //查询也要先下传懒标记 
	int mid = t[p].l + t[p].r >> 1, sum = 0;
	if (l <= mid) sum = (sum + query (l, r, ls(p))) % m;       //查询左子树 
	if (r > mid) sum = (sum + query (l, r, rs(p))) % m;        //查询右子树 
	return sum;
}

signed main() {
	scanf("%lld%lld%lld", &n, &q, &m);
	
	for (register int i = 1; i <= n; ++ i) scanf("%lld", a + i);
	
	build (1, n, 1);                   //建树 
	
	while (q -- ) {
		int op;

		scanf("%lld", &op);

		if (op == 1) {
			int x, y, k;

			scanf("%lld%lld%lld", &x, &y, &k);

			update (x, y, 1, k, 0);                          //加 k 即先乘 1，再加 k 
		}else if (op == 2) {
			int x, y, k;

			scanf("%lld%lld%lld", &x, &y, &k);

			update (x, y, 1, 1, k);                          //乘 k 即先乘 k, 再加 0 
		}else{
			int x, y;

			scanf("%lld%lld", &x, &y);

			printf("%lld\n", query (x, y, 1));
		}
	}
	return 0;
}

大家可以直接复制我的代码 $AC$ 这道题，我不举报，只要打我的比赛就可以。