大小比较之类从大往小进行+离线+ds： P3722

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135215119

https://www.luogu.com.cn/problem/P3722

看到什么排列，还有一堆大小比较，min/max的限制，考虑从大往小的顺序进行枚举，发现贡献如图：

在这里插入图片描述

离线后拿个ds维护即可。

1
2
3
4
5
pre coding at 21:34
st coding at 21:40
st bugging at 22:05
passing at 22:30
fn blogging at 10:12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
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^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 200010
//#define M
//#define mo
struct Pail {
	int x, id; 
}p[N];
struct node {
	int l, r, id; 
}b[N];
int n, m, i, j, k, T, p1, p2, q;
int L[N], R[N], ans[N]; 
vector<int>V[N]; 
vector<pair<int, int> >G[N]; 

struct Segment_tree {
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define mid ((l+r)>>1)
	int tag[N<<2], s[N<<2]; 
	void clear() {
		memset(s, 0, sizeof(s)); 
		memset(tag, 0, sizeof(tag)); 
	}
	void push_down(int k, int l, int r) {
		tag[ls]+=tag[k]; s[ls]+=(mid-l+1)*tag[k]; 
		tag[rs]+=tag[k]; s[rs]+=(r-mid)*tag[k]; 
		tag[k]=0; 
	}
	void push_up(int k) {
		s[k] = s[ls] + s[rs]; 
	}
	void add(int k, int l, int r, int x, int y, int z) {
		if(l>=x && r<=y) return tag[k]+=z, s[k]+=(r-l+1)*z, void(); 
		push_down(k, l, r); 
		if(x <= mid) add(ls, l, mid, x, y, z); 
		if(y >= mid+1) add(rs, mid+1, r, x, y, z); 
		push_up(k); 
//		debug("JIA : %lld [%lld %lld] %lld\n", k, l, r, s[k]); 
	}
	int que(int k, int l, int r, int x, int y) {
		if(l>=x && r<=y) return s[k]; 
		int sum = 0; 
//		debug("%lld [%lld %lld] %lld => %lld\n", k, l, r, s[k], sum); 
		push_down(k, l, r); 
		if(x <= mid) sum += que(ls, l, mid, x, y); 
		if(y >= mid+1) sum += que(rs, mid+1, r, x, y); 
		return sum; 
	}
	#undef ls
	#undef rs
	#undef mid
}Seg1, Seg;

void work(){
	Seg.clear(); 
	sort(b+1, b+q+1, [] (node x, node y) { return x.r < y.r; }); 
	for(i=1; i<=n; ++i) G[i].clear(); 
	for(i=1; i<=n; ++i) 
		if(R[i]!=n+1 &&  L[i]+1 < i) {
			debug("[%lld %lld] => [%lld]\n", L[i]+1, i-1, R[i]); 
			G[R[i]].pb({L[i]+1, i-1}); 
		
		}
	for(i=1, j=1; i<=q; ++i) {
		while(j <= b[i].r) {
			for(auto t : G[j]) Seg.add(1, 1, n, t.fi, t.se, p2); 
			++j; 
		}
		ans[b[i].id]+=Seg.que(1, 1, n, b[i].l, b[i].r); 
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); p1=read(); p2=read(); 
	for(i=1; i<=n; ++i) p[i].x=read(), p[i].id=i; 
	set<int>s; s.insert(0); s.insert(n+1); 
	sort(p+1, p+n+1, [] (Pail A, Pail B) { return A.x > B.x; }); 
	for(i=1; i<=n; ++i) {
		j = p[i].id; 
		auto it1 = s.lower_bound(j), it2 = it1; --it1; 
		L[j]=(*it1); R[j]=(*it2); s.insert(j); 
		if(L[j]!=0 && R[j]!=n+1) V[R[j]].pb(L[j]); 
	}
	for(i=1; i<=n; ++i) debug("[%lld %lld]\n", L[i], R[i]); 
	for(i=1; i<=q; ++i) b[i].l=read(), b[i].r=read(), b[i].id=i, ans[i]+=(b[i].r-b[i].l)*p1; //, ans[i]=p1*(b[i].r-b[i].l+1)*(b[i].r-b[i].l)/2; 
	sort(b+1, b+q+1, [] (node x, node y) { return x.r < y.r; }); 
	for(i=1, j=1; i<=q; ++i) {
		while(j <= b[i].r) {
			for(auto t : V[j]) Seg1.add(1, 1, n, t, t, p1);//, debug("Add: %lld %lld\n", t, j); 
			++j; 
		}
		ans[b[i].id]+=Seg1.que(1, 1, n, b[i].l, b[i].r); 
	}
	for(i=1; i<=q; ++i) debug("%lld ", ans[i]); debug("\n"); 
	work(); 
	for(i=1; i<=q; ++i) debug("%lld ", ans[i]); debug("\n"); 
	for(i=1; i<=n; ++i) L[i]=n-L[i]+1, R[i]=n-R[i]+1, swap(L[i], R[i]); 
	reverse(L+1, L+n+1); 
	reverse(R+1, R+n+1); 
	for(i=1; i<=q; ++i) b[i].l=n-b[i].l+1, b[i].r=n-b[i].r+1, swap(b[i].l, b[i].r); 
	work(); 
	for(i=1; i<=q; ++i) printf("%lld\n", ans[i]); 
	return 0;
}