Title Link

Meaning:
You have a length of n n The arrangement of n for a pair of subscripts i , j ( i < j ) i,j(i<j) i. J (I < J), if there is no ratio between them a i a_i ai} and a j a_j aj large number, then the contribution is p 1 p_1 p1, if there is a position k k k. Satisfied a i < a k < a j a_i<a_k<a_j ai < AK < AJ or a j < a k < a i a_j<a_k<a_i aj < AK < AI, the contribution is p 2 p_2 p2, no contribution from other situations. have m m m times of inquiry, each inquiry will give you an interval [ l , r ] [l,r] [l,r], ask you all subscript tuples in the interval i , j ( l < = i < j < = r ) i,j(l<=i<j<=r) i. The sum of the contributions of J (L < = I < J < = R).
n , m < = 2 e 5 n,m<=2e5 n. M < = 2e5, ensure that the answer does not explode long long

Solution:
I heard about this problem in high school. It was recommended, but I didn't do it at that time. Then when I went to do it now, I turned to the immortal's blog and found that I didn't do the same problem as him, QAQ

Let's talk about my practice first.
For this interval query, first consider the direct maintenance of the segment tree to see what information needs to be maintained to merge and maintain the answer. We found that if we want to merge answers, it seems that we need to maintain two monotone stacks for each interval, namely, the stack starting from the left and the stack starting from the right. Each interval merging, we need to merge the monotone stacks. Then we can know that this interval information cannot be maintained and merged directly.

A common idea for this interval query is to take all queries offline, and then answer all queries with this location as the right endpoint for each location. In this way, we update the answer and answer the query while enumerating the right endpoint from left to right.

First, consider the first type of contribution. For the current right endpoint, it is used as the j j j, all feasible i i i satisfied i , j i,j i. There is no greater number between J. For this thing, we maintain a monotonic stack. The closer to the top of the stack, the greater the subscript and the smaller the value. So when we add a number, all the pop-up positions of the play stack meet the requirements. If the play stack is not empty, the top of the stack also meets the requirements. For the information of an interval, we can use the segment tree to maintain it. Each time we find the matching position, we can add it at a single point. For the query, we can directly sum the interval. Because we answer the query in the order of the right endpoint, we can correctly maintain it without subtracting the prefix of the chairman tree.

Again, the second kind of contribution. This is more troublesome than the first category. We can still find that this is related to the elements in the monotone stack. Each time an element is added, if the current element can bounce the stack, the position between the first element on the top of the stack and the second element on the top of the stack is taken as the left endpoint, and the current position is taken as the right endpoint, which must be feasible. However, this only considers that the current position is the larger of the two endpoints. In fact, it's not difficult to do the smaller ones. We just need to do it again from the back to the front. When doing it, we sort the queries according to the left endpoint from large to small.

In this way, my practice is introduced.

Again, fairy y_immortal's approach. I'm not sure if his approach is exactly the same as what I said below, but the general idea should be the same.

His approach should be to use the monotone stack to sweep forward and backward twice, and calculate the previous and later positions larger than it for each position. For the first case, all legal intervals are the intervals formed by the previous and later positions larger than it corresponding to each position. For the second case, the number larger than it in front is used as the left endpoint, and it is legal to use the next position to the previous position larger than it as the right endpoint; The first position larger than it behind it is the right endpoint, and the next position larger than it in front is the legal left endpoint to its previous position. In other words, as the maximum value in that interval, we enumerated the maximum value of the interval, but we didn't do exactly that. Instead, we enumerated the maximum value of each position to see which is the corresponding left and right endpoints. But I didn't think about how to calculate it in detail, but I may have to sweep it both positively and negatively during the calculation.

code:

#include <bits/stdc++.h>
using namespace std;

int n,m,a[200010],sta[200010],tp,id[200010];
long long p1,p2;
struct node
{
	int l,r,id;
	long long ans;
}q[200010];
struct tree
{
	int l,r,tag2;
	long long num1,num2;
}tr[800010];
inline int cmp(node x,node y)
{
	return x.r<y.r;
} 
inline int cmp2(node x,node y)
{
	return x.l>y.l;
}
inline int cmp3(node x,node y)
{
	return x.id<y.id;
}
inline void build(int rt,int l,int r)
{
	tr[rt].l=l;
	tr[rt].r=r;
	tr[rt].num1=0;
	tr[rt].num2=0;
	tr[rt].tag2=0;
	if(l==r)
	return;
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}
inline void update(int rt,int x)
{
	int l=tr[rt].l,r=tr[rt].r;
	if(l==r)
	{
		tr[rt].num1++;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	update(rt<<1,x);
	else
	update(rt<<1|1,x);
	tr[rt].num1++;
}
inline void pushdown(int rt)
{
	if(tr[rt].tag2)
	{
		tr[rt<<1].tag2+=tr[rt].tag2;
		tr[rt<<1].num2+=tr[rt].tag2*(tr[rt<<1].r-tr[rt<<1].l+1);
		tr[rt<<1|1].tag2+=tr[rt].tag2;
		tr[rt<<1|1].num2+=tr[rt].tag2*(tr[rt<<1|1].r-tr[rt<<1|1].l+1);
		tr[rt].tag2=0;
	}
}
inline void update2(int rt,int le,int ri)
{
	int l=tr[rt].l,r=tr[rt].r;
	if(le<=l&&r<=ri)
	{
		tr[rt].tag2++;
		tr[rt].num2+=r-l+1;
		return;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(le<=mid)
	update2(rt<<1,le,ri);
	if(mid+1<=ri)
	update2(rt<<1|1,le,ri);
	tr[rt].num2=tr[rt<<1].num2+tr[rt<<1|1].num2;
}
inline long long query(int rt,int le,int ri)
{
	int l=tr[rt].l,r=tr[rt].r;
	if(le<=l&&r<=ri)
	return tr[rt].num1;
	int mid=(l+r)>>1;
	long long res=0;
	if(le<=mid)
	res+=query(rt<<1,le,ri);
	if(mid+1<=ri)
	res+=query(rt<<1|1,le,ri);
	return res;
}
inline long long query2(int rt,int le,int ri)
{
	int l=tr[rt].l,r=tr[rt].r;
	if(le<=l&&r<=ri)
	return tr[rt].num2;
	pushdown(rt);
	int mid=(l+r)>>1;
	long long res=0;
	if(le<=mid)
	res+=query2(rt<<1,le,ri);
	if(mid+1<=ri)
	res+=query2(rt<<1|1,le,ri);
	return res;
}
int main()
{
	scanf("%d%d%lld%lld",&n,&m,&p1,&p2);
	for(int i=1;i<=n;++i)
	scanf("%d",&a[i]);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	build(1,1,n);
	int cur=1;
	sta[0]=2e9;
	id[0]=0;
	for(int i=1;i<=n;++i)
	{
		while(a[i]>sta[tp])
		{
			update(1,id[tp]);
			if(id[tp-1]+1<=id[tp]-1)
			update2(1,id[tp-1]+1,id[tp]-1);		
			--tp;
		}
		if(tp!=0)
		update(1,id[tp]);
		sta[++tp]=a[i];
		id[tp]=i;
		while(q[cur].r<=i&&cur<=m)
		{
			q[cur].ans+=query(1,q[cur].l,q[cur].r)*p1;
			q[cur].ans+=query2(1,q[cur].l,q[cur].r)*p2;	
			++cur;
		}
	}
	build(1,1,n);
	tp=0;
	id[0]=n+1;
	sort(q+1,q+m+1,cmp2);
	cur=1;
	for(int i=n;i>=1;--i)
	{
		while(a[i]>sta[tp])
		{
			if(id[tp-1]-1>=id[tp]+1)
			update2(1,id[tp]+1,id[tp-1]-1);
			--tp;
		}
		sta[++tp]=a[i];
		id[tp]=i;
		while(q[cur].l>=i&&cur<=m)
		{
			q[cur].ans+=query2(1,q[cur].l,q[cur].r)*p2;
			++cur;
		}
	}
	sort(q+1,q+m+1,cmp3);
	for(int i=1;i<=m;++i)
	printf("%lld\n",q[i].ans);
	return 0;
}