8.16 pomorodo to-do list
小本本需记录：to_do list 今日明日的任务，完成情况，积分情况
7:00--7:30 回顾昨日笔记与算法，确立今日学习目标 && 打鸡血（回顾人生，展望人生）
7:40--8:20 查找今日所需资料，制定目标，设置完每一个*安排的番茄钟
（有想要做的顺延到明天的to_do list）
8:30--9:00 树状数组
https://www.cnblogs.com/RabbitHu/p/BIT.html#4321088
9:00--9:30
tarjan系列算法代码小结
https://www.cnblogs.com/zwfymqz/p/8480778.html
10:10--10:50 差分约束
https://www.cnblogs.com/zwfymqz/p/8515897.html
11:00-- 11:40 夜深人静写算法
https://blog.csdn.net/WhereIsHeroFrom/article/details/78969718
11:40--12:00
折线分割
https://blog.csdn.net/qq_34131212/article/details/78043679
中午：
- 看lyd tarjan
- 看主席树
14:30--15:10 模板4个
树状数组1.2.3.- 线段树
1.2. - 主席树（回寝室学习）
15:20--15:50 线段树 (咕咕咕)
https://www.cnblogs.com/cjyyb/p/8567674.html
15:50--16:20 线段树
https://www.cnblogs.com/cjyyb/p/8567674.html
16:20--17:00 2-SAT问题
https://www.cnblogs.com/zwfymqz/p/8485365.html
17:00--18:00 莫队
https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html
18:00--18:20 matrix
https://www.guokr.com/i/0376718656/articles/
18:30--19:00 bilibili Friends
晚上
19:00--20:00 两道noip原题（一道数据结构一道搜索）
https://www.cnblogs.com/fengxunling/p/9565047.html
20:00--20:30 拓展阅读
https://www.cnblogs.com/fengxunling/p/10363327.html
20:30--21:00 写博客 && 清理所学。【明得失，清理不足，不能盲目刷题】
21:00--21:30 遗忘曲线
21:30--22:10 刷今日遗留问题
回寝后，变身文艺青年，一首古诗词。
最小瓶颈路
https://www.cnblogs.com/zwfymqz/p/9717129.html
【1】 C +1 二维的树状数组未搞定
【2】 C +1 点双，边双未搞完
【3】 B +3 P2194 HXY烧情侣
P3916 【图的遍历】
可以采用反向建边,从最大的点开始dfs
我们考虑每次从所剩点中最大的一个点出发，我们暂且称它为i，而凡是i这个点所能到达的点，可以到达的点最大都是i。
在遍历的时候按n——>1的顺序
因为是从大到小遍历，故每个点第一次被碰到的i一定是这个点最大可到达的点
用树状数组区间修改区间查询：
/*
translation:
solution:
trigger:
note:
*
date:
2019.08.16
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,x) for(int i=head[x];i;i=e[i].next)
#define N 500010
int n,m;
int tr1[N],tr2[N];
void add(int x,int k){
for(int i=x;i<=n;i+=(-i)&i)
tr1[i]+=k,tr2[i]+=k*x;
}
int query(int x){
int res=0;
for(int i=x;i;i-=(-i)&i)
res+=(x+1)*tr1[i]-tr2[i];
return res;
}
signed main(){
rd(n),rd(m);
int last=0,now;
rep(i,1,n){
rd(now);
add(i,now-last);//////////////////////////////
last=now;
}
rep(i,1,m){
int op,x,y,k;
rd(op);
if(op==1){
rd(x),rd(y),rd(k);
add(x,k),add(y+1,-k);
}
else if(op==2){
rd(x),rd(y);
printf("%lld
",query(y)-query(x-1));
}
}
}