数据结构——线段树

例 1 1 1

题目描述

���定一个长为 n n n的序列，有 m m m次操作，每次操作为以下三种之一。

• 修改序列中的一个数
• 求序列中某连续一段所有数的两两乘积的和 mod 1000000007 \text{mod} 1000000007 mod
• 求序列中某连续一段所有相邻两数乘积的和 mod 1000000007 \text{mod} 1000000007 mod

  做法

  一般单点修改的难点都在于区间合并信息的操作。

  Part 1 \text{Part}1 Part1

  先考虑第二个操作，假设对于一个区间我们已经求出了它左右两个子区间的两两乘积之和，例如左区间的数为 a , b , c a,b,c a,b,c，我们右区间的数为 d , e d,e d,e，我们已经知道了 a × b , a × c , b × c a\times b,a\times c,b\times c a×b,a×c,b×c的和与 d × e d \times e d×e的和。

  那合并后增加的部分就为 a × d + a × e + b × d + b × e + c × d + c × e a \times d+a\times e+b\times d+b\times e+c\times d+c\times e a×d+a×e+b×d+b×e+c×d+c×e的和，提取公因式得 a × ( d + e ) + b × ( d + e ) + c × ( d + e ) a\times(d+e)+b\times(d+e)+c\times(d+e) a×(d+e)+b×(d+e)+c×(d+e)，再提取公因式得 ( a + b + c ) × ( d + e ) (a+b+c)\times(d+e) (a+b+c)×(d+e)，我们发现 a + b + c a+b+c a+b+c与 d + e d+e d+e都是维护区间的和，可以在线段树合并时维护区间和就可以了。

  具体操作为我们对于每个区间维护两个信息，一个为这个区间的两两元素乘积之和 a n s 2 ans_2 ans2​，另一个为这个区间所有元素的和 s u m sum sum。

  例如在合并 A A A与 B B B区间到 C C C时，可以这么合并： C . a n s 2 = A . a n s 2 + B . a n s 2 + A . s u m × B . s u m C.ans_2=A.ans_2+B.ans_2+A.sum\times B.sum C.ans2​=A.ans2​+B.ans2​+A.sum×B.sum， C . s u m = A . s u m + B . s u m C.sum=A.sum+B.sum C.sum=A.sum+B.sum。

  Part 2 \text{Part} 2 Part2

  再考虑第一个操作，仿照第二个操作的做法，假设对于一个区间我们已经求出了它左右两个子区间的相邻两数乘积之和，例如左区间的数为 a , b , c a,b,c a,b,c，我们右区间的数为 d , e d,e d,e，我们已经知道了 a × b , b × c a\times b,b\times c a×b,b×c的和与 d × e d \times e d×e的和。

  那合并后增加的部分就为 c × d c\times d c×d，我们发现 c c c与 d d d区间的左右元素，可以在线段树合并时维护左右元素是谁就可以了。

  具体操作为我们对于每个区间维护三个信息，一个为这个区间的两两元素乘积之和 a n s 1 ans_1 ans1​，另一个为这个区间最左边元素为 l l l，最右边元素为 r r r。

  例如在合并 A A A与 B B B区间到 C C C时，可以这么合并： C . a n s 1 = A . a n s 1 + B . a n s 1 + A . r × B . l C.ans_1=A.ans_1+B.ans_1+A.r\times B.l C.ans1​=A.ans1​+B.ans1​+A.r×B.l， C . l = A . l , C . r = B . r C.l=A.l,C.r=B.r C.l=A.l,C.r=B.r。

  这道题启发我们往往不能只维护题目所求的信息（因为这样很有可能无法直接维护）还要维护一些其它的信息。

  例 2 2 2 小白逛公园

  题目传送门

  做法

  在例 1 1 1的引导下，我们可以考虑一个区间的答案可以由左右两个区间的答案更新而来，也可以是左右两个区间的最大子段和，也就是左区间的后缀最大和再加上右区间的前缀最大和。而一个区间的前缀最大和可以是由它的左区间的前缀最大和更新过来，也可使左区间加上右区间的前缀最大和更新过来，右区间同理。所以我们还要维护区间和的信息。

  C o d e Code Code

  #include
  using namespace std;
  const int N=5e5+50;
  int a[N],n,m;
  struct data{
  	int sum,leftmax,rightmax,totalmax;
  }tree[N*4];
  data merge(data A,data B){
  	data C;
  	C.sum=A.sum+B.sum;
  	C.leftmax=max(A.leftmax,A.sum+B.leftmax);
  	C.rightmax=max(B.rightmax,B.sum+A.rightmax);
  	C.totalmax=max(max(A.totalmax,B.totalmax),A.rightmax+B.leftmax);
  	return C;
  }
  void build(int p,int l,int r){
  	if(l==r){
  		tree[p].sum=tree[p].leftmax=tree[p].rightmax=tree[p].totalmax=a[l];
  		return;
  	}
  	int mid=(l+r)/2;
  	build(p*2,l,mid);build(p*2+1,mid+1,r);
  	tree[p]=merge(tree[p*2],tree[p*2+1]);
  	return;
  }
  void modify(int p,int l,int r,int x,int y){
  	if(l==r){
  		tree[p].sum=y;
  		tree[p].leftmax=y;
  		tree[p].rightmax=y;
  		tree[p].totalmax=y;
  		return;
  	}
  	else{
  		int mid=(l+r)/2;
  		if(x>mid) modify(p*2+1,mid+1,r,x,y);
  		else modify(p*2,l,mid,x,y);
  		tree[p]=merge(tree[p*2],tree[p*2+1]);
  	}
  }
  data query(int p,int l,int r,int x,int y){
  	if(l>=x&&r
  		return tree[p];
  	}
  	int mid=(l+r)/2;
  	if(y
  		data A=query(p*2,l,mid,x,mid);
  		data B=query(p*2+1,mid+1,r,mid+1,y);
  		data C;
  		
  		C.sum=A.sum+B.sum;
  		C.leftmax=max(A.leftmax,A.sum+B.leftmax);
  		C.rightmax=max(B.rightmax,B.sum+A.rightmax);
  		C.totalmax=max(max(A.totalmax,B.totalmax),A.rightmax+B.leftmax);
  		return C;
  	}
  }
  int main(){
  	scanf("%d%d",&n,&m);
  	for(int i=1;i
  		int a,b,c;
  		scanf("%d%d%d",&a,&b,&c);
  		if(a==1){
  			if(bc)swap(b,c);
  			printf("%d\n",query(1,1,n,b,c).totalmax);
  		}
  		else{
  			modify(1,1,n,b,c);
  		}
  	}
  	return 0;
  }
  
  	struct node{
  		ll sum,tag;
  	}T[N * 4];
  	void pushup(int p)
  	{
  		T[p].sum = T[p * 2].sum + T[p * 2 + 1].sum;
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].tag = 0;T[p].sum = 0;
  		if(l == r)
  		{
  			T[p].sum = a[l];
  			return;
  		}
  		int mid = (l + r)  1;
  		build(p * 2,l,mid);build(p * 2 + 1,mid + 1,r);
  		pushup(p);
  		return;
  	}
  	void f(int p,int l,int r,int k)
  	{
  		T[p].sum += (r - l + 1) * k;
  		T[p].tag += k;
  		return;
  	}
  	void pushdown(int p,int l,int r)
  	{
  		int mid = (l + r) >> 1;
  		f(p * 2,l,mid,T[p].tag);f(p * 2 + 1,mid + 1,r,T[p].tag);
  		T[p].tag = 0;
  		return;
  	}
  	void update(int p,int l,int r,int x,int y,int k)
  	{
  		if(x 
  			T[p].tag += k;
  			T[p].sum += (r - l + 1) * k;
  			return;
  		}
  		pushdown(p,l,r);
  		int mid = (l + r)  1;
  		if(x  mid)update(p * 2 + 1,mid + 1,r,x,y,k);
  		pushup(p);
  		return;
  	}
  	ll query(int p,int l,int r,int x,int y)
  	{
  		if(x  1;
  		ll res = 0;
  		if(x  mid)res += query(p * 2 + 1,mid + 1,r,x,y);
  		return res;
  	}
  }
  T;
  int main()
  {
  	scanf("%d %d",&n,&m);
  	T.build(1,1,n);
  	while(m--)
  	{
  		getchar();
  		char op[3];
  		scanf("%s",op);
  		if(op[0] == 'A' && op[1]=='s')
  		{
  			int x,y,k;
  			scanf("%d %d",&x,&y);
  			printf("%lld\n",T.query(1,1,n,x,y));
  		}
  		else
  		{
  			int x,y;
  			scanf("%d %d",&x,&y);
  			if(op[0]=='S')y=-y;
  			T.update(1,1,n,x,x,y);
  		}
  	}
  	return 0;
  }
  

  题 2 2 2 【线段树】简单题（CQOI2006）

  思路

  区间翻转，考虑为护 t a g tag tag，表示一个区间被翻转几次。查询时直接下传标记即可。

  C o d e : Code: Code:

  #include
  typedef long long ll;
  using namespace std;
  const int N = 1e5 + 50;
  int n,m;
  int a[N];
  struct Segment
  {
  	struct node{
  		int len,sum,lmax1,rmax1,max1,lmax0,rmax0,max0;
  		bool tag,tag1,tag2;
  	}T[N * 4];
  	void pushup(int p)
  	{
  		T[p].sum = T[p * 2].sum + T[p * 2 + 1].sum;
  		T[p].max1 = max(T[p * 2].max1,T[p * 2 + 1].max1);
  		T[p].max1 = max(T[p].max1,T[p * 2].rmax1 + T[p * 2 + 1].lmax1);
  		T[p].max0 = max(T[p * 2].max0,T[p * 2 + 1].max0);
  		T[p].max0 = max(T[p].max0,T[p * 2].rmax0 + T[p * 2 + 1].lmax0);
  		if(T[p * 2].rmax1 == T[p * 2].len)T[p].max1 = max(T[p].max1,T[p * 2].len + T[p * 2 + 1].lmax1);
  		if(T[p * 2 + 1].lmax1 == T[p * 2 + 1].len)T[p].max1 = max(T[p].max1,T[p * 2 + 1].len + T[p * 2].rmax1);
  		if(T[p * 2].rmax0 == T[p * 2].len)T[p].max0 = max(T[p].max0,T[p * 2].len + T[p * 2 + 1].lmax0);
  		if(T[p * 2 + 1].lmax0 == T[p * 2 + 1].len)T[p].max0 = max(T[p].max0,T[p * 2 + 1].len + T[p * 2].rmax0);
  		T[p].lmax1 = T[p * 2].lmax1;T[p].lmax0 = T[p * 2].lmax0;
  		T[p].rmax1 = T[p * 2 + 1].rmax1;T[p].rmax0 = T[p * 2 + 1].rmax0;
  		if(T[p * 2].lmax1 == T[p * 2].len)T[p].lmax1 = max(T[p].lmax1,T[p * 2].len + T[p * 2 + 1].lmax1);
  		if(T[p * 2].lmax0 == T[p * 2].len)T[p].lmax0 = max(T[p].lmax0,T[p * 2].len + T[p * 2 + 1].lmax0);
  		if(T[p * 2 + 1].rmax1 == T[p * 2 + 1].len)T[p].rmax1 = max(T[p].rmax1,T[p * 2 + 1].len + T[p * 2].rmax1);
  		if(T[p * 2 + 1].rmax0 == T[p * 2 + 1].len)T[p].rmax0 = max(T[p].rmax0,T[p * 2 + 1].len + T[p * 2].rmax0);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].tag = 0;T[p].sum = 0;T[p].len = r - l + 1;T[p].max1 = 0;T[p].tag = T[p].tag1 = T[p].tag2 = 0;
  		T[p].lmax1 = T[p].rmax1 = 0;
  		if(l == r)
  		{
  			if(a[l] == 1)
  				T[p].max1 = T[p].lmax1 = T[p].rmax1 = T[p].sum = 1;
  			if(a[l] == 0)
  				T[p].max0 = T[p].lmax0 = T[p].rmax0 = 1;
  			return;
  		}
  		int mid = (l + r) >> 1;
  		build(p * 2,l,mid);build(p * 2 + 1,mid + 1,r);
  		pushup(p);
  		return;
  	}
  	void f(int p,int l,int r)
  	{
  		T[p].sum = T[p].len - T[p].sum;
  		swap(T[p].lmax1,T[p].lmax0);swap(T[p].rmax1,T[p].rmax0);swap(T[p].max1,T[p].max0);
  		if(T[p].tag1 || T[p].tag2)
  			swap(T[p].tag1,T[p].tag2);
  		else
  			T[p].tag ^= 1;
  		return;
  	}
  	void pushdown(int p,int l,int r)
  	{
  		int mid = (l + r) >> 1;
  		f(p * 2,l,mid);f(p * 2 + 1,mid + 1,r);
  		T[p].tag = 0;
  		return;
  	}
  	void f1(int p,int l,int r)
  	{
  		T[p].tag = 0;T[p].tag2 = 0;
  		T[p].max1 = T[p].lmax1 = T[p].rmax1 = T[p].sum = 0;
  		T[p].max0 = T[p].lmax0 = T[p].rmax0 = T[p].len;
  		T[p].tag1 = 1;
  		return;
  	}
  	void pushdown1(int p,int l,int r)
  	{
  		int mid = (l + r) >> 1;
  		f1(p * 2,l,mid);f1(p * 2 + 1,mid + 1,r);
  		T[p].tag1 = 0;
  		return;
  	}
  	void f2(int p,int l,int r)
  	{
  		T[p].tag = 0;T[p].tag1 = 0;
  		T[p].max1 = T[p].lmax1 = T[p].rmax1 = T[p].sum = T[p].len;
  		T[p].max0 = T[p].lmax0 = T[p].rmax0 = 0;
  		T[p].tag2 = 1;
  		return;
  	}
  	void pushdown2(int p,int l,int r)
  	{
  		int mid = (l + r) >> 1;
  		f2(p * 2,l,mid);f2(p * 2 + 1,mid + 1,r);
  		T[p].tag2 = 0;
  		return;
  	}
  	void update(int p,int l,int r,int x,int y,int op)
  	{
  //		cout 
  			if(op == 2)
  				f(p,l,r);
  			else if(op == 0)
  			{
  				T[p].tag = 0;T[p].tag2 = 0;
  				T[p].max1 = T[p].lmax1 = T[p].rmax1 = T[p].sum = 0;
  				T[p].max0 = T[p].lmax0 = T[p].rmax0 = T[p].len;
  				T[p].tag1 = 1;
  			}
  			else if(op == 1)
  			{
  				T[p].tag = 0;T[p].tag1 = 0;
  				T[p].max1 = T[p].lmax1 = T[p].rmax1 = T[p].sum = T[p].len;
  				T[p].max0 = T[p].lmax0 = T[p].rmax0 = 0;
  				T[p].tag2 = 1;
  			}
  			return;
  		}
  		if(T[p].tag)
  			pushdown(p,l,r);
  		if(T[p].tag1)
  			pushdown1(p,l,r);
  		if(T[p].tag2)
  			pushdown2(p,l,r);
  		int mid = (l + r)  1;
  		if(x 
  //		cout 
  //		cout 
  			node res;
  			res.rmax1 = res.lmax1 = res.max1 = 0;
  			res.rmax0 = res.lmax0 = res.max0 = 0;
  			node res1 = query2(p * 2,l,mid,x,y);
  			node res2 = query2(p * 2 + 1,mid + 1,r,x,y);
  			res.len = res1.len + res2.len;
  			res.max1 = max(res.max1,max(res1.max1,res2.max1));
  			res.max1 = max(res.max1,res1.rmax1 + res2.lmax1);
  			if(res1.rmax1 == res1.len)res.max1 = max(res.max1,res1.len + res2.lmax1);
  			if(res2.lmax1 == res2.len)res.max1 = max(res.max1,res2.len + res1.rmax1);
  			res.lmax1 = res1.lmax1;res.lmax0 = res1.lmax0;
  			res.rmax1 = res2.rmax1;res.rmax0 = res2.rmax0;
  			if(res1.lmax1 == res1.len)res.lmax1 = max(res.lmax1,res1.len + res2.lmax1);
  			if(res1.lmax0 == res1.len)res.lmax0 = max(res.lmax0,res1.len + res2.lmax0);
  			if(res2.rmax1 == res2.len)res.rmax1 = max(res.rmax1,res2.len + res1.rmax1);
  			if(res2.rmax0 == res2.len)res.rmax0 = max(res.rmax0,res2.len + res1.rmax0);
  			return res;
  		}
  	}
  }
  T;
  int main()
  {
  	scanf("%d %d",&n,&m);
  	T.build(1,1,n);
  	while(m--)
  	{
  		int op,a,b;
  		scanf("%d",&op);
  		if(op == 1)
  		{
  			scanf("%d %d",&a,&b);
  			T.update(1,1,n,a,b,2);
  		}
  		else
  		{
  			scanf("%d",&a);
  			int x=T.query1(1,1,n,a,a);
  			printf("%d\n",x);
  		}
  	}
  	return 0;
  }
  
  	struct node{
  		int sum,tag;
  	}T[N * 4];
  	void pushup(int p)
  	{
  		T[p].sum = T[p * 2].sum + T[p * 2 + 1].sum;
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].tag = -1;T[p].sum = 0;
  		if(l == r)
  		{
  			T[p].sum = a[l];
  			return;
  		}
  		int mid = (l + r)  1;
  		build(p * 2,l,mid);build(p * 2 + 1,mid + 1,r);
  		pushup(p);
  		return;
  	}
  	void f(int p,int l,int r,int k)
  	{
  		T[p].sum = (r - l + 1) * k;
  		T[p].tag = k;
  		return;
  	}
  	void pushdown(int p,int l,int r)
  	{
  		int mid = (l + r)  1;
  		f(p * 2,l,mid,T[p].tag);f(p * 2 + 1,mid + 1,r,T[p].tag);
  		T[p].tag = -1;
  		return;
  	}
  	void update(int p,int l,int r,int x,int y,int k)
  	{
  		if(x 
  			T[p].tag=k;
  			T[p].sum=(r-l+1)*k;
  			return;
  		}
  		if(T[p].tag!=-1)pushdown(p,l,r);
  		int mid = (l + r)  1;
  		if(x 
  		if(x 
  	scanf("%d %d",&n,&m);
  	T.build(1,1,n);
  	for(int i=1;i
  		int op,l,r;
  		scanf("%d %d %d",&op,&l,&r);
  		if(op==1)T.update(1,1,n,l,r-1,1);
  		else T.update(1,1,n,l,r-1,0);
  	}
  	printf("%d\n",T.query(1,1,n,1,n));
  	return 0;
  }
  
  	struct node{
  		int tag,maxx;
  	}T[N*4];
  	void pushup(int p)
  	{
  		T[p].maxx=max(T[p*2].maxx,T[p*2+1].maxx);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].tag=T[p].maxx=0;
  		if(l==r)
  		{
  			T[p].maxx=0;
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		pushup(p);
  		return;
  	}
  	void pushdown(int p)
  	{
  		T[p*2].tag+=T[p].tag;
  		T[p*2+1].tag+=T[p].tag;
  		T[p*2].maxx+=T[p].tag;
  		T[p*2+1].maxx+=T[p].tag;
  		T[p].tag=0;
  		return;
  	}
  	void update(int p,int l,int r,int x,int y,int k)
  	{
  		if(x
  			T[p].maxx+=k;
  			T[p].tag+=k;
  			return;
  		}
  		if(T[p].tag!=0)pushdown(p);
  		int mid=(l+r)1;
  		if(x
  		if(x
  	scanf("%lld %lld %lld",&n,&s,&m);
  	T.build(1,1,n);
  	for(int i=1;i
  		int l,r,x;
  		scanf("%lld %lld %lld",&l,&r,&x);
  		if(T.query(1,1,n,l,r-1)+x
  			T.update(1,1,n,l,r-1,x);
  			printf("YES\n");
  		}
  		else printf("NO\n");
  	}
  	return 0;
  }
  
  	struct node{
  		int ans,tag;
  	}T[N*4];
  	node merge(node A,node B)
  	{
  		node C;
  		C.tag=-1;C.ans=A.ans+B.ans;
  		return C; 
  	}
  	void pushup(int p)
  	{
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].tag=-1;
  		if(l==r)
  		{
  			T[p].ans=0;
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		pushup(p);
  		return;
  	}
  	void f(int p,int l,int r)
  	{
  		T[p].tag=1;T[p].ans=r-l+1;
  		return;
  	}
  	void pushdown(int p,int l,int r)
  	{
  		int mid=(l+r)1;
  		f(p*2,l,mid);f(p*2+1,mid+1,r);
  		T[p].tag=0;
  		return;
  	}
  	void update(int p,int l,int r,int x,int y)
  	{
  		if(x
  			T[p].ans=r-l+1;
  			T[p].tag=1;
  			return;
  		}
  		if(T[p].tag==1)
  			pushdown(p,l,r);
  		int mid=(l+r)1;
  		if(x
  	scanf("%d %d %d",&L,&R,&n);
  	L+=M;R+=M; 
  	T.build(1,1,200050);
  	for(int i=1;i
  		int l,r;
  		scanf("%d %d",&l,&r);
  		l+=M;r+=M;
  		T.update(1,1,200050,l,r-1);
  	}
  	printf("%d\n",T.T[1].ans);
  	return 0;
  }
  
  	int l,r,flag;
  }tree[maxm];
  void Build(int k,int l,int r){
  	tree[k]=(Seg){l,r,0};
  	if(l==r)return ;
  	int mid=(l+r)1;
  	Build(lc,l,mid);
  	Build(rc,mid+1,r);
  }
  void pushup(int k){
  	if(tree[lc].flag&&tree[rc].flag)tree[k].flag=1;
  }
  void pushdown(int k){
  	if(!tree[k].flag)return;
  	tree[lc].flag=tree[rc].flag=1;
  }
  void Ask(int k,int l,int r){
  	if(tree[k].lr||tree[k].r
  		if(tree[k].flag==0){
  			flag=true;
  			tree[k].flag=1;
  		}
  		return;
  	}
  	pushdown(k);
  	Ask(lc,l,r);
  	Ask(rc,l,r);
  	pushup(k);
  }
  signed main(){
  	cinllrrn;
  	ll+=uni;
  	rr+=uni;
  	rr--; 
  	Build(1,ll,rr);
  	for(int i=1;i
  		flag=false;
  		Ask(1,x[i]+uni,y[i]+uni-1);
  		if(flag==true)ans++;
  	}
  	cout
  	struct node{
  		int lc,rc,ans,tag;
  	}T[N*4];
  	node merge(node A,node B)
  	{
  		node C;C.lc=C.rc=C.ans=0;C.tag=-1;
  		if(A.rc==B.lc)C.ans=A.ans+B.ans-1;
  		else C.ans=A.ans+B.ans;
  		C.lc=A.lc;C.rc=B.rc;
  		return C; 
  	}
  	void pushup(int p)
  	{
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].tag=-1;T[p].lc=T[p].rc=T[p].ans=0;
  		if(l==r)
  		{
  			T[p].lc=T[p].rc=xc;T[p].ans=1;
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		pushup(p);
  		return;
  	}
  	void f(int p,int k)
  	{
  		T[p].tag=k;
  		T[p].ans=1;T[p].lc=T[p].rc=k;
  		return;
  	}
  	void pushdown(int p)
  	{
  		f(p*2,T[p].tag);f(p*2+1,T[p].tag);
  		T[p].tag=-1;
  		return;
  	}
  	void update(int p,int l,int r,int x,int y,int k)
  	{
  		if(x
  			T[p].ans=1;T[p].lc=T[p].rc=k;
  			T[p].tag=k;
  			return;
  		}
  		if(T[p].tag!=-1)
  			pushdown(p);
  		int mid=(l+r)1;
  		if(x
  	scanf("%d %d",&xc,&n);
  	T.build(1,1,200010);
  	for(int i=1;i
  		int l,r,x;
  		scanf("%d %d %d",&l,&r,&x);
  		l+=M;r+=M;
  		T.update(1,1,200010,l,r-1,x);
  	}
  	cout
  	scanf("%d %d",&h,&n);
  	for(int i=1,x;i
  		if(l[i]
  	node C;C.lans=C.rans=C.ans=C.sum=0;
  	C.ans=max(A.ans,B.ans);C.lans=A.lans;C.rans=B.rans;C.sum=A.sum+B.sum;
  	C.ans=max(C.ans,A.rans+B.lans);
  	C.lans=max(C.lans,A.sum+B.lans);C.rans=max(C.rans,A.rans+B.sum);
  	return C;
  }
  
  	struct node{
  		int lans,rans,ans,sum;
  	}T[N*4];
  	node merge(node A,node B)
  	{
  		node C;C.lans=C.rans=C.ans=C.sum=0;
  		C.ans=max(A.ans,B.ans);C.lans=A.lans;C.rans=B.rans;C.sum=A.sum+B.sum;
  		C.ans=max(C.ans,A.rans+B.lans);
  		C.lans=max(C.lans,A.sum+B.lans);C.rans=max(C.rans,A.rans+B.sum);
  		return C;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].lans=T[p].rans=T[p].ans=T[p].sum=0;
  		if(l==r)
  		{
  			T[p].sum=T[p].lans=T[p].rans=T[p].ans=a[l];
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	void update(int p,int l,int r,int x,int y)
  	{
  		if(l==r)
  		{
  			T[p].ans=T[p].lans=T[p].rans=T[p].sum=y;
  			return;
  		}
  		int mid=(l+r)1;
  		if(x
  		if(x
  	scanf("%d",&n);
  	for(int i=1;i
  		int x,y;
  		scanf("%d %d",&x,&y);
  		printf("%d\n",T.query(1,1,n,x,y).ans);
  	}
  	return 0;
  }
  
  	struct node{
  		int lans,rans,ans,sum;
  	}T[N*4];
  	node merge(node A,node B)
  	{
  		node C;C.lans=C.rans=C.ans=C.sum=0;
  		C.ans=max(A.ans,B.ans);C.lans=A.lans;C.rans=B.rans;C.sum=A.sum+B.sum;
  		C.ans=max(C.ans,A.rans+B.lans);
  		C.lans=max(C.lans,A.sum+B.lans);C.rans=max(C.rans,A.rans+B.sum);
  		return C;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].lans=T[p].rans=T[p].ans=T[p].sum=0;
  		if(l==r)
  		{
  			T[p].sum=T[p].lans=T[p].rans=T[p].ans=a[l];
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	void update(int p,int l,int r,int x,int y)
  	{
  		if(l==r)
  		{
  			T[p].ans=T[p].lans=T[p].rans=T[p].sum=y;
  			return;
  		}
  		int mid=(l+r)1;
  		if(x
  		if(x
  	scanf("%d",&n);
  	for(int i=1;i
  		int op,x,y;
  		scanf("%d %d %d",&op,&x,&y);
  		if(op==1)
  		{
  			if(xy)swap(x,y);
  			printf("%d\n",T.query(1,1,n,x,y).ans);
  		}
  		else T.update(1,1,n,x,y);
  	}
  	return 0;
  }
  
  	struct node{
  		int lans,rans,ans,sum;
  	}T[N*4];
  	node merge(node A,node B)
  	{
  		node C;C.lans=C.rans=C.ans=C.sum=0;
  		C.ans=max(A.ans,B.ans);C.lans=A.lans;C.rans=B.rans;C.sum=A.sum+B.sum;
  		C.ans=max(C.ans,A.rans+B.lans);
  		C.lans=max(C.lans,A.sum+B.lans);C.rans=max(C.rans,A.rans+B.sum);
  		return C;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].lans=T[p].rans=T[p].ans=T[p].sum=0;
  		if(l==r)
  		{
  			T[p].sum=T[p].lans=T[p].rans=T[p].ans=a[l];
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	void update(int p,int l,int r,int x,int y)
  	{
  		if(l==r)
  		{
  			T[p].ans=T[p].lans=T[p].rans=T[p].sum=y;
  			return;
  		}
  		int mid=(l+r)1;
  		if(x
  		if(x
  	scanf("%lld %lld",&n,&m);
  	for(int i=1;i
  		int op,x,y;
  		scanf("%lld %lld %lld",&op,&x,&y);
  		if(op==1)
  		{
  			if(xy)swap(x,y);
  			printf("%lld\n",T.query(1,1,n,x,y).ans);
  		}
  		else T.update(1,1,n,x,y);
  	}
  	return 0;
  }
  
  	struct node{
  		int lans,rans,sum,ans;
  	}T[N*4];
  	node merge(node A,node B)
  	{
  		node C;C.lans=C.rans=C.sum=C.ans=0;
  		C.sum=A.sum+B.sum;
  		C.ans=max(A.ans,B.ans);C.ans=max(C.ans,A.rans+B.lans);
  		C.lans=A.lans;C.lans=max(C.lans,A.sum+B.lans);
  		C.rans=B.rans;C.rans=max(C.rans,A.rans+B.sum);
  		return C; 
  	}
  	void pushup(int p)
  	{
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].ans=T[p].lans=T[p].rans=T[p].sum=0;
  		if(l==r)
  		{
  			T[p].lans=T[p].rans=T[p].ans=T[p].sum=a[l];
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		pushup(p);
  		return;
  	}
  	node query(int p,int l,int r,int x,int y)
  	{
  		if(xy)
  			return node{0,0,0,0};
  		if(x
  //	freopen("data.in","r",stdin);
  //	freopen("baoli.out","w",stdout);
  	scanf("%d",&cas);
  	while(cas--)
  	{
  		scanf("%d",&n);
  		for(int i=1;i
  			int a1,b1,a2,b2;
  			scanf("%d %d %d %d",&a1,&b1,&a2,&b2);
  			if(b1=a2)
  			{
  				int x=T.query(1,1,n,a2,b1).ans;
  //				cout
  	struct node{
  		int ans,lans,rans,sum;
  		int ans2,lans2,rans2;
  		int tag;
  	}T[N*4];
  	node merge(node A,node B)
  	{
  		node C;C.ans=C.lans=C.rans=0;
  		C.sum=A.sum+B.sum;
  		C.ans=max(A.ans,B.ans);C.lans=A.lans;C.rans=B.rans;
  		C.ans=max(C.ans,A.rans+B.lans);
  		C.lans=max(C.lans,A.sum+B.lans);C.rans=max(C.rans,A.rans+B.sum);
  		
  		C.ans2=min(A.ans2,B.ans2);C.lans2=A.lans2;C.rans2=B.rans2;
  		C.ans2=min(C.ans2,A.rans2+B.lans2);
  		C.lans2=min(C.lans2,A.sum+B.lans2);C.rans2=min(C.rans2,B.sum+A.rans2);
  		return C;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].ans=T[p].lans=T[p].rans=0;T[p].ans2=T[p].lans2=T[p].rans2=0;
  		if(l==r)
  		{
  			T[p].ans=T[p].lans=T[p].rans=a[l];
  			T[p].ans2=T[p].lans2=T[p].rans2=a[l];
  			T[p].sum=a[l];
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	void update(int p,int l,int r,int x,int y,int k)
  	{
  		if(x
  			T[p].ans=T[p].lans=T[p].rans=k;
  			T[p].ans2=T[p].lans2=T[p].rans2=k;
  			T[p].sum=k;
  			return;
  		}
  		int mid=(l+r)1;
  		if(x
  		if(x
  	scanf("%d",&n);
  	for(int i=1;i
  		int x,y;
  		scanf("%d %d",&x,&y);
  		T.update(1,1,n,x,x,y);
  		printf("%d\n",max(T.T[1].sum-T.T[1].ans2,max(T.query_max(1,1,n,1,n-1).ans,T.query_max(1,1,n,2,n).ans)));
  	}
  	return 0;
  }
  
  	struct node{
  		int len,lmax,rmax;
  		int sum,tag;
  	}T[N * 4];
  	void pushup(int p)
  	{
  		T[p].sum = max(T[p * 2].sum,T[p * 2 + 1].sum);
  		T[p].sum = max(T[p].sum,T[p * 2].rmax + T[p * 2 + 1].lmax);
  		T[p].lmax = T[p * 2].lmax;T[p].rmax = T[p * 2 + 1].rmax;
  		if(T[p * 2].len == T[p * 2].sum)T[p].sum = max(T[p].sum,T[p * 2].len + T[p * 2 + 1].lmax),T[p].lmax = max(T[p].lmax,T[p * 2].len + T[p * 2 + 1].lmax);
  		if(T[p * 2 + 1].len == T[p * 2 + 1].sum)T[p].sum = max(T[p].sum,T[p * 2 + 1].len + T[p * 2].rmax),T[p].rmax = max(T[p].rmax,T[p * 2 + 1].len + T[p * 2].rmax);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].tag = 0;T[p].lmax = T[p].rmax = T[p].sum = T[p].len = r - l + 1;
  		if(l == r)
  			return;
  		int mid = (l + r)  1;
  		build(p * 2,l,mid);build(p * 2 + 1,mid + 1,r);
  		pushup(p);
  		return;
  	}
  	void f(int p,int k)
  	{
  		if(k == 1)
  			T[p].sum = T[p].lmax = T[p].rmax = 0,T[p].tag = 1;
  		else
  			T[p].sum = T[p].lmax = T[p].rmax = T[p].len,T[p].tag = 2;
  		return;
  	}
  	void pushdown(int p)
  	{
  		f(p * 2,T[p].tag);f(p * 2 + 1,T[p].tag);
  		T[p].tag = 0;
  		return;
  	}
  	void update(int p,int l,int r,int x,int y,int op)
  	{
  		if(x 
  			if(op == 1)
  				T[p].sum = T[p].lmax = T[p].rmax = 0,T[p].tag = 1;
  			else
  				T[p].sum = T[p].lmax = T[p].rmax = T[p].len,T[p].tag = 2;
  			return;
  		}
  		if(T[p].tag)pushdown(p);
  		int mid = (l + r)  1;
  		if(x 
  		if(l == r)return l;
  		if(T[p].tag)pushdown(p);
  		int mid = (l + r)  1;
  		if(T[p * 2].sum = k)return query(p * 2,l,mid,k);
  		if(T[p * 2].rmax + T[p * 2 + 1].lmax = k)return mid - T[p * 2].rmax + 1;
  		else return query(p * 2 + 1,mid + 1,r,k);
  	}
  }
  T;
  int main()
  {
  	scanf("%d %d",&n,&m);
  	T.build(1,1,n);
  	for(int i = 1;i 
  		int op;
  		scanf("%d",&op);
  		if(op == 1)
  		{
  			int x;
  			scanf("%d",&x);
  			if(T.T[1].sum = x)
  			{
  				int ans = T.query(1,1,n,x);
  				printf("%d\n",ans);
  				T.update(1,1,n,ans,ans + x - 1,op);
  			}
  			else printf("0\n");
  		}
  		else
  		{
  			int x,y;
  			scanf("%d %d",&x,&y);
  			T.update(1,1,n,x,x + y - 1,op);
  		}
  	}
  	return 0;
  }
  
  	struct node{
  		int ans,maxx,minn,ans2;
  	}T[N*4];
  	node merge(node a,node b)
  	{
  		node c;
  		c.ans=max(a.ans,b.ans);c.ans2=max(a.ans2,b.ans2);
  		c.maxx=max(a.maxx,b.maxx);c.minn=min(a.minn,b.minn);
  		c.ans=max(c.ans,b.maxx-a.minn);c.ans2=max(c.ans2,a.maxx-b.minn);
  		return c;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].maxx=T[p].minn=T[p].ans=T[p].ans2=0;
  		if(l==r)
  		{
  			T[p].maxx=T[p].minn=a[l];
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		T[p]=merge(T[p*2],T[p*2+1]);
  		return;
  	}
  	node query(int p,int l,int r,int x,int y)
  	{
  		if(x
  	scanf("%d",&n);
  	for(int i=1;i
  		int x,y;
  		scanf("%d %d",&x,&y);
  		if(x
  	struct node{
  		int maxx,minn;
  	}T[N*4];
  	void pushup(int p)
  	{
  		T[p].maxx=max(T[p*2].maxx,T[p*2+1].maxx);
  		T[p].minn=min(T[p*2].minn,T[p*2+1].minn);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		if(l==r)
  		{
  			T[p].maxx=T[p].minn=a[l];
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		pushup(p);
  		return;
  	}
  	int query_max(int p,int l,int r,int x,int y)
  	{
  		if(x
  		if(x
  	scanf("%d %d",&n,&q);
  	for(int i=1;i
  		int l,r;
  		scanf("%d %d",&l,&r);
  		printf("%d\n",T.query_max(1,1,n,l,r)-T.query_min(1,1,n,l,r));
  	}
  	return 0;
  }
  
  	struct node{
  		int lans,rans,ans;
  	}T[N*4];
  	void pushup(int p,int l,int r)
  	{
  		int mid=(l+r)1;
  		T[p].ans=max(T[p*2].ans,T[p*2+1].ans);T[p].lans=T[p*2].lans;T[p].rans=T[p*2+1].rans;
  		if(a[mid]==a[mid+1])
  			T[p].ans=max(T[p].ans,T[p*2].rans+T[p*2+1].lans);
  		if(a[l]==a[mid]&&a[mid]==a[mid+1])
  			T[p].lans=max(T[p].lans,mid-l+1+T[p*2+1].lans);
  		if(a[r]==a[mid+1]&&a[mid]==a[mid+1])
  			T[p].rans=max(T[p].rans,r-mid+T[p*2].rans);
  		return;
  	}
  	void build(int p,int l,int r)
  	{
  		T[p].ans=T[p].lans=T[p].rans=0;
  		if(l==r)
  		{
  			T[p].ans=T[p].lans=T[p].rans=1;
  			return;
  		}
  		int mid=(l+r)1;
  		build(p*2,l,mid);build(p*2+1,mid+1,r);
  		pushup(p,l,r);
  		return;
  	}
  	node merge(node A,node B,int l,int r,int x)
  	{
  		node C;C.lans=C.rans=C.ans=0;
  		C.ans=max(A.ans,B.ans);C.lans=A.lans;C.rans=B.rans;
  		if(a[x]==a[x+1])
  			C.ans=max(C.ans,A.rans+B.lans);
  		if(a[x]==a[x+1]&&a[l]==a[x])
  			C.lans=max(C.ans,x-l+1+B.lans);
  		if(a[x]==a[x+1]&&a[r]==a[x])
  			C.rans=max(C.rans,r-x+A.rans);
  		return C;
  	}
  	node query(int p,int l,int r,int x,int y)
  	{
  		if(x
  			node xx=query(p*2,l,mid,x,y),yy=query(p*2+1,mid+1,r,x,y);
  			return merge(xx,yy,max(l,x),min(r,y),mid);
  		}
  	}
  }T;
  int main()
  {
  	scanf("%d %d",&n,&q);
  	for(int i=1;i
  		int l,r;
  		scanf("%d %d",&l,&r);
  		printf("%d\n",T.query(1,1,n,l,r).ans);
  	}
  	return 0;
  }