Description

个人觉得这是这道题最难的一步...出题人的语文...

每次给出一个区间，求这个区间最少能被多少个单调上升的序列覆盖。

Solution

这个东西可以转化为这个区间中出现次数最多的数的出现次数（很好理解吧）

然后用莫队维护两个东西

1. \(cnt_x\) 表示 \(x\) 的出现次数
2. \(num_x\) 表示有多少个数出现次数是 \(x\)

用这两个东西可以方便地维护答案 ans。

加入 \(x\) 就是 num[cnt[x]]--; cnt[x]++; num[cnt[x]]++

删除 \(x\) 麻烦一些。

若 \(cnt_x = ans\) 并且 \(num_{cnt_x}=1\) ，那么 ans 要减 \(1\) (为什么 ans - 1 合法呢？因为删除之后这个数的出现次数就是 ans - 1)

如果不满足上面的这个条件，那么 ans 就不会有变化。最后记得 num[cnt[x]]--; cnt[x]--; num[cnt[x]]++

Code

#include 
    
     using namespace std;const int N = 200200; int n, m, cnt[N], num[N], blo, A[N], a[N], ans, aans[N]; struct node {  int l, r, id;   inline bool operator < (const node &x) const {    return l / blo == x.l / blo ? r < x.r : l / blo < x.l / blo;   }} Q[N]; inline void add(int x) {   num[cnt[a[x]]]--; num[++cnt[a[x]]]++;  ans = max(ans, cnt[a[x]]);  }inline void del(int x) {  if(cnt[a[x]] == ans     && num[cnt[a[x]]] == 1)       ans--;   num[cnt[a[x]]]--;   num[--cnt[a[x]]]++; }int main() {  scanf("%d %d", &n, &m); blo = sqrt(m); int nn = n;   for(int i = 1; i <= n; i++) scanf("%d", &A[i]), a[i] = A[i];   sort(A + 1, A + n + 1); n = unique(A + 1, A + n + 1) - A - 1;   for(int i = 1; i <= nn; i++) a[i] = lower_bound(A + 1, A + n + 1, a[i]) - A;  for(int i = 1; i <= m; i++) {    scanf("%d %d", &Q[i].l, &Q[i].r); Q[i].id = i;   } sort(Q + 1, Q + m + 1);    int L = 0, R = 0;   for(int i = 1; i <= m; i++) {    int l = Q[i].l, r = Q[i].r;    while(L > l) add(--L);    while(R < r) add(++R);    while(L < l) del(L++);     while(R > r) del(R--);     aans[Q[i].id] = -ans;   }  for(int i = 1; i <= m; i++) printf("%d\n", aans[i]);   return 0; }