约束条件转保序回归问题——之间用贪心+单调栈维护：P7294 / 1218T3

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

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

http://47.92.197.167:5283/contest/439/problem/3

发现行很大，那肯定是一列列枚举。

考虑单个询问 (x,y)(x,y) ，假设第 ii 列向第 i+1i+1 列的转折点是 pip_i ，则对应的贡献 ∑((pi−pi−1)×ci+pi2[i<y])\sum ((p_i-p_{i-1})\times c_i+p_i^2[i<y]) ，其中 p0=1p_0=1 。

一坨东西很难看，直接拆开算出每个 pip_i 的贡献为 pi2−ci+1−ci2pip_i^2-\dfrac{c_{i+1}-c_i}2p_i ，甚至可以推广到从第 ii 列一口气走到第 jj 列的最优决策点 pp （我们对相同的 pp 进行合并以方便处理问题），满足 min⁡((i−j)p2−cj−cij−ip)\min((i-j)p^2-\dfrac{c_j-c_i}{j-i}p) 。根据初中知识可得 min⁡((p−cj−ci2(j−i))2)\min((p-\dfrac{c_j-c_i}{2(j-i)})^2) 。

我们要求的是 min⁡∑(p−cj−ci2(j−i))2\min\sum(p-\dfrac{c_j-c_i}{2(j-i)})^2 ，满足 pp 递增。这是一个保序回归问题，参见IOI2018国家集训队论文。我们只需要贪心令 p=cj−ci2(j−i)p=\dfrac{c_j-c_i}{2(j-i)} （四舍五入），然后拿单调栈维护即可。（证明我还小，还没）

考虑 xx 的性质。我们在栈上二分出最后一个满足决策点 ≤p\le p 的区间，最后先往下后往右走即可。

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
#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
//#define M
//#define mo
#define N 2000010
struct node {
	int l, r, p; 
}z[N];
int n, m, i, j, k, T;
int top, ans[N], c[N], s[N], w[N], l, r, p1, p2, x, y, mid; 
int q, lstr; 
struct edge { int x, id; };
vector<edge>G[N]; 

namespace Kit {
	int div(int a, int b) {
		return (a + b) / (2 * b); 
	}
	int Point(int i, int j) {
		return min(max(div(c[j] - c[i], j - i), 1ll), n); 
	}
	void print() {
		for(int i=1; i<=top; ++i) 
			debug("[%d %d] %d ", z[i].l, z[i].r, z[i].p); 
		debug("\n"); 
	}
}

signed main()
{
	freopen("chess.in", "r", stdin);
	freopen("chess.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=m; ++i) c[i]=read(); 
	for(i=1; i<=m; ++i) w[i]=w[i-1]+Z(i); 
	q=read(); 
	for(i=1; i<=q; ++i) {
		x=read(); y=read(); 
		if(y!=1) G[y].pb({x, i}); 
		else ans[i] = c[1] * (x - 1); 
	}
	z[top=1]={1, 1, 1}; 
	for(i=2; i<=m; ++i) {
//		debug(">> %d\n", Kit::Point(z[top].r, i)); 
		while(z[top].p > Kit::Point(z[top].r, i)) --top; 
		lstr = z[top].r;  
		z[++top] = {lstr, i, Kit::Point(lstr, i)}; 
		p1 = z[top-1].p; p2 = z[top].p; 
		x = z[top].l; y = z[top].r; 
		s[top] = s[top-1] + (p2 - p1) * c[x] + Z(p2) * (i - lstr); 
//		debug("---------- %d : (lstr)%d\n", i, lstr); Kit :: print(); 
		for(auto t : G[i]) {
			l=1; r=top; 
			while(l < r) {
				mid = (l + r + 1) >> 1; 
				if(z[mid].p <= t.x) l = mid; 
				else r = mid - 1; 
			}
			x = z[l].l; y = z[l].r; 
//			debug("To (%d %d) use %d | (s)%d\n", t.x, i, l, s[l]); 
			ans[t.id] = s[l] + (t.x - z[l].p) * c[y] + Z(t.x) * (i - y); 
		}
	}
	for(i=1; i<=q; ++i) printf("%lld\n", ans[i]); 	
	return 0;
}