P9991 [Ynoi Easy Round 2023] TEST_107

枚举任意一种未出现的情况，此时限制是最松的。此时答案为：

\(\max \{p_i-p_{i-1}-1|p_i,p_{i-1}\in[l,r]\}\)

套路的可以用扫描线解决。还有两种情况为：

1. \(p_{i}\in[l,r],p_{i-1}<l\)，贡献为 \(p_i-l\)。

2. \(p_{i}\in[l,r],p_{i+1}>r\)，贡献为 \(r-p_i\)。

以第一种为例，以 \(l\) 作扫描线，则相当于查询 \([l,r]\) 中所有作为该种数最后一次出现的位置的最大值。类似的每次将 \(lst_{a_i}\) 位置的权置为 \(inf\)，\(i\) 处置为 \(i\) 即可。第二种同理。

为了卡常严肃学习了 zkw 线段树 /ll。

Takanashi Rikka

// Problem: P9991 [Ynoi Easy Round 2023] TEST_107
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9991
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
char *p1,*p2,buf[200000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,200000,stdin),p1==p2)?EOF:*p1++)
#define tup(x) array<int,(x)>
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
const int N=2e6+5;
int p[N],ans[N],l[N],r[N],a[N],headl[N],headr[N],cntl,cntr,k;
struct edge{int to,nxt;}L[N],R[N];
inline void addl(int u,int v){L[++cntl]={v,headl[u]},headl[u]=cntl;}
inline void addr(int u,int v){R[++cntr]={v,headr[u]},headr[u]=cntr;}
struct sgt{int x[N<<2],y[N<<2];void build(){intz(y,0x3f);}inline void upd(int i,int d){i+=k,x[i]=y[i]=d;for(i>>=1;i;i>>=1)x[i]=max(x[i<<1],x[i<<1|1]),y[i]=min(y[i<<1],y[i<<1|1]);}inline int MAX(int l,int r){int res=-1e9;for(l=l-1+k,r=r+1+k;l^r^1;l>>=1,r>>=1){if(!(l&1))cmx(res,x[l^1]);if(r&1)cmx(res,x[r^1]);}return res;}inline int MIN(int l,int r){int res=1e9;for(l=l-1+k,r=r+1+k;l^r^1;l>>=1,r>>=1){if(!(l&1))cmn(res,y[l^1]);if(r&1)cmn(res,y[r^1]);}return res;}
}t1,t2;
void UesugiErii(){int n,m;n=read(),m=read(),k=1;while(k<=n+1)k<<=1;for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=m;i++)l[i]=read(),r[i]=read(),addl(l[i],i),addr(r[i],i);t1.build(),t2.build();for(int i=1;i<=n;i++){if(p[a[i]])t1.upd(p[a[i]],i-p[a[i]]-1),t2.upd(p[a[i]],1e9);p[a[i]]=i,t2.upd(i,i);for(int j=headr[i],v;j;j=R[j].nxt)v=R[j].to,cmx(ans[v],t1.MAX(l[v],r[v])),cmx(ans[v],i-t2.MIN(l[v],r[v]));}t1.build();for(int i=1;i<=n;i++)p[a[i]]=0;for(int i=n;i;i--){if(p[a[i]])t1.upd(p[a[i]],-1);t1.upd(i,i),p[a[i]]=i;for(int j=headl[i],v;j;j=L[j].nxt)v=L[j].to,cmx(ans[v],t1.MAX(l[v],r[v])-i);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}
signed main(){// cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}