其实本题的思路大概可以从数据范围看出来:

\(n\le5\times 10^5\)

这个东西要嘛\(O(n~logn)\)要嘛\(O(n)\)，要\(O(n~logn)\)只有二分或排序或常数（stl模板）三个个选项。

这题能二分吗？似乎不能（check是写不了的，能写那直接写正解不好了）。

那排序有可能吗？似乎是不行的（他的操作按顺序，你排了那能对吗？）。

所以说这题肯定是线性的（可能有log常数）。

\(O(n)\)通常是dp，dp通常出于bfs，那我们先写bfs吧。

关注每一次操作，他的答案要的是对于每一个\(i\)的数出现几次，那我们可以数视为点，那边就是两次操作的链接，如果一个数在上一次出现过就意味着从上一个数出现的地方删到这个数的前一个数，相当于在从上一个数出现的地方的前一个数到现在的数。

那一次操作的图如下(1 4 2 3 4 2 3的第一次操作)：

1(第1个数)->4(第5个数)->2(第6个数)->3(第7个数)

我们把操作都合在一起（点权为下标）：

（虚线指第一次操作放的数被删了）

可以注意到边是一样的，所以可以先统一建边，再统一放每个起始。

#include
using namespace std;
int a[500050],at[500050],to[500050],d[500050],ans[500050];
bool fl[500050];
int main(){//freopen("card.in","r",stdin);//freopen("card.out","w",stdout);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];to[i]=i+1;}for(int i=n;i>=1;i--){if(at[a[i+1]])to[i]=at[a[i+1]];//连跳else at[a[i+1]]=i+1;}if(!at[a[1]])at[a[1]]=1;priority_queue,greater> q;//保持顺序for(int i=1;i<=n;i++){d[at[a[i]]]++;q.push(at[a[i]]);}while(!q.empty()){int u=q.top();q.pop();if(fl[u])continue;if(u==0||u==n+1)break;fl[u]=1;ans[a[u]]+=d[u];d[to[u]]+=d[u];q.push(to[u]);}for(int i=1;i<=m;i++)cout<

这可以等价于dp。 代码（仅供参考）

using namespace std;
int a[500050],at[500050],to[500050],dp[500050],ans[500050];
int main(){//freopen("card.in","r",stdin);//freopen("card.out","w",stdout);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];to[i]=i+1;}for(int i=n;i>=1;i--){if(at[a[i+1]])to[i]=at[a[i+1]];//连跳else at[a[i+1]]=i+1;}if(!at[a[1]])at[a[1]]=1;for(int i=1;i<=n;i++){dp[at[a[i]]]++;}for(int i=1;i<=n;i++){ans[a[i]]+=dp[i];dp[to[i]]+=dp[i];}for(int i=1;i<=m;i++)cout<