一道简单题

线段树题解

对于每次查询的T(l,r,x)，暂时不看第三个参数，即 Q(l,r)= $\sum_{i=l}^{r}$ max(a[i],a[i+1],…,a[r]). 每个位置对答案有个贡献且这个贡献等于[i,r]这段区间中a的最大值
所以

左边的a[j] (j<i)不会影响右边的贡献
右边的a[i]最大值可能会影响左边的贡献

例如区间查询 [1,8]：[2，5，3，2，3，4，2，1]
各个位置贡献分别为:[5，5，4，4，4，4，2，1]
显然，区间内每个位置的贡献是逐渐递减的
而[1,4]和[5,8]贡献：[5，5，3，2] [4，4，2，1]

考虑两子区间Pushup成大区间，从右往左看，右孩子的贡献和sum[rs] (4,4,2,1)直接传给了父节点，而左区间有一部分被右区间的最大Max[rs] (4)“覆盖”了。
由于从区间内左往右贡献是单调递减的，所以可以试着在左区间二分
设右区间的最大值为maxr

如果maxr>=左区间的最大值，左区间被全部覆盖，return maxr*len;
如果maxr<=区间右端点，那么，maxr不会影响区间内的贡献，return sum[rt];
否则将这个区间二分成左右两个区间
如果maxr<右孩子的最大值，这时，maxr只会影响右孩子不会影（要影响也是右孩子的最大值来影响）左孩子，再去递归找右孩子的贡献，return (sum[rt]-sum[rs])+find_sum(右孩子);（为什么是sum[rt]-sum[rs]见代码中的解释）
如果max>右孩子的最大值，右孩子被全部覆盖，递归找左孩子的贡献，return find_sum(左孩子)+maxr*右区间长度;

有了find_sum()这个函数，就可以建树和查询区间了，每次二分会多乘以一个logn，所以总的复杂度O（nlognlogn），最后，要注意在查询的时候，得先右后左，记录最大值，考虑右边最大值对左边区间的影响

回到开头，我们计算的是Q(l,r),即T(l,r,r)，容易发现， T(l,r,x)=Q(l,x)-Q(r+1,x);
那么就这样讲完了，表达得不太好，还是看代码吧qwq

代码

#include<iostream>
using namespace std;
typedef long long ll; 
const int N=2e5+10;
ll n,a[N];
struct Segment{
	#define ls (rt<<1)
	#define rs (rt<<1|1)
	ll sum[N<<2],Max[N<<2];
	ll find_sum(int rt,int l,int r,ll maxr){//O(logn) 
		//左端的最大值 
		if(Max[rt]<=maxr) return maxr*(r-l+1);
		//右端的最小值 
		if(a[r]>=maxr) return sum[rt];
		//递归 
		int m=l+r>>1;	
		if(Max[rs]>maxr) return sum[rt]-sum[rs] + find_sum(rs,m+1,r,maxr);	
//return find_sum(ls,l,m,Max[rs]) + find_sum(rs,m+1,r,maxr); 
//由于之前计算过sum[rt]=find_sum(ls,l,m,Max[rs])+sum[rs]，
//所以左边的贡献 = sum[rt]-sum[rs]，而不必再递归下去 
		else return find_sum(ls,l,m,maxr)+maxr*(r-m);		
	}
	void build(int rt,int l,int r){
		if(l==r) {
			sum[rt]=a[l];
			Max[rt]=a[l];
			return;
		}
		int m=l+r>>1;
		build(rs,m+1,r);
		build(ls,l,m);
		//Pushup
		Max[rt]=max(Max[ls],Max[rs]);
		sum[rt]=find_sum(ls,l,m,Max[rs])+sum[rs];//节点更新 
	}
	ll query(int rt,int l,int r,int ql,int qr,ll &maxr)
	{
		if(ql<=l&&r<=qr) {
			ll ans=find_sum(rt,l,r,maxr);
			maxr=max(maxr,Max[rt]);	//更新右边的最大值 
			return ans;
		}
		int m=l+r>>1;
		ll ans=0;
		//先右后左 
		if(qr>m) ans+=query(rs,m+1,r,ql,qr,maxr);	
		if(ql<=m) ans+=query(ls,l,m,ql,qr,maxr);	
		return ans;
	}
	ll _query(int l,int r){
		if(l>r) return 0;
		ll maxr=0;		//初始置为0
		return query(1,1,n,l,r,maxr);
	}
}tr;
	


int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	tr.build(1,1,n);
	
	int q;cin>>q;
	while(q--){
		int l,r,x;
		cin>>l>>r>>x;
		cout<<tr._query(l,x)-tr._query(r+1,x)<<" ";
	}
	return 0;
}

Pushup的logn化，能想到这些源于我在洛谷上做的一道相似的题:楼房重建
最后，谢谢观看

题解 | #一道简单题#

一道简单题

线段树题解

代码

完结撒花