- F. Machine Learning
- time limit per test
- 4 seconds
- memory limit per test
- 512 megabytes
- input
- standard input
- output
- standard output
- 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
- a
- l:r
- , where
- a
- l: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 (1n,q100000) the length of the array and the number of queries respectively.
- The second line of input contains
- n integers
- a1,
- a2,
- ...,
- an (
- 1ai109).
- 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 1lirin the bounds of the subarray.
- The second type of query is described by three integers ti=2, pi, xi, where 1pin is the index of the element, which must be changed and
- 1xi109 is the new value.
- Output
- For each query of the first type output a single integer the
- Mex of
- {c0,c1,...,c109}.
- Example
- Input
- Copy
- 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
- #include<cstdio>
- #include<cstring>
- #include<map>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- const int N=2e5+88;
- map<int,int>M;
- int vis[N],num[N],a[N],b[N],now[N],ans[N],unit,l,r,t;
- struct Query{
- int l,r,tim,id;
- bool operator < (const Query &A)const{
- return l/unit==A.l/unit?(r/unit==A.r/unit?tim<A.tim:r<A.r):l<A.l;
- }
- }Q[N];
- struct Change{
- int pos,x,y;
- }C[N];
- void modify(int x,int d){
- --vis[num[x]];num[x]+=d;++vis[num[x]];
- }
- void going(int T,int d){
- if(C[T].pos>=l&&C[T].pos<=r) modify(C[T].x,d),modify(C[T].y,-d);
- if(d==1) a[C[T].pos]=C[T].x;else a[C[T].pos]=C[T].y;
- }
- int calc(){
- for(int i=1;;++i) if(!vis[i]) return i;
- }
- int main(){
- int n,q,tot,op,cc=0,pp=0;
- scanf("%d%d",&n,&q);
- for(int i=1;i<=n;++i) scanf("%d",&a[i]),now[i]=b[i]=a[i];
- tot=n,unit=(int)pow(n,0.6666666);
- for(int i=1;i<=q;++i) {
- scanf("%d",&op);
- if(op==2){
- ++cc,scanf("%d%d",&C[cc].pos,&C[cc].x);
- C[cc].y=now[C[cc].pos],b[++tot]=now[C[cc].pos]=C[cc].x;
- }
- else {
- ++pp,scanf("%d%d",&Q[pp].l,&Q[pp].r);
- Q[pp].tim=cc,Q[pp].id=pp;
- }
- }
- sort(b+1,b+tot+1);
- tot=unique(b+1,b+tot+1)-b-1;
- for(int i=1;i<=tot;++i) M[b[i]]=i;
- for(int i=1;i<=n;++i) a[i]=M[a[i]];
- for(int i=1;i<=cc;++i) C[i].x=M[C[i].x],C[i].y=M[C[i].y];
- sort(Q+1,Q+pp+1);
- for(int i=1;i<=pp;++i) {
- while(t<Q[i].tim) going(t+1,1),++t;
- while(t>Q[i].tim) going(t,-1),--t;
- while(l<Q[i].l) modify(a[l],-1),++l;
- while(l>Q[i].l) modify(a[l-1],1),--l;
- while(r<Q[i].r) modify(a[r+1],1),++r;
- while(r>Q[i].r) modify(a[r],-1),--r;
- ans[Q[i].id]=calc();
- }
- for(int i=1;i<=pp;++i) printf("%d\n",ans[i]);
- }
- 2
- 3
- 2
莫队学习博客
来源: http://www.bubuko.com/infodetail-2518196.html