本文主要是介绍codeforces 940f Machine Learning【带修改莫队+离散化】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
1
2
3
4
5
6
output
2
3
2
题意：
题意难懂，两种操作，
1.查询：区间所有数的次数第一个为0的自然数，假如这个区间1出现2次，3出现1次，则答案是3，注意是出现次数
2、修改：修改某一个位置的值。
分析：
带修改莫队的基本应用，用一个num记录数出现的个数就ok，看代码把，一看就懂
///带莫队算法模板：求区间不同数的个数+单点修改
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
const int maxn=1000005;
typedef long long ll;void add(int x);
void del(int x);
void modify(int x,int ti); //这个函数会执行或回退修改ti（执行还是回退取决于是否执行过，具体通过swap实现），x表明当前的询问是x，即若修改了区间[q[x].l,q[x].r]便要更新答案int sz,cnt[maxn],b[maxn],a[maxn],Ans,ans[maxn],num[maxn];struct Change
{int p,col;
}c[maxn];struct Query
{int l,r,t,id;bool operator<(Query& b){return l/sz==b.l/sz?(r/sz==b.r/sz?t<b.t:r<b.r):l<b.l;}
}q[maxn];int main()
{int n,m;while(scanf("%d%d",&n,&m)!=-1){memset(cnt,0,sizeof(cnt)); memset(num,0,sizeof(num));sz=pow(n,0.66666);for (int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}int op;int ccnt=0,qcnt=0;for (int i=1;i<=m;++i){scanf("%d",&op);if (op==1){++qcnt;scanf("%d%d",&q[qcnt].l,&q[qcnt].r) ;q[qcnt].t=ccnt;q[qcnt].id=qcnt;}else{++ccnt;scanf("%d%d",&c[ccnt].p,&c[ccnt].col);b[n+ccnt]=c[ccnt].col;}}sort(b+1,b+n+ccnt+1);int sum=unique(b+1,b+n+ccnt+1)-b-1;for(int i=0;i<=n;i++){a[i]=lower_bound(b+1,b+sum+1,a[i])-b;//cout<<a[i]<<endl;}for(int i=1;i<=ccnt;i++){c[i].col=lower_bound(b+1,b+sum+1,c[i].col)-b;}int l=1,r=0,now=0;Ans=0;sort(q+1,q+qcnt+1);for (int i=1;i<=qcnt;++i){while (r<q[i].r){add(a[++r]);}while(l>q[i].l){add(a[--l]);}while (l<q[i].l){del(a[l++]);}while (r>q[i].r){del(a[r--]);}while (now<q[i].t){modify(i,++now);}while (now>q[i].t){modify(i,now--);}for(ans[q[i].id]=1;num[ans[q[i].id]]>0;++ans[q[i].id]);}for (int i=1;i<=qcnt;++i){cout<<ans[i]<<endl;}}return 0;
}void add(int x)
{num[cnt[x]]--;cnt[x]++;num[cnt[x]]++;
}void del(int x)
{num[cnt[x]]--;cnt[x]--;num[cnt[x]]++;
}void modify(int x,int ti)
{if (c[ti].p>=q[x].l&&c[ti].p<=q[x].r){del(a[c[ti].p]);add(c[ti].col);}swap(a[c[ti].p],c[ti].col);
}
这篇关于codeforces 940f Machine Learning【带修改莫队+离散化】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
