linkkkk
题意：
给定一个长度为n的数组，两种操作：
1.单点修改
2.求区间[ l , r ]里不下降子串的个数。
思路：
跟线段树维护最大连续子段和类似
维护左右端点，子串个数，从左端点开始的不下降连续序列长度c n t l，从右端点开始的不下降连续序列长度c n t r。
答案是具有合并性的，对于p u s h u p函数来说：
答案除了左子区间里不下降串的个数，右子区间里不下降串的个数，还有合并后的答案。如果左子区间右端点的值小于等于右子区间左端点的值的话，那么答案还应该加上左子区间里从右端点开始的不下降连续序列长度*右子区间里从左端点开始的不下降连续序列长度。并且要更新c n t l , c n t r。
查询的时候，对于不完整的子区间，也要考虑答案的合并
代码：
// Problem: E. Non-Decreasing Dilemma // Contest: Codeforces - Codeforces Round #742 (Div. 2) // URL: https://codeforces.com/contest/1567/problem/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> //#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; typedef pair<string,string>PSS; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define x first #define y second ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=2e5+100; struct node{ ll l,r; ll sum; ll cntl,cntr; }tr[maxn*4]; ll n,a[maxn],m; void pushup(int u){ node l=tr[u<<1],r=tr[u<<1|1]; tr[u].sum=l.sum+r.sum; if(a[l.r]<=a[r.l]) tr[u].sum+=l.cntr*r.cntl; if(l.cntl==l.r-l.l+1){ tr[u].cntl=l.cntl; if(a[l.r]<=a[r.l]) tr[u].cntl+=r.cntl; } else tr[u].cntl=l.cntl; if(r.cntr==r.r-r.l+1){ tr[u].cntr=r.cntr; if(a[l.r]<=a[r.l]) tr[u].cntr+=l.cntr; } else tr[u].cntr=r.cntr; } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,1,1,1}; return ; } tr[u]={l,r,0,0,0}; int mid=(l+r)/2; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } void update(int u,int l,int r,int pos,int val){ if(l==r&&l==pos){ a[pos]=val; return ; } int mid=(l+r)/2; if(pos<=mid) update(u<<1,l,mid,pos,val); if(pos>mid) update(u<<1|1,mid+1,r,pos,val); pushup(u); } ll query(int u,int l,int r,int ql,int qr){ if(l>=ql&&r<=qr) return tr[u].sum; int mid=(l+r)/2; ll ans=0; if(qr<=mid) return query(u<<1,l,mid,ql,qr); else if(ql>mid) return query(u<<1|1,mid+1,r,ql,qr); else{ ans=query(u<<1,l,mid,ql,qr)+query(u<<1|1,mid+1,r,ql,qr); node ll=tr[u<<1],rr=tr[u<<1|1]; if(a[ll.r]<=a[rr.l]) ans+=min(ll.r-ql+1,ll.cntr)*min(qr-rr.l+1,rr.cntl); return ans; } } int main() { n=read;m=read; rep(i,1,n) a[i]=read; build(1,1,n); rep(i,1,m){ int op=read,l=read,r=read; if(op==1){ update(1,1,n,l,r); } else printf("%lld\n",query(1,1,n,l,r)); } return 0; }
