参考博客https://blog.csdn.net/neighthorn/article/details/52115830
这里只讨论区间处理+lazy
acm比赛考察不会出裸的模板，所以必须深刻理解线段树原理，各函数的目的。
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <queue>
#define MAXN 100010
#define inf 0x3f3f3f3f using namespace std; struct node{ int l,r;//区间[l,r] int add;//区间的延时标记 int sum;//区间和 int mx; //区间最大值 int mn; //区间最小值
}tree[MAXN<<2];//一定要开到4倍多的空间 void pushup(int index){ tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum; tree[index].mx = max(tree[index<<1].mx,tree[index<<1|1].mx); tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}
void pushdown(int index){ //说明该区间之前更新过 //要想更新该区间下面的子区间，就要把上次更新该区间的值向下更新 if(tree[index].add){ //替换原来的值 /* tree[index<<1].sum = (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add; tree[index<<1|1].sum = (tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add; tree[index<<1].mx = tree[index].add; tree[index<<1|1].mx = tree[index].add; tree[index<<1].mn = tree[index].add; tree[index<<1|1].mn = tree[index].add; tree[index<<1].add = tree[index].add; tree[index<<1|1].add = tree[index].add; tree[index].add = 0;*/ //在原来的值的基础上加上val tree[index<<1].sum += (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add; tree[index<<1|1].sum +=(tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add; tree[index<<1].mx += tree[index].add; tree[index<<1|1].mx += tree[index].add; tree[index<<1].mn += tree[index].add; tree[index<<1|1].mn += tree[index].add; tree[index<<1].add += tree[index].add; tree[index<<1|1].add += tree[index].add; tree[index].add = 0; }
}
void build(int l,int r,int index){ tree[index].l = l; tree[index].r = r; tree[index].add = 0;//刚开始一定要清0 if(l == r){ scanf("%d",&tree[index].sum); tree[index].mn = tree[index].mx = tree[index].sum; return ; } int mid = (l+r)>>1; build(l,mid,index<<1); build(mid+1,r,index<<1|1); pushup(index);
}
void updata(int l,int r,int index,int val){ if(l <= tree[index].l && r >= tree[index].r){ /*把原来的值替换成val,因为该区间有tree[index].r-tree[index].l+1 个数，所以区间和 以及 最值为： */ /*tree[index].sum = (tree[index].r-tree[index].l+1)*val; tree[index].mn = val; tree[index].mx = val; tree[index].add = val;//延时标记*/ //在原来的值的基础上加上val,因为该区间有tree[index].r-tree[index].l+1 //个数，所以区间和 以及 最值为： tree[index].sum += (tree[index].r-tree[index].l+1)*val; tree[index].mn += val; tree[index].mx += val; tree[index].add += val;//延时标记 return ; } pushdown(index); int mid = (tree[index].l+tree[index].r)>>1; if(l <= mid){ updata(l,r,index<<1,val); } if(r > mid){ updata(l,r,index<<1|1,val); } pushup(index);
}
int query(int l,int r,int index){ if(l <= tree[index].l && r >= tree[index].r){ //return tree[index].sum; return tree[index].mx; //return tree[index].mn; } pushdown(index); int mid = (tree[index].l+tree[index].r)>>1; int ans = 0; int Max = 0; int Min = inf; if(l <= mid){ ans += query(l,r,index<<1); Max = max(query(l,r,index<<1),Max); Min = min(query(l,r,index<<1),Min); } if(r > mid){ ans += query(l,r,index<<1|1); Max = max(query(l,r,index<<1|1),Max); Min = min(query(l,r,index<<1|1),Min); } //return ans; return Max; //return Min;
}
int main()
{ int n,m,q,x,y,z; while(~scanf("%d%d",&n,&m)){ build(1,n,1); while(m--){ scanf("%d",&q); if(q == 1){ cout<<"查询:(x,y)"<<endl; scanf("%d %d",&x,&y); cout<<query(x,y,1)<<endl; } else{ cout<<"更新(x,y)为z："<<endl; scanf("%d %d %d",&x,&y,&z); updata(x,y,1,z); for(int i = 1; i <= n; ++i){ printf("a[%d] = %d\n",i,query(i,i,1)); } } } } return 0;
}
拿到问题，简单数学化题目要求 ， 比如说这题
poj 3667
题意：
两种操作 1）订房间 给定长度x ，求连续长度>=x 的区间起始位置， 尽量靠左 ， 查询到结果后把该段长度标记为不可用
2) 退房间 给定xy，把xy区间标记为可用
思路：
操作1 等价于两部， 1 查询到可用区间的起始位置， 2 更新该段区间为不可用
操作2 等价于更新该段区间为可用
分析 ：
数据结构
我们要知道线段树数据结构需要哪些内容， l,r,lazy (必备) 、v(区间[l,r]内连续最大区间，用于查询时判断是否进入这个区间)、llen,rlen(区间[l,r]的前缀， 后缀长度。 举例分析 ，假设n为6，所需x为4 . 则一开始进入[1,6]。分成两个区间[1,3][4,6[ 。这个时候左子树的后缀 + 右子树的前缀可以符合条件，我们就要把答左子树的后缀起点就是我们要的案)
struct node
{int l,r,v,lazy,llen,rlen;void changeLen(){llen = rlen = v = lazy*(r-l+1);}
}node[N<<2]; // 线段树的空间大概是数组空间的4倍；
changelen()的作用，lazy标记了区间[l,r]的可用性（整体），那么[l,r]内的v,llen,rlen 就等于 区间长度*lazy。
通过lazy的改变，修改最长连续区间、左后缀、右前缀的值
build 建树
定位到叶子节点后，标记lazy的1(通过changelen函数，修改v,llen, rlen 为 1) 。
存储信息：node[numb].l = l , node[numb].r = r（必须的，线段树的基本）
void build(int l,int r,int numb) // 线段树的建立；
{node[numb].lazy=1;node[numb].l = l;node[numb].r = r;node[numb].changeLen();if(l==r) return;int mid=(l+r)>>1;build(l,mid,numb<<1);build(mid+1,r,numb<<1|1);
}
change 更新操作
更新操作模板的架构基本是这样的
if (区间重合，即定位到目标区间)
{lazy标记 // 节约时间，不向下走return;
}// 没有定位到目标区间，那么向下一层走if(node[numb].lazy != -1) // 向下走之前，倘若节点上有lazy标志，那么先更新子树信息，才能向下走pushDown(numb)
mid = (node[numb].l + node[numb].r) / 2;
if(l>mid) // 目标区间 在本节点的右子树上更新右边
else if(r<=mid)更新左边
else{ // 左右各占一部分，分别更新更新左更新右
}
pushUp(numb); // 更新完左右子树，那么本节点的信息也要修改
本题中，我们要明白更新时，那些参数是需要改变的，
1）我们定位到目标区间，更新其lazy，马上能得到该区间上的 v=llen = rlen因此changelen()
2）PushDown ，向下传递，那么子节点上的 lazy 就该被更新为 父节点上的lazy (这里注意，本题的lazy取值只有1可用，0不可用，-1没有lazy ， 其他题有的lazy暂存的是操作次数那么应该累加，比如对区间做加法，那么向下传递应该是node[rt<<1].lazy+=node[rt].lazy)。并且同时更新子节点上的v,llen,rlen
3)PushUp ， 用左右节点的信息更新父节点。逐个分析父节点的各个变量 ，
l r lazy :跟子树无关 。
v: 修改为 左节点的v 和 右节点的v 以及 左节点后缀 + 右节点前缀 三者的最大值
llen: 左节点的前缀， 当左节点区间都是可用时，那么还需加上右节点的前缀 (两个区间能连起来)
rlen: 右节点的后缀， 当右节点区间都是可用时，还需加上左节点的后缀
void PushDown(int numb) // 向下往左右儿子方向更新数据；
{// 为了父节点的lazy 对左右子树的影响，要思考lazy会影响左右子树的什么// 本题，lazy肯定要向下传递，子树再根据lazy ，修改自身变量//(标记为0 相当于该区间完全被占用，也就是llen rlen v = 0 )// 最后 把父节点的 lazy 标记取消 变成-1node[numb<<1].lazy=node[numb].lazy;node[numb<<1|1].lazy=node[numb].lazy;node[numb<<1].changeLen();node[numb<<1|1].changeLen();node[numb].lazy=-1; // 更新完了要清零；
}
void PushUp(int numb)
{// 假设父节点是A ，左右子树分别是BC// pushUp时 关心BC，对A的影响// 1） A的连续区间最大长 v =max( B.v,C.v ,B.rlen+C.llen)// 2) A的llen = B.llen 。 且当 B整只为1 A.len += C.llen// 3) A的rlen = C.rlen 且当 C整只为1 A.rlen += B.rlenint tmp = max(node[numb<<1].v, node[numb<<1|1].v);node[numb].v = max(tmp, node[numb<<1].rlen + node[numb<<1|1].llen);// 更新根节点的 区间内最长区间值node[numb].llen = node[numb<<1].llen;node[numb].rlen = node[numb<<1|1].rlen;if(node[numb<<1].v == node[numb<<1].r-node[numb<<1].l + 1)node[numb].llen += node[numb<<1|1].llen;if(node[numb<<1|1].v == node[numb<<1|1].r - node[numb<<1|1].l + 1)node[numb].rlen += node[numb<<1].rlen ;}void change(int l,int r,int numb,int val) // 插入更新数据；
{if(node[numb].l==l&&node[numb].r==r) // 如果区间完全重合，则不需要再往下更新了，先保存起来，可以节约很多的时间（lazy思想）{node[numb].lazy=val;node[numb].changeLen();return;}if(node[numb].lazy!=-1) PushDown(numb); // 因为没有找到完全重合的区间，所以要先更新下一层区间；int mid=(node[numb].r+node[numb].l)>>1;if(l>mid) change(l,r,numb<<1|1,val);else if(r<=mid) change(l,r,numb<<1,val);else{change(l,mid,numb<<1,val);change(mid+1,r,numb<<1|1,val);}PushUp(numb); // 最后还得往上返回，更新父节点区间；
}
query查询
if 查询到目标区间返回节点上的信息 // 有时候是最大值，有时候是和retrurn;if lazy pushDown() // 向下找之前，有lazy标记必须先向下更新mid = (node[numb].l + node[numb].r) / 2;if(l>mid) // 进入右子树return 查询右子树
else if(r<=mid) //进入左子树return 查询左子树
else
{// 左右子树都占一部分// 返回值 需要就题论题，int tmp1 = query(l,mid,numb<<1);int tmp2 = query(mid+1,r,numb<<1|1);// 求最大值 return max(tmp1,tmp2);// 求和 return tmp1+tmp2;// 不过本题有不一样的需求
}
分析本题， 需求是找到 满足区间的起始位置， 而且尽可能靠左。 那么判断条件就应是 v ,llen ,rlen
1、如果左儿子的v>=x那么就返回query（左儿子）
2、如果左儿子的后缀+右儿子的前缀>=x，直接返回左儿子的后缀开始的下标
3、若果右儿子的v>=x那么就返回query（右儿子）
4、那就只能返回0了（忧桑~~>_<)
由此可见不同题目要求，判断条件，返回条件也要顺应着修改
int query(int l,int r,int numb, int len)
{if(node[numb].l==node[numb].r&&len == 1){return node[numb].l;}if(node[numb].lazy!=-1) PushDown(numb); int mid=(node[numb].r+node[numb].l)>>1;// 若左边区间大于等于val 则去左边查// 若左边的后缀 + 右边的前缀 >= val ，则返回左边后缀的起点// 若右边区间大于等于val ，则去右边if(node[numb<<1].v >= len)return query(l,mid,numb<<1,len);if(node[numb<<1].rlen + node[numb<<1|1].llen >= len)return node[numb<<1].r - node[numb<<1].rlen + 1;if(node[numb<<1|1].v >= len)return query(mid+1,r,numb<<1|1, len);return 0;
}
完整代码
#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
int ans[N];
struct node
{int l,r,v,lazy,llen,rlen;void changeLen(){llen = rlen = v = lazy*(r-l+1);}
}node[N<<2]; // 线段树的空间大概是数组空间的4倍；void build(int l,int r,int numb) // 线段树的建立；
{node[numb].lazy=1;node[numb].l = l;node[numb].r = r;node[numb].changeLen();if(l==r) return;int mid=(l+r)>>1;build(l,mid,numb<<1);build(mid+1,r,numb<<1|1);
}
void PushUp(int numb)
{// 假设父节点是A ，左右子树分别是BC// pushUp时 关心BC，对A的影响// 1） A的连续区间最大长 v =max( B.v,C.v ,B.rlen+C.llen)// 2) A的llen = B.llen 。 且当 B整只为1 A.len += C.llen// 3) A的rlen = C.rlen 且当 C整只为1 A.rlen += B.rlenint tmp = max(node[numb<<1].v, node[numb<<1|1].v);node[numb].v = max(tmp, node[numb<<1].rlen + node[numb<<1|1].llen);// 更新根节点的 区间内最长区间值node[numb].llen = node[numb<<1].llen;node[numb].rlen = node[numb<<1|1].rlen;if(node[numb<<1].v == node[numb<<1].r-node[numb<<1].l + 1)node[numb].llen += node[numb<<1|1].llen;if(node[numb<<1|1].v == node[numb<<1|1].r - node[numb<<1|1].l + 1)node[numb].rlen += node[numb<<1].rlen ;}
void PushDown(int numb) // 向下往左右儿子方向更新数据；
{// 为了父节点的lazy 对左右子树的影响，要思考lazy会影响左右子树的什么// 本题，lazy肯定要向下传递，子树再根据lazy ，修改自身变量//(标记为0 相当于该区间完全被占用，也就是llen rlen v = 0 )// 最后 把父节点的 lazy 标记取消 变成-1node[numb<<1].lazy=node[numb].lazy;node[numb<<1|1].lazy=node[numb].lazy;node[numb<<1].changeLen();node[numb<<1|1].changeLen();node[numb].lazy=-1; // 更新完了要清零；
}void change(int l,int r,int numb,int val) // 插入更新数据；
{if(node[numb].l==l&&node[numb].r==r) // 如果区间完全重合，则不需要再往下更新了，先保存起来，可以节约很多的时间（lazy思想）{node[numb].lazy=val;node[numb].changeLen();return;}if(node[numb].lazy!=-1) PushDown(numb); // 因为没有找到完全重合的区间，所以要先更新下一层区间；int mid=(node[numb].r+node[numb].l)>>1;if(l>mid) change(l,r,numb<<1|1,val);else if(r<=mid) change(l,r,numb<<1,val);else{change(l,mid,numb<<1,val);change(mid+1,r,numb<<1|1,val);}PushUp(numb); // 最后还得往上返回，更新父节点区间；
}// 查询到 连续区间>=len的 返回左边第一个坐标
int query(int l,int r,int numb, int len)
{if(node[numb].l==node[numb].r&&len == 1){return node[numb].l;}if(node[numb].lazy!=-1) PushDown(numb); int mid=(node[numb].r+node[numb].l)>>1;// 若左边区间大于等于val 则去左边查// 若左边的后缀 + 右边的前缀 >= val ，则返回左边后缀的起点// 若右边区间大于等于val ，则去右边if(node[numb<<1].v >= len)return query(l,mid,numb<<1,len);if(node[numb<<1].rlen + node[numb<<1|1].llen >= len)return node[numb<<1].r - node[numb<<1].rlen + 1;if(node[numb<<1|1].v >= len)return query(mid+1,r,numb<<1|1, len);return 0;
}int main()
{int n,m;scanf("%d%d",&n,&m);build(1,n,1);while(m--){int x,y,z;scanf("%d",&z);if(z==1){scanf("%d",&x),cout<<(y=query(1,n,1,x))<<endl;if(y!=0)change(y,y+x-1,1,0);}elsescanf("%d%d",&x,&y),change(x,x+y-1,1,1);}return 0;
}
HDU 6315 Naive Operations
1、分析数据结构
1、lazy： 加1操作时，如果该节点以下的子节点+1 不会产生贡献， 那么本次操作寄存在该节点上，即lazy+1
2、num： 该节点管辖的区间下，还差多少能产生贡献度，如果能产生贡献度，那么必须更新到叶子节点上
3、v ： 贡献度
4、b： 分母b数组
2、更新操作
当查找到目标区间，对目标区间内的num--，
如果减完的num >0 ，那么本次操作寄存到lazy 。
当num ==0 ，则表明产生了贡献，那么此时需要更新到叶子节点
pushUp 保证了父节点的num、v 受到左右子节点影响，到底层更新节点，回溯回去后就更新。
void Insert(int l,int r,int numb) // 插入更新数据；
{if(node[numb].l==l&&node[numb].r==r) // 找到目标区间 ，那么区间上的 num--， 因为这段区间是被更新的{node[numb].num --;if(node[numb].num > 0){// 还产生价值node[numb].lazy ++ ;// 找到目标区间，而且未产生价值，那么这段区间以下的 加操作先存到lazy里。return ;}else{if(node[numb].l == node[numb].r) // 当num == 0 , 则必须要更新到叶子节点{node[numb].v ++;node[numb].num = node[numb].b;node[numb].lazy = 0;return;}}}if(node[numb].lazy)PushDown(numb);int mid=(node[numb].r+node[numb].l)>>1;if(l>mid)Insert(l,r,numb<<1|1);else if(r<=mid)Insert(l,r,numb<<1);else{Insert(l,mid,numb<<1);Insert(mid+1,r,numb<<1|1);}PushUp(numb);
}
完整代码
#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
int ans[N];
int b[N];struct node
{int l,r,v,lazy,b,num; // v: 值 ，b: 输入的b数组 num: 每个节点上 差多少能再得到一个满足的 最小值// lazy 标记为该节点以下 ，还得加多少次， 先寄存} node[N<<2]; // 线段树的空间大概是数组空间的4倍；void build(int l,int r,int numb) // 线段树的建立；
{node[numb].l=l;node[numb].r=r;node[numb].v=0;node[numb].lazy=0; // 用了lazy思想，提高了效率；if(l==r){node[numb].b = b[l];node[numb].num = b[l];//cout<<b[l]<<' ';return;}int mid=(l+r)>>1;build(l,mid,numb<<1);build(mid+1,r,numb<<1|1);node[numb].num = min(node[numb<<1].num, node[numb<<1|1].num);
}
void PushUp(int numb)
{node[numb].v= node[numb<<1].v + node[numb<<1|1].v;node[numb].num = min(node[numb<<1].num,node[numb<<1|1].num );
}
void PushDown(int numb) // 向下往左右儿子方向更新数据；
{node[numb<<1].lazy+=node[numb].lazy; // 寄存肯定是要 += node[numb<<1|1].lazy+=node[numb].lazy;node[numb<<1].num-=node[numb].lazy;node[numb<<1|1].num-=node[numb].lazy;node[numb].lazy=0; // 更新完了要清零；
}
void Insert(int l,int r,int numb) // 插入更新数据；
{if(node[numb].l==l&&node[numb].r==r) // 找到目标区间 ，那么区间上的 num--， 因为这段区间是被更新的{node[numb].num --;if(node[numb].num > 0){// 还产生价值node[numb].lazy ++ ;// 找到目标区间，而且未产生价值，那么这段区间以下的 加操作先存到lazy里。return ;}else{if(node[numb].l == node[numb].r) // 当num == 0 , 则必须要更新到叶子节点{node[numb].v ++;node[numb].num = node[numb].b;node[numb].lazy = 0;return;}}}if(node[numb].lazy)PushDown(numb);int mid=(node[numb].r+node[numb].l)>>1;if(l>mid)Insert(l,r,numb<<1|1);else if(r<=mid)Insert(l,r,numb<<1);else{Insert(l,mid,numb<<1);Insert(mid+1,r,numb<<1|1);}PushUp(numb);
}
int query(int l,int r,int numb)
{if(node[numb].l==l&&node[numb].r==r){return node[numb].v;}if(node[numb].lazy)PushDown(numb);int mid=(node[numb].r+node[numb].l)>>1;if(l>mid)return query(l,r,numb<<1|1);else if(r<=mid)return query(l,r,numb<<1);else{return query(l,mid,numb<<1) + query(mid+1,r,numb<<1|1) ;}
}
int main()
{char str[10];int x, y,n,m;while(~scanf("%d%d", &n, &m)){for(int i=1; i<=n; i++)scanf("%d",&b[i]);build(1, n, 1);for(int i = 0; i < m; i ++){scanf("%s%d%d", str, &x, &y);if(str[0] == 'a'){Insert(x, y, 1);}elseprintf("%d\n", query(x, y, 1));}}return 0;
}
/*
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<cstdlib>
#include<stdlib.h>
#include<queue>
#include<map>
#include<set>
#include<stack>
#define bug printf("*********\n");
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define in1(a) scanf("%d" ,&a);
#define in2(a, b) scanf("%d%d", &a, &b);
#define in3(a, b, c) scanf("%d%d%d", &a, &b, &c);
#define out1(a) printf("%d\n", a);
#define out2(a, b) printf("%d %d\n", a, b);
#define pb(G, b) G.push_back(b);
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const int mod = 998244353;
const LL INF = 1e9+7;
const int N = 1010;
const double pi = 3.1415926;int n, m, mi;struct node
{int l;int r;int num; //节点当前状态，为0时意味着达到整除状态int lazy; //懒惰标记int sum; //整除结果int b; //b数组初始值
}e[100010*4];void build(int l, int r, int k)
{e[k].l = l;e[k].r = r;e[k].sum = 0;e[k].lazy = 0;if(l == r) {scanf("%d", &e[k].b);e[k].sum = 0;e[k].num = e[k].b;return;}int mid = (l+r)/2;build(l, mid, 2*k);build(mid+1, r, 2*k+1);e[k].num = min(e[2*k].num, e[2*k+1].num); //维护区间最小值
}void push(int k)
{if(e[k].lazy) {e[2*k].num += e[k].lazy;e[2*k+1].num += e[k].lazy;e[2*k].lazy += e[k].lazy;e[2*k+1].lazy += e[k].lazy;e[k].lazy = 0;}
}void update(int l, int r, int k)
{if(e[k].l == l && e[k].r == r) {e[k].num --;if(e[k].num) {e[k].lazy --; //该区间没有可以整除的节点return;}else {if(e[k].l == e[k].r) { //找到达到整除状态的节点e[k].sum ++;e[k].num = e[k].b; //更新return;}}}push(k);int mid = (e[k].l+e[k].r)/2;if(r <= mid) update(l, r, 2*k);else if(l > mid) update(l, r, 2*k+1);else {update(l, mid, 2*k);update(mid+1, r, 2*k+1);}e[k].num = min(e[2*k].num, e[2*k+1].num); //维护区间最小值e[k].sum = e[2*k].sum + e[2*k+1].sum;
}int quary(int l, int r, int k)
{if(e[k].l == l && e[k].r == r) {return e[k].sum;}int mid = (e[k].l+e[k].r)/2;if(r <= mid) return quary(l, r, 2*k);else if(l > mid) return quary(l ,r, 2*k+1);else {return quary(l, mid, 2*k) + quary(mid+1, r, 2*k+1);}
}int main()
{char str[10];int x, y;while(~scanf("%d%d", &n, &m)) {build(1, n, 1);for(int i = 0; i < m; i ++) {scanf("%s%d%d", str, &x, &y);if(str[0] == 'a') {update(x, y, 1);}else printf("%d\n", quary(x, y, 1));}}return 0;
}
*/
手残居然求和、最大值写不出来，我恨！
#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
int ans[N];
struct node
{int l,r,v,lazy,sum,maxx;void changeLen(){sum += lazy*(r-l+1);maxx += lazy;}
} node[N<<2]; // 线段树的空间大概是数组空间的4倍；void build(int l,int r,int numb) // 线段树的建立；
{node[numb].lazy=0;node[numb].l = l;node[numb].r = r;node[numb].changeLen();if(l==r)return;int mid=(l+r)>>1;build(l,mid,numb<<1);build(mid+1,r,numb<<1|1);
}
void PushUp(int numb)
{node[numb].sum += node[numb<<1].sum + node[numb<<1|1].sum;node[numb].maxx = max(node[numb<<1].maxx , node[numb<<1|1].maxx);
}
void PushDown(int numb) // 向下往左右儿子方向更新数据；
{node[numb<<1].lazy=node[numb].lazy;node[numb<<1|1].lazy=node[numb].lazy;node[numb<<1].changeLen();node[numb<<1|1].changeLen();node[numb].lazy=0; // 更新完了要清零；
}void change(int l,int r,int numb,int val) // 插入更新数据；
{if(node[numb].l==l&&node[numb].r==r) // 如果区间完全重合，则不需要再往下更新了，先保存起来，可以节约很多的时间（lazy思想）{node[numb].lazy=val;node[numb].changeLen();return;}if(node[numb].lazy!=0)PushDown(numb); // 因为没有找到完全重合的区间，所以要先更新下一层区间；int mid=(node[numb].r+node[numb].l)>>1;if(l>mid)change(l,r,numb<<1|1,val);else if(r<=mid)change(l,r,numb<<1,val);else{change(l,mid,numb<<1,val);change(mid+1,r,numb<<1|1,val);}PushUp(numb); // 最后还得往上返回，更新父节点区间；
}// 查询到 连续区间>=len的 返回左边第一个坐标
int query(int l,int r,int numb)
{if(node[numb].l==node[numb].r){return node[numb].sum;}if(node[numb].lazy!=0)PushDown(numb);int mid=(node[numb].r+node[numb].l)>>1;if(r <= mid)return query(l,r,numb<<1);else if(l > mid)return query(l,r,numb<<1|1);else{return query(l,mid,numb<<1) + query(mid+1, r, numb<<1|1);}
}int queryMax(int l,int r, int numb)
{if(node[numb].l==node[numb].r){return node[numb].maxx;}if(node[numb].lazy!=0)PushDown(numb);int mid=(node[numb].r+node[numb].l)>>1;if(r <= mid)return queryMax(l,r,numb<<1);else if(l > mid)return queryMax(l,r,numb<<1|1);else{return max( queryMax(l,mid,numb<<1) , queryMax(mid+1, r, numb<<1|1));}
}int main()
{int n,m;scanf("%d%d",&n,&m);build(1,n,1);while(m--){int x,y,z;scanf("%d",&z);if(z==1){scanf("%d%d",&x,&y);cout<<query(x,y,1)<<endl;}else if(z == 2){scanf("%d%d",&x,&y);cout<<queryMax(x,y,1)<<endl;}elsescanf("%d%d",&x,&y),change(x,y,1,1);}return 0;
}