[决策单调性] 交与并
_Cheems
·
·
个人记录
小成从 bzoj 搬来的，题意：对于一个区间集合{A1,A2,⋯,AK}(K>1,∀i≠j,Ai≠Aj)，我们定义其权值W=|A1∪A2∪\dots∪AK|*|A1∩A2∩\dots∩AK| 当然，如果这些区间没有交集则权值为 0。
首先按 l 排 并去重，容易发现新的数组上，选取的集合必然是连续一段区间，否则交集为 0 没有意义。
假如选择 a_x,a_{x+1}\dots a_y，那么价值为 w(x,y)=(r_y-l_x)(r_x-l_y)。
考虑决策点 $p<x$，必然满足 $l_p< l_x< l_y$，那么：
$w(x,y)=r_xr_y-l_yr_y-l_xr_x+l_xl_y$。
$w(p,y)=r_p r_y-l_yr_y-l_pr_p+l_pl_y$。
当 $y$ 增长，设其相比于 $l_y$ 增长 $\Delta l$，同理有 $\Delta r$，那么欲证 $w_x$ 的变化量更大：
$$\Delta w_x\ge \Delta w_p$$
$$r_x\Delta r+l_x\Delta l\ge r_p\Delta r+l_p\Delta l$$
注意，$l_yr_y$ 这一项只与 $y$ 有关，比较时舍去即可。
$$\Delta r(r_x-r_p)\ge \Delta l(l_p-l_x)$$
$$\frac {\Delta r} {\Delta l}\ge \frac {l_p-l_x}{r_x-r_p}$$
显然，$\Delta r,\Delta l> 0$，$l_p<l_x,r_p<r_x$。
所以 $\frac {\Delta r}{\Delta l} >0$，$\frac {l_p-l_x}{r_x-r_p} <0$。
所以不等式成立，证毕。
最后有个坑点，要计算被包含的区间，显然只涉及两个区间，我们可以在去重时计算：
1. 对于极大区间：维护单调栈，满足栈底到栈顶，区间左端点递增、大小递减，每有一段极大区间，就比较栈顶是否小于它，满足则栈顶一定劣于当前区间。
2. 对于小区间：考虑单调栈内覆盖它的区间，显然，栈顶到栈底右端点递减，覆盖它的区间集合必然是栈顶往下连续一段的，二分出最下面的满足条件的区间即可
（貌似可以不二分，从栈底开始检查是否覆盖，若不满足就直接退掉。因为让它再覆盖后面的更小区间，一定不优？不太清楚。）
总复杂度 $O(n\log n)$。
#### 代码
后话：百万搬来的数据出锅了，不太清楚代码写的有无瑕疵，但思路应该没错。
```cpp
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define int long long
const int N = 1e6 + 5, py = 1e8;
int n, _n, ans, opt;
int q[N], l, r;
struct node{int l, r;} a[N], b[N];
inline bool cmp(node A, node B) {return A.l == B.l ? A.r > B.r : A.l < B.l;}
inline int W(int x, int y) {return (b[y].r - b[x].l) * (b[x].r - b[y].l);}
inline void calc(int l, int r, int kl, int kr){
if(l > r || kl > kr) return ;
int mid = ((l + r) >> 1), p = kl;
for(int i = kl; i < min(mid, kr); ++i) if(W(i, mid) >= W(p, mid)) p = i;
if(p < mid) ans = max(ans, W(p, mid));
calc(l, mid - 1, kl, p), calc(mid + 1, r, p, kr);
}
inline int read() {int x = 0, w = 0; char ch = 0; while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();} while (isdigit(ch)) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();} return w ? -x : x;}
inline int erf(int p){
int L = l - 1, R = r, mid;
while(L + 1 < R){
mid = ((L + R) >> 1);
if(a[q[mid]].r >= p) R = mid;
else L = mid;
}
return R;
}
signed main(){
cin >> n;
for(int i = 1; i <= n; ++i) a[i].l = read(), a[i].r = read();
sort(a + 1, a + 1 + n, cmp);
l = 1, r = 0;
for(int i = 1; i <= n; ++i){
if(a[i].r > b[_n].r){
while(l <= r && a[q[r]].r - a[q[r]].l <= a[i].r - a[i].l) --r;
q[++r] = i;
b[++_n] = a[i];
}
else if(l <= r){
int pos = erf(a[i].r);
if(a[q[pos]].r >= a[i].r) ans = max(ans, (a[q[pos]].r - a[q[pos]].l) * (a[i].r - a[i].l));
}
}
n = _n;
calc(1, n, 1, n);
cout << ans;
return 0;
}
```