[ABC248Ex] Beautiful Subsequences Solution
目录更好的阅读体验戳此进入
题面
给定排列 $ P_n $ 和整数 $ k $，求满足如下条件的点对 $ (l, r) $ 数量。
- $ 1 \le l \le r \le n $。
- $ \max_{i = l}^rP_i - \min_{i = l}^rP_i \le r - l + k $。
Solution
首先为了方便我们令 $ mx = \max_{i = l}^rP_i, mn = \min_{i = l}^rP_i $，原式转化为 $ mx - mn \le r - l + k $，发现 $ k \in [0, 3] $，所以可以考虑将不等式转化为等式，枚举 $ k $，对于每个 $ k $，合法方案满足 $ mx - mn = r - l + k $。于是原式可以转化为对于每个 $ r \in [1, n] $，求满足 $ l \in [1, r], k \in [0, K], l + mx - mn = r + k $ 的个数，此时 $ l, r, k $ 均为固定的，所以我们只需要求出此时的区间 $ \max, \min $，即可确定是否合法。换句话说，对于枚举的 $ r $，要找其左侧所有点的 $ l + mx - mn $ 的值与 $ r + k $ 相等的个数。
于是到此问题可转化为，求区间最大值最小值，然后再求区间等于 $ r $ 的数量。对于求区间最大值最小值，这个东西我们发现求的是对于每个 $ r $ 的所有后缀最大最小值，这个东西用单调栈维护即可。具体地，对于一个新的值，显然其只有可能更新它前面的点的最值，其自己在第一次插入的时候后缀的区间为 $ [i, i] $，最值显然均为 $ a_i $，但是这个时候我们却不需要更新最值，因为我们要的值是 $ mx - mn $，既然最值相同那么这个东西为 $ 0 $，所以可以忽略。然后对于一个新的值，要去尝试更新前面值的最值，如对于最大值需要维护单调递减的栈，即栈顶最小，如果新的值更小直接丢到栈上，否则更新栈顶和次栈顶之间区间的最大值。把这些维护完之后直接求所有值为 $ r $ 的点即可。
然后考虑如何维护区间等于 $ r + k $ 的个数，有一个比较好想的就是维护一棵线段树，对于每个节点都维护一个 basic_string < pair < int, int > >，存储对应值有多少个，合并的时候直接把两个加起来即可，然后去个重。同时此时查询的时候可以不用枚举 $ k $，直接找 $ r + k $ 大于等于对应值即可。以此我们便可很直观地写出如下实现，但是这个是错误的。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MAXN (150000)
template< typename T = int >
inline T read(void);
int N, K;
int val[MAXN];
struct MyPair{
int first, second;
friend const bool operator < (const MyPair &a, const MyPair &b){
return a.first == b.first ? a.second < b.second : a.first < b.first;
}
};
struct Node{
basic_string < MyPair/*val, cnt*/ > vals;
int lz;
Node operator = (const Node &b){
this->vals = b.vals;
this->lz = b.lz;
return *this;
}
friend const Node operator + (const Node &a, const Node &b){
Node ret{a.vals + b.vals, 0};
sort(ret.vals.begin(), ret.vals.end());
for(auto it = ret.vals.begin(); next(it) != ret.vals.end();)
if(it->first == next(it)->first)next(it)->second += it->second, it = ret.vals.erase(it);
else advance(it, 1);
return ret;
}
friend Node operator += (Node &a, const int &val){
for(auto &nod : a.vals)nod.first += val;
a.lz += val;
return a;
}
};
class SegTree{
private:
Node tr[MAXN << 2];
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)
public:
void Pushup(int p){tr[p] = tr[LS] + tr[RS];}
void Pushdown(int p){
if(!tr[p].lz)return;
tr[LS].lz = tr[RS].lz = tr[p].lz;
tr[LS] += tr[p].lz, tr[RS] += tr[p].lz;
tr[p].lz = 0;
}
void Build(int p = 1, int gl = 1, int gr = N){
if(gl == gr)return tr[p].vals += {gl = gr, 1}, void();
Build(LS, gl, MID), Build(RS, MID + 1, gr);
Pushup(p);
}
void Modify(int l, int r, int val, int p = 1, int gl = 1, int gr = N){
if(l <= gl && gr <= r)return tr[p] += val, void();
Pushdown(p);
if(l <= MID)Modify(l, r, val, LS, gl, MID);
if(r >= MID + 1)Modify(l, r, val, RS, MID + 1, gr);
Pushup(p);
}
Node Query(int l, int r, int p = 1, int gl = 1, int gr = N){
if(l <= gl && gr <= r)return tr[p];
Pushdown(p);
if(l > MID)return Query(l, r, RS, MID + 1, gr);
if(r < MID + 1)return Query(l, r, LS, gl, MID);
return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
}
}st;
ll Cal(int R){
ll ret(0);
auto vals = st.Query(1, R).vals;
//r + k >= l + max - min
for(auto nod : vals)if(R + K >= nod.first)ret += nod.second;
return ret;
}
int mx[MAXN]/*Query Min*/, mn[MAXN]/*Query Max*/;
int mxp(0), mnp(0);
int main(){
N = read(), K = read();
for(int i = 1; i <= N; ++i)val[i] = read();
st.Build();
ll ans(0);
for(int R = 1; R <= N; ++R){
while(mxp && val[R] > val[mx[mxp]])st.Modify(mx[mxp - 1] + 1, mx[mxp], val[R] - val[mx[mxp]]), --mxp;
while(mnp && val[R] < val[mn[mnp]])st.Modify(mn[mnp - 1] + 1, mn[mnp], val[mn[mnp]] - val[R]), --mnp;
mx[++mxp] = mn[++mnp] = R;
ans += Cal(R);
// printf("R = %d, Cal = %lld\n", R, Cal(R));
}printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
不过这个东西我们简单分析以下复杂度就会发现，每次合并和修改之后的 Pushup 都会使其重构然后耗费大量时间，所以最后复杂度是 $ O(\texttt{玄学}) $ 的，提交后就会发现 AT 上只能过十多个点。。感觉复杂度直接退化到暴力了。
然后对于 basic_string < pair < int, int > > 还有个很严重的问题，对于一般的 C++14 及以下都不会有任何问题，但是在 C++17 之后，因为 basic_string.h 中有如下语段：
#if __cplusplus >= 201703L
# include <string_view>
#endif
然而引入的这个头文件中还存在如下语句：
static_assert(is_trivial_v<_CharT> && is_standard_layout_v<_CharT>);
此时我们发现，这东西会 CE！测试后发现如下语段会输出 $ 0 $：
cout << is_trivial < pair< int, int > >::value << endl;
众所周知 is_trivial 一般就是用于判断类型的构造函数是否为默认构造函数，而 pair 的构造函数似乎是用初始化列表写的，可能是因为这个原因，就会导致其无法通过这个 assert，于是就寄了。然而 AT 上默认的不知道是 C++17 还是 20 或者更高，所以无法过编。这个或许可以通过一些高妙的方式解决，但是我不会，于是考虑自定义一个结构体实现跟 pair 一样但是使用默认构造函数即可。
所以话说回来，这个做法本身就是错误的，于是现在我们考虑正解：
思考什么东西比较好维护区间最值和区间等于 $ x $ 的数量，不难想到分块，维护的方式和上面说的差不多，只是用分块替换线段树即可，这个东西的复杂度就是 $ O(k n \sqrt{n}) $，可以通过，似乎也是官方正解，但是我不太喜欢分块这个复杂度不够优秀，所以这里就不给代码实现了，我们考虑一些更优秀的做法。
考虑分治，思路来自机房大佬 @sssmzy，发现对于每一个区间，如果我们令 $ l \in [L, mid], r \in [mid + 1, R] $ 是可以快速维护答案的，于是我们只需要以此为基础，计算完答案后分别二分下去即可。
具体地，对于维护答案的过程，我们发现最大值和最小值的位置无法确定，所以考虑枚举最大值在左侧或右侧，以左侧为例子，我们按照类似猫树的思想，从 $ mid $ 向两侧维护后/前缀最值，不难想到，以前缀最大值为例，显然扩展时最大值是单调不降的，最小值同理，然而我们需要让最大值取在左侧，那么显然存在一个分割点 $ sp1 $，在其左的右侧点是合法的，同时也存在一个分割点 $ sp2 $，满足在其左的点最小值取左侧，其右的取右侧，然后发现这个东西是单调的，所以可以直接双（三）指针，枚举 $ l $，考虑 $ sp1, sp2 $，同时维护桶记录所有可能的合法的值的数量。然后讨论 $ r $ 位置与分割点的关系，如果在 $ [mid + 1, \min(sp1, sp2)] $ 那么显然此时最大最小值都在左侧，也就是此时确定 $ k $ 之后直接就有 $ r = l + mx - mn - k $，判断 $ \texttt{RHS} $ 是否在范围内即可。否则在 $ (sp1, sp2] $ 之间的话，最大值在左侧和 $ l $ 相关，最小值在右侧和 $ r $ 相关，此时有 $ r - mn = l + mx - k $，同样将对应 $ \texttt{RHS} $ 的桶加上即可。然后再考虑 $ mx $ 再右侧同理算一遍即可，注意此时因为索引可能为负，所以需要加个 $ n $ 转正。
当前区间算完之后二分下去分别求解即可，这样最终复杂度 $ O(k n \log n) $，跑得飞快。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MAXN (150000)
template < typename T = int >
inline T read(void);
int N, K;
int a[MAXN];
ll ans(0);
int mx[MAXN], mn[MAXN];
int buc[MAXN << 1];
void Divide(int gl = 1, int gr = N){
if(gl == gr)return ++ans, void();
int MID = (gl + gr) >> 1;
mx[MID] = mn[MID] = a[MID], mx[MID + 1] = mn[MID + 1] = a[MID + 1];
for(int i = MID - 1; i >= gl; --i)mx[i] = max(mx[i + 1], a[i]), mn[i] = min(mn[i + 1], a[i]);
for(int i = MID + 2; i <= gr; ++i)mx[i] = max(mx[i - 1], a[i]), mn[i] = min(mn[i - 1], a[i]);
int sp1(MID), sp2(MID);
for(int l = MID; l >= gl; --l){
while(sp1 + 1 <= gr && mx[sp1 + 1] <= mx[l])++sp1, buc[sp1 + mn[sp1]]++;
while(sp2 + 1 <= gr && mn[sp2 + 1] >= mn[l])++sp2, buc[sp2 + mn[sp2]]--;
for(int k = 0; k <= K; ++k){
int r = l + mx[l] - mn[l] - k;
int idx = l + mx[l] - k;
if(MID + 1 <= r && r <= min(sp1, sp2))++ans;
if(sp2 < sp1 && idx > 0)ans += buc[idx];
}
}for(int i = MID + 1; i <= gr; ++i)buc[i + mn[i]] = 0;
sp1 = MID + 1, sp2 = MID + 1;
for(int r = MID + 1; r <= gr; ++r){
while(sp1 - 1 >= gl && mx[sp1 - 1] <= mx[r])--sp1, buc[sp1 - mn[sp1] + N]++;
while(sp2 - 1 >= gl && mn[sp2 - 1] >= mn[r])--sp2, buc[sp2 - mn[sp2] + N]--;
for(int k = 0; k <= K; ++k){
int l = r - mx[r] + mn[r] + k;
int idx = r - mx[r] + k + N;
if(max(sp1, sp2) <= l && l <= MID)++ans;
if(sp1 < sp2 && idx > 0)ans += buc[idx];
}
}for(int i = gl; i <= MID; ++i)buc[i - mn[i] + N] = 0;
Divide(gl, MID), Divide(MID + 1, gr);
}
int main(){
N = read(), K = read();
for(int i = 1; i <= N; ++i)a[i] = read();
Divide();
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2022_11_22 初稿
标签：Beautiful,return,int,题解,mn,MID,ret,Subsequences,mx From： https://www.cnblogs.com/tsawke/p/16945795.html