本文主要是介绍CodeForces - 940F Machine Learning —— 带修改莫队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
You come home and fell some unpleasant smell. Where is it coming from?
You are given an array a. You have to answer the following queries:
You are given two integers l and r. Let ci be the number of occurrences of i in al: r, where al: r is the subarray of a from l-th element to r-th inclusive. Find the Mex of {c0, c1, …, c109}
You are given two integers p to x. Change ap to x.
The Mex of a multiset of numbers is the smallest non-negative integer not in the set.
Note that in this problem all elements of a are positive, which means that c0 = 0 and 0 is never the answer for the query of the second type.
Input
The first line of input contains two integers n and q (1 ≤ n, q ≤ 100 000) — the length of the array and the number of queries respectively.
The second line of input contains n integers — a1, a2, …, an (1 ≤ ai ≤ 109).
Each of the next q lines describes a single query.
The first type of query is described by three integers ti = 1, li, ri, where 1 ≤ li ≤ ri ≤ n — the bounds of the subarray.
The second type of query is described by three integers ti = 2, pi, xi, where 1 ≤ pi ≤ n is the index of the element, which must be changed and 1 ≤ xi ≤ 109 is the new value.
Output
For each query of the first type output a single integer — the Mex of {c0, c1, …, c109}.
Example
Input
10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8
Output
2
3
2
Note
The subarray of the first query consists of the single element — 1.
The subarray of the second query consists of four 2s, one 3 and two 1s.
The subarray of the fourth query consists of three 1s, three 2s and one 3.
题意：
给你n个数，有两个操作，1 l r表示在l到r这段区间，询问{c0,c1,c2,⋯,c109}的Mex，而ci表示数值i在l r中的出现次数，Mex代表未出现的最小的正整数。举个例子:1 2 3 4 3 2 2 ，最小为4，1 2 3 3 2 1最小是1.。。。2 p x 代表把a[p]改成x
题解：
带修莫队，cnt1[x]维护x出现的次数cnt2[x]维护出现x次的数有多少个。把所有2的操作记录下来，在记录tim代表这个1操作之前有多少2操作，如果在莫队的时候的t小了，那就增加2操作，反之减少
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int len;
struct node
{int l,r,t,bl,br,indx;node(){}node(int l,int r,int t,int indx):l(l),r(r),t(t),indx(indx){bl=l/len,br=r/len;}bool operator< (const node& a)const{if(bl==a.bl&&br==a.br)return t<a.t;if(bl==a.bl)return br<a.br;return bl<a.bl;}
}que[N];
struct query
{int pos,pre,val;// 位置，上一个数，当前的数query(){}query(int pos,int pre,int val):pos(pos),pre(pre),val(val){}
}c[N];
int cnt1[2*N],cnt2[2*N],a[N],b[N*2],now[N],cnt,ans[N];
void add(int pos)
{cnt2[cnt1[pos]]--;cnt1[pos]++;cnt2[cnt1[pos]]++;
}
void del(int pos)
{cnt2[cnt1[pos]]--;cnt1[pos]--;cnt2[cnt1[pos]]++;
}
int ll,rr;
void change(int pos,int x)
{if(pos>=ll&&pos<=rr){del(now[pos]);add(x);}now[pos]=x;
}
int main()
{int n,q;scanf("%d%d",&n,&q);len=pow(n,0.666667);for(int i=1;i<=n;i++){scanf("%d",&a[i]);now[i]=a[i];b[++cnt]=a[i];}/*for(int i=1;i<=n;i++)cout<<now[i]<<" ";cout<<endl;*/int op,qnum=0,tim=0;for(int i=1;i<=q;i++){scanf("%d%d%d",&op,&ll,&rr);if(op==1)que[++qnum]=node(ll,rr,tim,qnum);elseb[++cnt]=rr,c[++tim]=query(ll,now[ll],rr),now[ll]=rr;}/*for(int i=1;i<=n;i++)cout<<now[i]<<" ";cout<<endl;*/sort(b+1,b+1+cnt);sort(que+1,que+qnum+1);int all=unique(b+1,b+1+cnt)-b-1;for(int i=1;i<=n;i++)now[i]=lower_bound(b+1,b+1+all,a[i])-b;for(int i=1;i<=tim;i++){c[i].pre=lower_bound(b+1,b+1+all,c[i].pre)-b;c[i].val=lower_bound(b+1,b+1+all,c[i].val)-b;}ll=1,rr=0;int t=0;for(int i=1;i<=qnum;i++){while(ll>que[i].l)ll--,add(now[ll]);while(rr<que[i].r)rr++,add(now[rr]);while(ll<que[i].l)del(now[ll]),ll++;while(rr>que[i].r)del(now[rr]),rr--;while(t<que[i].t)t++,change(c[t].pos,c[t].val);while(t>que[i].t)change(c[t].pos,c[t].pre),t--;int mex=1;while(cnt2[mex])mex++;ans[que[i].indx]=mex;}for(int i=1;i<=qnum;i++)printf("%d\n",ans[i]);return 0;
}这篇关于CodeForces - 940F Machine Learning —— 带修改莫队的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
