非递归线段树
迟延列车
離れ離れの街を将四散分离的街道
繋ぐ列車は行ってしまったね连接起来的列车开走了呢
失くした言葉を知らないなら如果不知道那些失去了的言语
ポケットで握りしめて就在口袋里握紧双手吧
あがいた息を捨てて舍弃拼命挣扎的呼吸
延びる今日は眠って誤魔化せ延误的今天就这样睡过去吧
失くした言葉を知らないなら如果不知道那些失去了的言语
各駅停車に乗り込んで就乘坐上每站停靠的列车吧
夕方と退屈のお誘いを断って拒绝黄昏与无聊的邀请
一人きり 路地裏は決して急がないで独自一人 小巷中绝不可急行
ほら 横断歩道も待ってくれと言ってる看啊 人行横道也在让你等等
見張る街角があなたを引き留めてく街角也在监视着把你留了下来
離れ離れの街を将四散分离的街道
繋ぐ列車は行ってしまったね连接起来的列车开走了呢
失くした言葉を知らないなら如果不知道那些失去了的言语
ポケットで握りしめて就在口袋里握紧双手吧
あがいた夢を捨てて舍弃拼命挣扎的梦想
揺れる今日は眠って誤魔化せ动摇的今天就这样睡过去吧
失くした言葉を知らないなら如果不知道那些失去了的言语
各駅停車に乗り込んで就乘坐上每站停靠的列车吧
--間奏----间奏--
夕方の駅のホームはひどく混み合って黄昏的车站特别特别拥挤
ひとり占めできるまで休憩して欲しくて在能独占这里之前真想好好休息
また 集団下校が又是 放学的时候啊
あなたを急かしている你的动作急切起来
ほら 自動改札は待ってくれと言ってる看啊 自动检票机也在让你等等
塞がる両手があなたを引き留めてく堵塞住的双手把你留了下来
あがいた夢を捨てて舍弃拼命挣扎的梦想
揺れる今日は眠って誤魔化せ动摇的今天就这样睡过去吧
失くした言葉を知らないなら如果不知道那些失去了的言语
各駅停車に乗り込んで就乘坐上每站停靠的列车吧
--間奏----间奏--
離れた街と街を繋ぐ列車が将四散分离的街道连接起来的列车
呼んだ風に飛ばされないでいてくれ不要被呼唤而至的风儿吹跑了啊
失くした言葉はそのままでいいよ那些失去了的言语就这样也没关系
揺れる列車に身を任せて欲しいから我现在只想委身于这摇晃的列车
離れ離れの街を将分离四散的街道
離れ離れの街を将分离四散的街道
繋ぐ列車は行ってしまったね连接起来的列车开走了呢
失くした言葉を知らないなら如果不知道那些失去了的言语
ポケットで握りしめて就在口袋里握紧双手吧
あがいた息を捨てて舍弃拼命挣扎的呼吸
延びる今日は眠って誤魔化せ延误的今天就这样睡过去吧
失くした言葉を知らないなら如果不知道那些失去了的言语
各駅停車で旅をして乘上每站停靠的列车踏上旅途吧
ツイッターランド（twitter land）
誰でも刺す切らす下す裁かれざる極悪と全能の神が能刺穿切开贬低制裁任何人的极恶而全能的神明大人
バレてるカス潰す碾碎了爬出的渣滓
うだつ上げたら去るぞんざいな洗脳と愛登上高地就甩手离开漫不经心的洗脑与爱
誰でも待つ焦らす等著随便谁来关心
知らず知らず迫る限界と膨大な不愿想不愿看膨胀到拥挤的极限
誰か戯言だって勘ぐってこの呼吸を褒めて玩笑也好猜疑也好请夸夸我呼吸着的事实吧
単細胞 多剤 圏外 放つ言葉は問題外单细胞 过服 圈外 评论内容在论题外
解剖したら免罪 できることなくローテーション解剖完发现无罪 无能为力所以只好按个转发补救
癌細胞 幼い 論外癌细胞 年轻 个例
未だに殺され足んないな看来全网抹杀力度不够啊
断罪されることなく夢に芽が出る没能被定罪的事实在梦中长出新芽
単細胞 多剤 圏外 放つ言葉は問題外单细胞 过服 圈外 评论内容在论题外
解剖したら免罪 できることなくローテーション解剖完发现无罪 无能为力所以只好按个转发补救
癌細胞 幼い 論外癌细胞 年轻 个例
未だに殺され足んないな看来全网抹杀力度不够啊
断罪されることなくまた息をして没能被定罪的事实让呼吸得以延续
あぁ誰でも刺す切らす下す裁かれざる極悪な神が啊啊能刺穿切开贬低制裁所有人的极恶的神明大人
バレてるカス潰す碾碎了爬出的渣滓
うだつ上げたら去るぞんざいな愛登上高地就甩手离开漫不经心的爱
誰でも待つ焦らす等著随便谁来关心
知らず知らず迫る限界な不愿想不愿看拥挤的极限
誰か戯言だって勘ぐってこの呼吸を褒めて玩笑也好猜疑也好请夸夸我呼吸着的事实吧
誰でも刺す切らす下す裁かれざる極悪と全能の神が能刺穿切开贬低制裁所有人的极恶而全能的神明大人
バレてるカス潰す碾碎了爬出的渣滓
うだつ上げたら去るぞんざいな洗脳と愛登上高地就甩手离开漫不经心的洗脑与爱
誰でも待つ焦らす等著随便谁来关心
知らず知らず迫る限界と膨大な不愿想不愿看膨胀到拥挤的极限
誰か戯言だって勘ぐってこの呼吸を褒めて玩笑也好猜疑也好请夸夸我呼吸着的事实吧
我挺喜欢 STEAKA 的，很冰。这个是第一首听的，但我当时还不知道这是啥。
冰指冰块，表达的是一种清凉轻快的感觉。但他的歌说很冰也没啥问题，这个冰不是冰块。
默认大家都会 zkw。
我们发现 zkw 必须开 4 倍空间太不牛了，普通线段树都能轻松只开 2 倍空间。并且还不能写成多叉。
我们学习 U 选，给一篇比较新的 blog。
确实是只开了 2 倍空间，但是我们发现在 pushup 的时候还需要专门记录一个标记表示这个点是否被修改，我们 zkw 不是这样的！我不接受！
问题非常简单，因为我们是左闭右开的，左闭的部分没法直接遍历到需要 pushup 的点。我们期望把它改成左开右开的，这样就和 zkw 一样写了。
但是如果我们直接将序列长度变为 \(n + 1\)，其总长变成了 \(2n + 1\)，并且需要在一些奇奇怪怪的地方平移下标，不太好写。
但是我们发现其实我们并不需要保留 \(n\) 个点作为非叶子点，我们只保留 \(n - 1\) 个也是对的，我们发现其会在那个空点后面建两个叶子，但是空点不会被修改，你把它当成一个新的树也毫无问题。
代码非常好写，给个线段树 1 的代码：
Code
/*
g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -Wshadow && ulimit -v 128000 && time ./%< && size %<
g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -Wshadow -fsanitize=address,undefined -g && ./%<
echo && cat out.out && echo
ulimit -v 128000; f='file'; for i in {1..3}; do cp $f$i'.in' in.in && cp $f$i'.ans' ans.ans && ./%< && diff -Z -q out.out ans.ans && echo $i; done
while python3 rnd.py > in.in && ./std && ./%< && diff -Z -q out.out ans.ans && let ++i; do echo $i; done
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
template<class T> inline void Cmin(T &a, T b){ if(a > b) a = b; }
template<class T> inline void Cmax(T &a, T b){ if(a < b) a = b; }
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in.in", "r", stdin), *OutFile = freopen("out.out", "w", stdout);
#endifconst int N = 1e5 + 3;
int n, m; llt _a[N];class Seg{
#define lson (t << 1)
#define rson (t << 1 | 1)
private:llt sm[N << 1], tg[N << 1];void upd(int t){ sm[t] = sm[lson] + sm[rson]; }void dwn(int l, int t){ if(llt x = tg[t]) tg[t] = 0, tg[lson] += x, tg[rson] += x, l >>= 1, sm[lson] += x * l, sm[rson] += x * l; }void Dwn(int t){ for(int i = __lg(n); i; --i) if(t >> i) dwn(1 << i, t >> i); }
public:void Bld(){for(int i = 1; i <= n; ++i) sm[i + n] = _a[i];for(int i = n - 1; i; --i) upd(i);}void Add(int l, int r, llt v){Dwn(l += n - 1), Dwn(r += n + 1);for(int ln = 1; l ^ r ^ 1; ln <<= 1){if(~l & 1) tg[l ^ 1] += v, sm[l ^ 1] += ln * v;if(r & 1) tg[r ^ 1] += v, sm[r ^ 1] += ln * v;upd(l >>= 1), upd(r >>= 1);}while(l >>= 1) upd(l);}llt Sum(int l, int r){Dwn(l += n - 1), Dwn(r += n + 1); llt s = 0;for(; l ^ r ^ 1; l >>= 1, r >>= 1){if(~l & 1) s += sm[l ^ 1];if(r & 1) s += sm[r ^ 1];}return s;}
#undef lson
#undef rson
} seg;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; ++i) cin >> _a[i];seg.Bld();for(int i = 1; i <= m; ++i){int op; cin >> op;if(op == 1){int l, r; llt k; cin >> l >> r >> k;seg.Add(l, r, k);}else{int l, r; cin >> l >> r;cout << seg.Sum(l, r) << endl;}}
}
P
我擦我孤独摇滚 & K-ON 图怎么推完了，得补充一点了。