[莫隊] 洛谷 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