找不到链接

题目描述

题解

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

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

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

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

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

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

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

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

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

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

代码

#include<bits/stdc++.h>//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,int>;
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].lz<MX)cover(t[x].s[0],t[x].lz),cover(t[x].s[1],t[x].lz),t[x].lz=MX;
}
bool cmp(int x,int y){return 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];
vector<pii>ad[MAXN];
//zkw线段树
struct zkw{bool f[4100000];int p;//精细计算使用到的位置，空间其实只用开两倍多点void init(int n){for(p=1;p<n+2;p<<=1);}void cg(int x){for(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<p;x<<=1,x^=f[x^1]);return x-p;}int schr(int x){for(x=p+x-1;x>1;x>>=1)if((~x&1)&&f[x^1]){x^=1;break;}for(;x<p;x<<=1,x^=f[x]^1);return x-p;}
}T;
int main()
{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]<i)as[x]=t[x].a,pushd(x),x=mergh(t[x].s[0],t[x].s[1]);T.cg(la[c]);if(x)y=T.schr(la[c]),cover(x,i-y+1),rt[y]=mergh(rt[y],x),x=0;}la[c]=i;for(auto&x:ad[i])y=T.schr(x.fi),cover(x.se,i-y+1),rt[y]=mergh(rt[y],x.se);}for(int i=1;i<=n;i++)if(rt[i])sk[++le]=rt[i];for(int i=1;i<=le;i++){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;
}