[莫队] 洛谷 P3709 大爷的字符串题

题目描述

给你一个字符串a，每次询问一段区间的贡献

贡献定义：

每次从这个区间中随机拿出一个字符x，然后把x从这个区间中删除，你要维护一个集合S

如果S为空，你rp减1

如果S中有一个元素不小于x，则你rp减1，清空S

之后将x插入S

由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少rp？rp初始为0

询问之间不互相影响~

输入输出格式

输入格式：

第一行两个数n，m，表示字符串长度与询问次数

之后一行n个数，表示字符串

由于你是大爷，所以字符集1e9

之后m行每行两个数，表示询问的左右区间

输出格式：

m行，每行一个数表示答案

输入输出样例

输入样例#1：

3 3
3 3 3
3 3
3 3
3 3      

输出样例#1：

-1
-1
-1      

说明

前4个点1s，后面的点4s

对于10%的数据，是样例

对于另外10%的数据，n,m <= 100

对于另外10%的数据，n,m <= 1000

对于另外10%的数据，n,m <= 10000

对于另外10%的数据，n,m <= 100000

对于100%的数据，n,m <= 200000

题解

• 先来看一下题目，首先题目要求我们求的是最少减去rp，那么根据题目我们知道就是要求单调上升的子序列的个数，其实答案其实就是要求区间中众数出现的次数
• 显然就可以用莫队来做
• 那么我们在对于加操作时，如果当前数字的出现次数就是ans，那么++ans
• 对于减操作时，如果当前数字出现次数为ans，且只有一个数字的出现次数为ans，则--ans

代码

1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 const int N=2e5+10;
 8 int n,m,a[N],num,b[N],cnt[N],p[N],ans,bz[N],len;
 9 struct edge { int l,r,d; }e[N];
10 bool cmp(edge a,edge b) { return (a.r/num)==(b.r/num)?a.l<b.l:a.r<b.r; }
11 void add(int x)
12 {
13     if (cnt[a[x]]==ans) ans++;
14     bz[cnt[a[x]]]--,bz[++cnt[a[x]]]++;
15 }
16 void del(int x)
17 {
18     if (ans==cnt[a[x]]&&bz[cnt[a[x]]]==1) ans--;
19     bz[cnt[a[x]]]--,bz[--cnt[a[x]]]++;
20 }
21 int main()
22 {
23     scanf("%d%d",&n,&m),num=sqrt(n);
24     for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
25     sort(b+1,b+n+1),len=unique(b+1,b+n+1)-b-1;
26     for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
27     for (int i=1;i<=m;i++) scanf("%d%d",&e[i].l,&e[i].r),e[i].d=i;
28     sort(e+1,e+m+1,cmp);
29     int l=1,r=0;
30     for (int i=1;i<=m;i++)
31     {
32         while (l<e[i].l) del(l++);
33         while (l>e[i].l) add(--l);
34         while (r<e[i].r) add(++r);
35         while (r>e[i].r) del(r--);
36         p[e[i].d]=ans;
37     }
38     for (int i=1;i<=m;i++) printf("%d\n",-p[i]);
39 }      

转载于:https://www.cnblogs.com/Comfortable/p/10307022.html