題意:給你n個數(shù),m個查詢,查詢有兩種:
(1)區(qū)間[l,r]中每個數(shù)出現(xiàn)的次數(shù)構成一個數(shù)列,問你這個數(shù)列中沒出現(xiàn)的最小數(shù)是多少
(2)將a[l]修改成r
題解:我們考慮莫隊,因為每個數(shù)有1e9這么大,因此要先對每個數(shù)進行離散化更新數(shù)組,然后直接跑莫隊即可。
對于每個第二種操作,我們更新它的影響即可。
?
#include<map>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define ll long long
#define maxn 300005
map<int,int>mp;
int n,q,cnt,tot,siz,sum[maxn],ans[maxn];
int l,r,a[maxn],aa[maxn],g[maxn];
struct node
{
int l,r,t;
}b[maxn],c[maxn];
bool comp(node a,node b)
{
if(a.l/siz<b.l/siz || a.l/siz==b.l/siz && a.r/siz<b.r/siz || a.l/siz==b.l/siz && a.r/siz==b.r/siz && a.t<b.t)
return 1;
return 0;
}
void update1(int x,int val)
{
g[sum[x]]--;
sum[x]+=val;
g[sum[x]]++;
}
void update2(int x,int y)
{
if(l<=x && x<=r)
update1(a[x],-1),update1(y,1);
a[x]=y;
}
int main(void)
{
int i,j,k=0;
scanf("%d%d",&n,&q);
siz=ceil(pow(n,2.0/3));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(!mp[a[i]]) mp[a[i]]=++cnt;
a[i]=aa[i]=mp[a[i]];
}
for(i=1;i<=q;i++)
{
scanf("%d%d%d",&c[i].t,&c[i].l,&c[i].r);
if(c[i].t==1)
b[++tot]=c[i],b[tot].t=i;
else
{
if(!mp[c[i].r]) mp[c[i].r]=++cnt;
c[i].r=mp[c[i].r];
}
}
sort(b+1,b+tot+1,comp);l=1;
for(i=1;i<=tot;i++)
{
while(l>b[i].l) update1(a[--l],1);
while(r<b[i].r) update1(a[++r],1);
while(l<b[i].l) update1(a[l++],-1);
while(r>b[i].r) update1(a[r--],-1);
if(b[i].t<k)
{
k=0;
for(j=1;j<=n;j++)
update2(j,aa[j]);
}
// printf("%d %d
",l,r);
for(;k<b[i].t;k++)
if(c[k].t==2)
update2(c[k].l,c[k].r);
//printf("%d %d
",a[7],sum[1]);
for(j=1;g[j];j++);ans[b[i].t]=j;
}
for(i=1;i<=q;i++)
if(ans[i])
printf("%d
",ans[i]);
return 0;
}
/*
10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8
*/
?
本文摘自 :https://blog.51cto.com/u