自己的套路还是见少了。
思路
考虑扫描线。
每一个颜色的 \(\min\) 具有单调性，这个很好看出来。
可以使用一个单调栈来维护。
这里都是朴素的。
考虑如何维护。
我们发现在通过单调栈维护的时候。
需要支持撤销上一个元素对区间的影响。
我就在这里卡了很久。
我们有一个很暴力的想法。
我们每一次区间取 \(\max\) 时，我们将这个元素留下来，直接存着。
然后在撤销影响的时候就可以删掉这个点。
发现可以线段树做。
每个点维护一个可删堆。
使用标记永久化的思想。
这样每一次插入时只会增加 \(\log\) 个值。
删除的时候也恰好时这 \(\log\) 个位置。
至于可删堆如何维护。
我们可以拿两个优先队列模拟。
加入时丢进一个优先队列，删除时丢进另一个。
查询时先将堆顶相同的不断弹掉就可以了。
Code
代码就比较简单。
/**
* @file P8543.cpp
* @author mfeitveer
* @date 2023-11-25
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 200010;
const int M = 1000010;
const int mod = 998244353;
int n, m, a[N], c[N], l[N], r[N], ans[M];
vector<int> to[N];
vector<PII> que[N];
priority_queue<int> t1[N<<1], t2[N<<1];
inline void ins(int p, int l, int r, int ls, int rs, int k)
{
if(ls <= l && r <= rs)
return t1[p].push(k), void();
int mid = (l + r) >> 1;
if(mid >= ls) ins(mid<<1, l, mid, ls, rs, k);
if(mid < rs) ins(mid<<1|1, mid + 1, r, ls, rs, k);
}
inline void del(int p, int l, int r, int ls, int rs, int k)
{
if(ls <= l && r <= rs)
return t2[p].push(k), void();
int mid = (l + r) >> 1;
if(mid >= ls) del(mid<<1, l, mid, ls, rs, k);
if(mid < rs) del(mid<<1|1, mid + 1, r, ls, rs, k);
}
inline void calc(int p)
{
while(!t1[p].empty() && !t2[p].empty() && t1[p].top() == t2[p].top())
t1[p].pop(), t2[p].pop();
}
inline int ask(int p)
{ return (t1[p].empty() ? 0 : t1[p].top()); }
inline int ask(int p, int l, int r, int k)
{
calc(p);
if(l == r) return ask(p); int mid = (l + r) >> 1;
if(mid >= k) return max(ask(p), ask(mid<<1, l, mid, k));
return max(ask(p), ask(mid<<1|1, mid + 1, r, k));
}
inline void solve()
{
cin >> n >> m; int x, y;
fro(i, 1, n) cin >> c[i];
fro(i, 1, n) cin >> a[i];
fro(i, 1, n) to[i].eb(0);
fro(i, 1, m) cin >> x >> y, que[y].eb(x, i);
fro(i, 1, n)
{
while(a[to[c[i]].back()] > a[i])
x = to[c[i]].back(), to[c[i]].pop_back(),
del(1, 1, n, l[x], r[x], a[x]);
r[i] = i, l[i] = to[c[i]].back() + 1, to[c[i]].eb(i);
ins(1, 1, n, l[i], r[i], a[i]);
for(auto [l, id] : que[i]) ans[id] = ask(1, 1, n, l);
}
fro(i, 1, m) cout << ans[i] << "\n";
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 1024;
cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
solve();
return 0;
}