【*2200线段树Pushup】CF1567 E-Toy模板网

这篇具有很好参考价值的文章主要介绍了【*2200线段树Pushup】CF1567 E。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Problem - E - Codeforces

题意：

【*2200线段树Pushup】CF1567 E,线段树与树状数组,算法,c++,数据结构

思路：

维护这些信息即可

【*2200线段树Pushup】CF1567 E,线段树与树状数组,算法,c++,数据结构

Code：文章来源地址https://www.toymoban.com/news/detail-563750.html

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int mxn=2e5+10;
const int mxe=2e5+10;
const int mod=1e9+7;
const int Inf=1e18;

struct info{
	int mx,lmx,rmx,sz,cnt=0;
	int lval,rval;
};

info operator+(const info &l,const info &r){
	info res;

	res.cnt=l.cnt+r.cnt;
	if(l.rval<=r.lval) res.cnt+=l.rmx*r.lmx;

	res.sz=l.sz+r.sz;
	res.lval=l.lval;
	res.rval=r.rval;

	if(l.mx==l.sz){
		if(l.rval<=r.lval) res.lmx=l.sz+r.lmx;
		else res.lmx=l.sz;
	}else{
		res.lmx=l.lmx;
	}

	if(r.mx==r.sz){
		if(l.rval<=r.lval) res.rmx=r.sz+l.rmx;
		else res.rmx=r.sz;
	}else{
		res.rmx=r.rmx;
	}

	res.mx=max(l.mx,r.mx);

	if(l.rval<=r.lval) res.mx=max(res.mx,l.rmx+r.lmx);

	return res;
}

struct Segtree{
	info Val;
}tree[mxe<<2];

int N,Q,op,x,y,l,r;
int a[mxn];

void pushup(int rt){
	tree[rt].Val=tree[rt<<1].Val+tree[rt<<1|1].Val;
}
void build(int rt,int l,int r){
	if(l==r){
		tree[rt].Val.cnt=1;
		tree[rt].Val.lmx=tree[rt].Val.rmx=tree[rt].Val.mx=tree[rt].Val.sz=1;
		tree[rt].Val.lval=tree[rt].Val.rval=a[l];
		return;
	}
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}
void change(int rt,int l,int r,int x,int k){
	if(l==r){
		tree[rt].Val.cnt=1;
		tree[rt].Val.lmx=tree[rt].Val.rmx=tree[rt].Val.mx=tree[rt].Val.sz=1;
		tree[rt].Val.lval=tree[rt].Val.rval=k;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) change(rt<<1,l,mid,x,k);
	else change(rt<<1|1,mid+1,r,x,k);
	pushup(rt);
}
info query(int rt,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return tree[rt].Val;
	}
	int mid=l+r>>1;
	if(x>mid) return query(rt<<1|1,mid+1,r,x,y);
	else if(y<=mid) return query(rt<<1,l,mid,x,y);
	else{
		return query(rt<<1,l,mid,x,y)+query(rt<<1|1,mid+1,r,x,y);
	}
}
void solve(){
	cin>>N>>Q;
	for(int i=1;i<=N;i++) cin>>a[i];
	build(1,1,N);
	while(Q--){
		cin>>op;
		if(op==1){
			cin>>x>>y;
			change(1,1,N,x,y);
		}else{
			cin>>l>>r;
			cout<<query(1,1,N,l,r).cnt<<'\n';
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int __=1;//cin>>__;
    while(__--)solve();return 0;
}

到了这里，关于【*2200线段树Pushup】CF1567 E的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！