Extended version of the title: there are two lengths n n Sequence of n a , b a,b a. B. you need maintenance m m m operations:

• yes a a a interval assignment.
• given l , r l,r l. R, for all i ∈ [ l , r ] i\in[l,r] i ∈ [l,r], execute b i ← b i + a i b_i\gets b_i+a_i bi​←bi​+ai​.
• Query interval b b b and.

Solution:

I feel that the whole problem solution is a little unclear, but I don't know how to express it.

Considering the use of segment tree, it is found that the lazy tags of operation one and operation two are not easy to merge, because there will be a case where one operation one is sandwiched between two operation two.

But we can do this: when the operation is carried out, only all the data in the interval represented by the current node a i a_i Update and end recursion only when ai # are the same.

At this time, the lazy mark of operation 2 can become the mark added to the interval: because the interval is empty a i a_i ai ， are the same, so this interval is t t t operation two is equivalent to every operation in this interval b i b_i I ， all plus a i t a_it ai​t.

At this time, you only need to maintain these marks: interval addition a a a interval assignment mark and second operation times mark. Regulations shall be implemented first a a a interval assignment mark, and then execute the operation twice mark, and ensure that when a a a when the interval assignment flag exists, the original value of the current interval a i a_i ai} are the same.

Algebraic understanding is that each position maintains a straight line y = a i x + c y=a_ix+c y=ai ＾ x+c, operation 2 is equivalent to the interval x x x plus one, and for the interval a i a_i ai assignment, if all in the original interval a i a_i ai ， are equal, and you'll find all the straight lines in this interval c c The variation of c is the same. At this time, the three marks correspond to: interval line intercept( c c c) Plus and interval straight line slope( a i a_i ai) assignment, interval x x x plus one.

Considering the time complexity of doing so, the bottleneck lies in the time of traversing the line segment tree.

set up S S S represents a a The number of extremely long equal segments in a sequence specifies that the "segment" here must be represented by a node on the segment tree. Initial time S S S is O ( n ) O(n) O(n) level.

Consider the process of one operation at a time: it will be accessed on the segment tree a a Several consecutive equal segments in a sequence p 1 , ⋯   , p k p_1,\cdots,p_k p1,..., pk, time complexity is O ( k log ⁡ n ) O(k\log n) O(klogn), but after access p 1 , ⋯   , p k p_1,\cdots,p_k p1,..., pk will be merged into at most O ( log ⁡ n ) O(\log n) O(logn) extremely long phase segments, S S S will at least decrease O ( k − log ⁡ n ) O(k-\log n) O(k−logn). But because p 1 p_1 p1 and p k p_k pk ， originally, they are not necessarily extremely long equal segments. In the process of accessing them, the extremely long phase segments they originally belong to will be divided into at most O ( log ⁡ n ) O(\log n) O(logn) is an extremely long phase segment, so S S S will increase at most O ( 2 log ⁡ n ) O(2\log n) O(2logn). So in general, S S S will at least decrease O ( k − log ⁡ n ) O(k-\log n) O(k−logn).

because S S S should always be greater than 0 0 0, so n − ∑ i = 1 m ( k − log ⁡ n ) > 0 n-\sum_{i=1}^m(k-\log n)>0 n − ∑ i=1m (k − logn) > 0, then ∑ i = 1 m k < n + m log ⁡ n \sum_{i=1}^m k<n+m\log n Σ i=1m K < n + mlogn, so the total time complexity is O ( ( n + m log ⁡ n ) log ⁡ n ) = O ( n log ⁡ n + m log ⁡ 2 n ) O((n+m\log n)\log n)=O(n\log n+m\log ^2n) O((n+mlogn)logn)=O(nlogn+mlog2n).

#include<bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define N 100010

using namespace std;

inline int read()
{
	int 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<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

ll ans[N];
int n,Q,a[N];
int top,sta[N];
ll sum[N<<2],suma[N<<2],add[N<<2];
int na[N<<2],tim[N<<2],reset[N<<2];
bool tag[N<<2];

vector<pii>q[N];

void up(int k)
{
	sum[k]=sum[k<<1]+sum[k<<1|1];
	suma[k]=suma[k<<1]+suma[k<<1|1];
	na[k]=na[k<<1];
}

void downa(int k,int nowa,int l,int r)
{
	add[k]+=1ll*tim[k]*na[k],tim[k]=0;
	tag[k]=1,na[k]=reset[k]=nowa,suma[k]=1ll*(r-l+1)*nowa;
}

void downt(int k,int t)
{
	sum[k]+=1ll*suma[k]*t;
	tim[k]+=t;
}

void downn(int k,ll v,int l,int r)
{
	sum[k]+=1ll*(r-l+1)*v;
	add[k]+=v;
}

void down(int k,int l,int r,int mid)
{
	if(tag[k])
	{
		downa(k<<1,reset[k],l,mid);
		downa(k<<1|1,reset[k],mid+1,r);
		tag[k]=0;
	}
	if(tim[k])
	{
		downt(k<<1,tim[k]);
		downt(k<<1|1,tim[k]);
		tim[k]=0;
	}
	if(add[k])
	{
		downn(k<<1,add[k],l,mid);
		downn(k<<1|1,add[k],mid+1,r);
		add[k]=0;
	}
}

void update(int k,int l,int r,int ql,int qr,int nowa)
{
	if(ql<=l&&r<=qr)
	{
		downa(k,nowa,l,r);
		return;
	}
	int mid=(l+r)>>1;
	down(k,l,r,mid);
	if(ql<=mid) update(k<<1,l,mid,ql,qr,nowa);
	if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,nowa);
	up(k);
}

ll query(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return sum[k];
	int mid=(l+r)>>1;
	down(k,l,r,mid);
	ll ans=0;
	if(ql<=mid) ans+=query(k<<1,l,mid,ql,qr);
	if(qr>mid) ans+=query(k<<1|1,mid+1,r,ql,qr);
	return ans;
}

int main()
{
	n=read(),Q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=Q;i++)
	{
		int l=read(),r=read();
		q[r].push_back(mk(l,i));
	}
	for(int i=1;i<=n;i++)
	{
		update(1,1,n,sta[top]+1,i,a[i]);
		while(top&&a[sta[top]]>a[i])
		{
			update(1,1,n,sta[top-1]+1,sta[top],a[i]);
			top--;
		}
		sta[++top]=i;
		downt(1,1);
		for(pii que:q[i])
			ans[que.se]=query(1,1,n,que.fi,i);
	}
	for(int i=1;i<=Q;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

Another very similar example: [XSY3813] missed fish.