CF1684F Diverse Segments

本题的问题等价于删除一个区间之后是否询问的所有区间都没有相同的数对。
记录 \(i\) 的 \(minL_i\) 表示包含 \(i\) 的区间的最小左端点 \(maxR_i\) 同理，每次删除 \(i\) 的时候记录一下 \(i\) 的贡献，就做完哩。
直接双指针即可。

Tips:
需要关注多个区间的问题都可以化为 \(minL_i\), \(maxR_i\) 的形式。

#include<bits/stdc++.h>
#define LL long long
#define U(x, y, z) for(int x = y; x <= z; ++x)
#define D(x, y, z) for(int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 2e5 + 10;
LL count(const vector<LL> &v, long long l, long long r) {
	return l > r ? 0 : upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
}

inline void solve() {
	LL n, m;
	read(n, m);
	vector<LL> a(n), minL(n, n), maxR(n, -1);
	map<LL, vector<LL>> pos;
	U(i, 0, n - 1) {
		read(a[i]);
		pos[a[i]].emplace_back(i);
	}

	while (m--) {
		LL l, r;
		read(l, r);
		--l, --r;
		if (l < minL[r]) minL[r] = l;
		if (r > maxR[l]) maxR[l] = r;
	}

	D(i, n - 2, 0)
		chkmin(minL[i], minL[i + 1]);
	U(i, 1, n - 1)
		chkmax(maxR[i], maxR[i - 1]);

	LL s = 0;
	for (auto &[v, p] : pos) for (auto &x : p)
		s += count(p, x + 1, maxR[x]);

	if (s == 0) {
		puts("0");
		return ;
	}

	LL l = 0, ans = n;
	U(i, 0, n - 1) {
    	s -= count(pos[a[i]], minL[i], l - 1) + count(pos[a[i]], i + 1, maxR[i]);
		while (l < i && s + count(pos[a[l]], minL[l], l - 1) + count(pos[a[l]], i + 1, maxR[l]) == 0) ++l;
		if (s == 0)
			chkmin(ans, i - l + 1);
	}
	writeln(ans);
}

int main(){
	//FO("");
	int T;
	read(T);
	while (T--) solve();
	return 0;
}