CF1000F One Occurrence

本题解用于记录一下一个优秀的东西——懒标记。

题解

可以很轻易的想到莫队的做法，但是题目让你输出的是满足条件的一个数，而不是满足条件的数的个数，似乎很难去 \(O(1)\) 转移。这个时候我们的懒标记就出场了。

我们可以维护一个栈，然后再加数字的时候直接加，但是删数字的时候在外面删（维护一个 \(bool\) 数组），然后回答询问时就不停的弹出栈首，直到栈首存活。这一系列操作可以满足均摊复杂度 \(O(1)\) ，很强，是使用莫队时搭配的好伙伴。

以上。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,Q=5e5+5;
int n,q,a[N];
int bel[N],size;
struct Query{int l,r,id;}s[Q];
bool cmp(Query a,Query b)
{
if(bel[a.l]!=bel[b.l]) return a.l<b.l;
if(bel[a.l]&1)  return a.r<b.r;
return a.r>b.r;
}
int cnt[N],ans[Q];
int l=1,r=0,res=0;
stack<int> st;
int alive[N];
int main()
{
cin>>n;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
cin>>q;
for(int i=1;i<=q;++i) scanf("%d%d",&s[i].l,&s[i].r),s[i].id=i;
size=sqrt(n);
for(int i=1,cnt=0;i<=n;i+=size,++cnt)
{
for(int j=i;j<=n&&j<i+size;++j)
bel[j]=cnt;
}
sort(s+1,s+1+q,cmp);
for(int i=1;i<=q;++i)
{
while(r<s[i].r)
{
r++;
if(cnt[a[r]]==1) --res,alive[a[r]]^=1;
cnt[a[r]]++;
if(cnt[a[r]]==1) ++res,alive[a[r]]^=1,st.push(a[r]);
}
while(r>s[i].r)
{
if(cnt[a[r]]==1) --res,alive[a[r]]^=1;
cnt[a[r]]--;
if(cnt[a[r]]==1) ++res,alive[a[r]]^=1,st.push(a[r]);
r--;
}
while(l<s[i].l)
{
if(cnt[a[l]]==1) --res,alive[a[l]]^=1;
cnt[a[l]]--;
if(cnt[a[l]]==1) ++res,alive[a[l]]^=1,st.push(a[l]);
l++;
}
while(l>s[i].l)
{
l--;
if(cnt[a[l]]==1) --res,alive[a[l]]^=1;
cnt[a[l]]++;
if(cnt[a[l]]==1) ++res,alive[a[l]]^=1,st.push(a[l]);
}
while(!st.empty()&&!alive[st.top()]) st.pop();
if(st.empty()) ans[s[i].id]=0;
else ans[s[i].id]=st.top();
}
for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
return 0;
}