题目链接: [yLOI2022] 长安幻世绘
比较不错的综合题。考虑下处理极差的绝对值我们应该怎么做，很显然排序是有必要的，我们需要带着下标排序。
考虑几个核心点：
1.假如没有其他限制考虑极差与序列长度有啥关系，很显然长度越长，极差单调不降，具备单调性。
2.考虑对于一个长度为 \(L\) 的连续序列，我们最多可以取多少个不相邻的数出来？举个例子：
\([1,2,3]\) 最多取两个不相邻的数，\([1,2,3,4]\) 也是两个，很容易知答案为 \(\lceil \frac{x}{2} \rceil =\frac{x+1}{2}\)
基于以上两点我们容易知道，如果跑一个双指针，基于单调性而言，易知道对于一个 \(l\) 它该往左移还是右移使得满足题意，也容易想到如果有一类 DS 去维护这些连续区间，并且根据第二点计算出此时此刻 \([l,r]\) 可以取出的不相邻的最长长度，用于判断双指针的移动。凡是符合题目的满足 \(m\) 长的不相邻序列，根据极差以及已经排好序所以有 \(a_{max}-a_{min}=a_r-a_l\)，那么答案就可以统计了。具体的 DS 可以选择平衡树维护区间，也可以用线段树，为了照顾其他语言，也降低手写平衡树的成本，这里使用线段树维护一段段连续子区间。
算法框架
首先需要把原序列带下标排序，然后跑一个双指针，双指针的移动 check 需要用到线段树统计当前双指针所在的区间的最长不相邻的序列的长度和题目的 \(m\) 的大小关系。具体的线段树维护连续区间，和最大子段和类似，只需要维护前后缀答案和当前区间答案，然后像最大字段和一样分讨 pushUp 即可。
参照代码带注释
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
#define isPbdsFile
#ifdef isPbdsFile
#include <bits/extc++.h>
#else
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>
#endif
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
template <typename T>
int disc(T* a, int n)
{
return unique(a + 1, a + n + 1) - (a + 1);
}
template <typename T>
T lowBit(T x)
{
return x & -x;
}
template <typename T>
T Rand(T l, T r)
{
static mt19937 Rand(time(nullptr));
uniform_int_distribution<T> dis(l, r);
return dis(Rand);
}
template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
return (a % b + b) % b;
}
template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
a %= c;
T1 ans = 1;
for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
return modt(ans, c);
}
template <typename T>
void read(T& x)
{
x = 0;
T sign = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')sign = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
x *= sign;
}
template <typename T, typename... U>
void read(T& x, U&... y)
{
read(x);
read(y...);
}
template <typename T>
void write(T x)
{
if (typeid(x) == typeid(char))return;
if (x < 0)x = -x, putchar('-');
if (x > 9)write(x / 10);
putchar(x % 10 ^ 48);
}
template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
write(x), putchar(c);
write(c, y...);
}
template <typename T11, typename T22, typename T33>
struct T3
{
T11 one;
T22 tow;
T33 three;
bool operator<(const T3 other) const
{
if (one == other.one)
{
if (tow == other.tow)return three < other.three;
return tow < other.tow;
}
return one < other.one;
}
T3() { one = tow = three = 0; }
T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
{
}
};
template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
if (x < y)x = y;
}
template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
if (x > y)x = y;
}
constexpr int N = 1e5 + 10;
int n, m;
pii a[N];
//线段树节点,维护区间[l,r]
struct Node
{
int l, mid, r;
//下标
//前缀最长相连
int pre;
//后缀最长相连
int suf;
//当前区间长度
int len;
//当前区间应该有的最长不相邻个数
int val;
//左右子树
Node *left, *right;
//初始化一下
Node(const int l, const int r) : l(l), r(r)
{
mid = (l + r) >> 1;
len = r - l + 1;
val = pre = suf = 0;
left = right = nullptr;
}
};
//计算一个连续数段的最长不相邻的个数.ceil(x/2）,例如(1,2,3)=>2
int get_ans(const int x)
{
return (x + 1) / 2;
}
//合并区间统计
void push_up(Node* node)
{
//左区间
auto left = node->left;
//右区间
auto right = node->right;
//更新左右前缀
node->pre = left->pre;
node->suf = right->suf;
//前缀充满区间,加上右区间的前缀
if (node->pre == left->len)node->pre += right->pre;
//后缀充满区间,加上左区间的前缀
if (node->suf == right->len)node->suf += left->suf;
//统计间隔子序列
//1.统计中间一段合并后的子序列的间隔段,这一连续的段,由左区间的后缀+右区间的前缀
int mid = get_ans(left->suf + right->pre);
//2.统计除去了这一段的分别两个区间剩余数贡献,只需要统计这分别两段里的贡献去掉"原来的前后缀贡献"的就行
//原来的ans是考虑到了区间完全不连续,拼接以后导致中间原有的一些数不能取了[l,mid],[mid+1,r],拼接以后导致可能mid无法再取贡献
int pre_suf = (left->val - get_ans(left->suf)) + (right->val - get_ans(right->pre));
//累计两个贡献即可
node->val = mid + pre_suf;
}
//动态开点
void push_down(Node* node)
{
if (!node->left)node->left = new Node(node->l, node->mid);
if (!node->right)node->right = new Node(node->mid + 1, node->r);
}
//由于是统计[1,n]之间的区间,我们预先需要build出来空树,所以动态开点也可以换成数组写法,但这样写更清晰
void build(Node* node)
{
if (node->l == node->r)return;
push_down(node);
build(node->left);
build(node->right);
}
//封装一下
struct Seg
{
Node* root;
//初始化一下
Seg()
{
root = new Node(1, n);
build(root);
}
//单点更新,涉及到+1和-1,取出一个数,增加一个数,为了方便,我们可以使用覆盖式更新,而不是+1-1,直接用1/0
static void update(const int x, const int val, Node* node)
{
//长度为1的区间
if (node->l == node->r)
{
node->val = node->pre = node->suf = val;
return;
}
if (x <= node->mid)update(x, val, node->left);
else update(x, val, node->right);
push_up(node);
}
//返回根的值就是目前这个段里面符合的不间隔的数量
int root_ans() const
{
return root->val;
}
};
void solve()
{
int ans = INT_MAX; //答案
cin >> n >> m;
forn(i, 1, n)cin >> a[i].first, a[i].second = i;
auto seg = new Seg();
//按值排序
sort(a + 1, a + 1 + n);
//双指针,表示的是当前这个范围
int l = 1, r = 1;
while (r <= n)
{
//添加一个数下标进去
seg->update(a[r].second, 1, seg->root);
//符合题意就统计,并不断缩小区间,每次最多增加1,所以不可能出现超过的情况,因为相等的时候就开始缩小了
while (seg->root_ans() == m)
{
ans = min(ans, a[r].first - a[l].first);
seg->update(a[l++].second, 0, seg->root);
}
r++;
}
cout << ans << endl;
}
int main()
{
Spider
//------------------------------------------------------
int test = 1;
// cin >> test;
while (test--)solve();
}