CC starter 71 Div 2

CC Starters 71 Div2

F. Unique Mode

题意

在一个数列中，有多少个子序列，满足子序列的众数唯一？

数列长度 $ N < 10^5$

其中 $ -10^9 \leq A[i] \leq 10^9$

每个数字的出现次数 $\leq100$

思路

如果枚举每个区间的话很简单。对于每个右端点$R$，不断左移$L$指针，统计众数的重数，以及有几个众数。很简单，但是很慢。

我们发现，在左移$L$指针的时候，众数的重数一定是递增的。在某一个时刻，会出现新的唯一的众数$w$。我们假设它的重数为$K$；继续左移，会有两种情况：

1. $w$的重数变成$K+1$

2. 出现另一个数$q$，它的重数也是$K$

这个时候，子列 $ A[L..R] $要么不符合要求，要么属于重数为 $K+1$的子列。

而此时右端点为$R$，左端点在 $L+1..R$ 之间的所有子列都可加入计数器。

因此对于每一个右端点，我们考虑找到它众数为$K$的可行子序列。通过上述分析，我们需要掌握的信息有：

$$fir[k] : 第一次出现K重众数的位置$$ $$sec[k] : 第一次出现多个K重众数的位置$$

以上两个“第一次”都是基于不断左移左指针的基础上。

当右端点移动时，只会有一个数字 $A[R+1] = num$ 的重数出现变化

如果$ pos[num][k] > fir[k] :$

$$sec[k] = fir[k]$$ $$fir[k] = pos[num][k]$$ $$否则：sec[k] = max(sec[k], pos[num][k])$$

相当于维护一个最大值和次大值。

注意，如果指针在$fir[k+1]+1与fir[k]$之间移动时始终保持众数唯一，就令$sec[k]=fir[k+1]$ 因此：

$$sec[k] = max(fir[k+1], pos[num][k])$$

以$A[R+1]$结尾的合法子序列数有 $\sum (fir[k] - sec[k])$

答案可能超过$int$，注意使用龙龙。

复杂度：$N \times 100 + NlogN$

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define max(x,y) ((x) > (y) ? (x) : (y))

const int MAXN=1e5+2;

int T,n,a[MAXN],b[MAXN],fir[104],sec[104];
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        long long ans=0;
        memset(fir,0,sizeof fir), memset(sec,0,sizeof sec);
        scanf("%d",&n);
        std::vector<int> pos[n + 1];
        for (int i = 1;i <= n;i++) 
            scanf("%d",&a[i]), b[i] = a[i];
        std::sort(b + 1,b + n + 1);
        for (int i = 1;i <= n;i++)
            a[i] = std::lower_bound(b + 1, b + n + 1, a[i])  - b - 1;

        for (int i = 1;i <= n;i++)
        {
            int num = a[i], siz = pos[num].size();
            for (int j = siz - 1;j >= 0;j--)
            {
                if (j == siz - 1)
                    pos[num].push_back(pos[num][j]);
                else
                    pos[num][j+1] = pos[num][j];
            }
            if (siz) pos[num][0] = i; else pos[num].push_back(i);

            for (int j = siz;j >= 0;j--) 
            {
                if (fir[j + 1] < pos[num][j])
                {
                    sec[j + 1] = max(sec[j + 1], fir[j + 1]);
                    fir[j + 1] = pos[num][j];
                } else
                sec[j + 1] = max(sec[j + 1], pos[num][j]);
            }
            for (int j = 1;j <= 100;j++) 
                ans += fir[j] - max(sec[j], fir[j+1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

本题中每个数字最多出现100次，所以最好从这里入手。因为众数的不可加性，大多数数据结构（除了分块，当然笔者也懒得写）都无法用在这道题中。