【2022国赛模拟】青蛙题——扫描线、可并堆

考虑暴力的做法，首先保留所有相同的数中最靠左的那个，然后从保留的数中选择最靠右的位置，不妨称其为“中点”。容易得出答案的 r ′ r' r′ 必须不左于这个位置 （这里的左仅仅是在左边的意思） 。

然后我们可以从“中点”到 r r r 进行扫描线，维护所有相同的数中最靠右的位置，然后取最小值得到对于每个 r ′ r' r′ 最优的 l ′ l' l′。

由于题目不要求在线，所以我们可以考虑把询问离线下来统一做扫描线。

首先可以离线然后做向左的扫描线求出每个询问的“中点”。然后由于中点的性质，从中点到询问的 r r r 扫描的过程中不会影响到 l l l 前面的值，所以问题就是对于每个询问，求扫描线在其中点到右端点之间的时候，维护的位置中在 l l l 右边的最近位置，到扫描线距离的最小值。

形式化地说，设 S x S_x Sx​ 表示扫描到 x x x 处时维护的最靠右位置的集合， m d i md_i mdi​ 表示询问 i i i 的“中点”，那么我们需要对每个 i i i 求
min ⁡ { x − min ⁡ { y ∣ y ∈ S x , y ≥ l i } + 1 ∣ m d i ≤ x ≤ r i } min{x-min{y|yin S_x,yge l_i}+1|md_ile xle r_i} min{x−min{y∣y∈Sx​,y≥li​}+1∣mdi​≤x≤ri​}我们可以先在扫描线进行到 m d i md_i mdi​ 处时将询问挂到此时对应的 y y y 上，由于维护的集合只会从右边加入并在前面删除，所以合法的 y y y 只会不断右移，并且只会在当前的 y y y 从集合中删除的时候移动。此时需要将挂在 y y y 上的询问整体迁移挂到另一个 y y y 上。

由于我们需要求最小值，所以对于某个合法的 y y y，只有询问刚挂上的时候的答案最优。此时我们需要对挂在此处的询问整体打上一个标记，表示对这些询问产生的贡献。

另外在打上标记之前，这些询问中可能有已经超出询问范围的（即此时扫描线已经超过了对应 r i r_i ri​），我们需要让它们带上标记走人。

最适合实现上述功能且常数最小的数据结构就是手写可并堆了，我们只需要实现懒标记功能和堆合并即可。

我们可以对每个集合内元素维护一个可并堆表示挂在此处的询问， r i r_i ri​ 小的放上面，这样在转移的时候就可以把超出范围的询问一个一个拿出来。

这样算下来总复杂度是 O ( n log ⁡ n ) O(nlog n) O(nlogn) 的，有一些卡常注意事项：
用 set 太慢了，建议换成线段树；
离线挂询问之前先记录一下 vector 需要开多大，然后进行 reserve，这样优化效果比优化可并堆要显著。
可并堆的话虽然在复杂度瓶颈上，但是并不需要多么卡常，所以你写什么都行，左偏树、随机堆，甚至斜堆都能过。

#include//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=2e6+5;
const ll INF=1e17;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
using pii=pair;
int n,m,k,a[MAXN],L[MAXN],R[MAXN],md[MAXN];
const int MX=1e8;
//随机堆
mt19937 Rand(1145141);
struct mgh{
	int s[2],a,lz;mgh(){}
	mgh(int A){a=A,lz=MX,s[0]=s[1]=0;}
}t[MAXN];
void cover(int x,int d){
	if(!x)return;
	t[x].a=min(t[x].a,d),t[x].lz=min(t[x].lz,d);
}
void pushd(int x){
	if(x&&t[x].lzreturn R[x]>R[y];}
int mergh(int x,int y){
	if(!x||!y)return x^y;
	if(cmp(x,y))swap(x,y);
	pushd(x);bool o=Rand()&1;
	if(!t[x].s[o^1])o^=1;
	return t[x].s[o]=mergh(t[x].s[o],y),x;
}
int la[MAXN],as[MAXN],rt[MAXN],sk[MAXN],le,sv[MAXN];
vectorad[MAXN];
//zkw线段树
struct zkw{
	bool f[4100000];int p;//精细计算使用到的位置，空间其实只用开两倍多点
	void init(int n){for(p=1;pfor(f[p+x]^=1,x=(p+x)>>1;x;x>>=1)f[x]=f[x<<1]|f[x<<1|1];}
	int schl(int x){
		for(x=p+x+1;x>1;x>>=1)if((x&1)&&f[x^1]){x^=1;break;}
		for(;x
		for(x=p+x-1;x>1;x>>=1)if((~x&1)&&f[x^1]){x^=1;break;}
		for(;x
	freopen("frog.in","r",stdin);
	freopen("frog.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),k=max(k,a[i]);
	m=read(),T.init(n);
	for(int i=1;i<=m;i++)L[i]=read(),R[i]=read(),sv[L[i]]++;
	for(int i=1;i<=n;i++)ad[i].reserve(sv[i]);
	for(int i=1;i<=m;i++)ad[L[i]].emplace_back(R[i],i);
	for(int i=n;i>0;i--){
		int c=a[i];
		if(la[c])T.cg(la[c]);
		la[c]=i,T.cg(i),sv[i]=0;
		for(auto&x:ad[i])sv[md[x.se]=T.schl(x.fi)]++;
		ad[i].clear();
	}
	for(int i=1;i<=k;i++)if(la[i])T.cg(la[i]),la[i]=0;
	for(int i=1;i<=n;i++)ad[i].reserve(sv[i]);
	for(int i=1;i<=m;i++)
		t[i]=mgh(R[i]-L[i]+1),ad[md[i]].emplace_back(L[i],i);
	for(int i=1;i<=n;i++){
		int c=a[i],y;
		T.cg(i);
		if(la[c]){
			int&x=rt[la[c]];
			while(x&&R[x]
		int x=sk[i];
		as[x]=t[x].a,pushd(x);
		if(t[x].s[0])sk[++le]=t[x].s[0];
		if(t[x].s[1])sk[++le]=t[x].s[1];
	}
	for(int i=1;i<=m;i++)print(as[i]);
	return 0;
}