题意大概是这样，「每次操作选出区间中的一个 LIS（strictly），满足其开端是极靠近左端点且大于 的位置，答案即这个 LIS 的末尾，做一个轮换后弹出序列末端」。
首先做几个观察。
Observation 1：每次被弹出的都是区间最大值。
证明：显然，你考虑有一个最大的值在钦定的 LIS 的前或后，都会被先行选择 / 扩展进来。
Observation 2（key observation）：如果对一个区间插入若干个值，插入顺序不影响最终序列的长相。
证明：每次插入进去的值不可能成为序列的最大值，所以弹出的数固定。并且插入进的数是根据严格偏序关系插进去的，所以顺序不影响长相。
仅凭以上两个观察，此题的奇怪操作怎么看也不像是个 ，选择对序列做 Sqrt Decomposition，接下来我们探讨整块间的处理方式和散块的做法，因为操作的特殊性我们并不需要做 8 种情况的伞兵讨论。
- 整块间：你考虑每个整块上维护一个大根堆，然后整块的后继继承该整块的最大值，该整块去除其最大值即可；
- 散块：把所有需要插入的元素存一个懒标在右边散块放出来，因为 Observation 2，我们贪心优先把值较小的懒标放出去即可。
#include <bits/stdc++.h>
template <class T> inline void chmax(T& a, const T b) { a = a > b ? a : b; }
template <class T> inline void chmin(T& a, const T b) { a = a < b ? a : b; }
inline long long rd() {
long long x = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch & 15), ch = getchar();
return f ? -x : x;
}
/** @brief
* 选出一个 LIS，满足开始是极靠近 l 的大于 A 的位置，答案即序列的末端，然后用 A 替换序列开头，做一个轮换，弹出序列末端
* Observation 1：每次被弹出的都是区间最大值
* Trick：序列分块
* Section 1：整块
* 整块上维护一个堆，整块间下一块继承上一块的最大值
* Section 2：散块
* 维护一个小根堆，每次散块暴力重构
* key observation：插入顺序不影响序列的长相
*/
constexpr int BS = 650;
int n, m, a[400100], pos[400100];
int L[660], R[660];
std::priority_queue<int> max[660];
std::priority_queue<int, std::vector<int>, std::greater<int>> tag[660];
void push(int i, int x) { max[i].emplace(x); }
void setBound(int i) { L[i] = (i - 1) * BS + 1, R[i] = i * BS; }
int Qry(int i, int l, int r, int x) {
if (tag[i].size()) {
for (int j = L[i]; j <= R[i]; ++j)
if (int t = a[j]; tag[i].top() < t)
a[j] = tag[i].top(), tag[i].pop(), tag[i].emplace(t);
}
while (max[i].size()) max[i].pop();
while (tag[i].size()) tag[i].pop();
for (int j = l; j <= r; ++j)
if (a[j] > x) std::swap(a[j], x);
for (int f = L[i]; f <= R[i]; ++f) push(pos[L[i]], a[f]);
return x;
}
int Mdf(int i, int x) {
if (x >= max[i].top()) return x;
int res = max[i].top(); max[i].pop();
max[i].emplace(x), tag[i].emplace(x);
return res;
}
signed main() {
n = rd(), m = rd();
for (int i = 1; i <= n; ++i)
push(pos[i] = (i - 1) / BS + 1, a[i] = rd());
for (int i = 1; i <= pos[n]; ++i) setBound(i);
R[pos[n]] = n;
for (int l, r, a; m--;) {
l = rd(), r = rd(), a = rd();
if (pos[l] == pos[r] && l <= r) printf("%d\n", Qry(pos[l], l, r, a));
else {
a = Qry(pos[l], l, R[pos[l]], a);
for (int u = pos[l] + 1 > pos[n] ? 1 : pos[l] + 1; u != pos[r]; u = u + 1 > pos[n] ? 1 : u + 1)
a = Mdf(u, a);
printf("%d\n", Qry(pos[r], L[pos[r]], r, a));
}
}
return 0;
}