P8543 「Wdoi-2」纯粹的复仇女神 题解

自己的套路还是见少了。

思路

考虑扫描线。

每一个颜色的 \(\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;
}