纸牌游戏

记last[x]为x在整个数组中的最后出现位置。从位置i开始的游戏中，a[i]会一直保留到它最后一次出现；该次打出会清空它右侧所有牌，因此最终桌面等于a[i]接上从last[a[i]]+1开始的游戏结果。令next[i]=last[a[i]]+1，则next[i]>i。所有起点各提供一个单位贡献，ways[i]初始为1。按i递增，ans[a[i]]加ways[i]，并将ways[i]加到ways[next[i]]（若仍在数组内）。每条链上同一种牌只会出现一次，故不会重复统计。O(n+m)时间、O(n+m)空间。注意不应逐个模拟全部后缀。

难度：5（geekpi-9-v2），依据：将每个后缀的保留序列转为最后出现位置后的跳转链，在有向无环依赖上累加所有起点贡献。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;int main(){int n,m;cin>>n>>m;vector<int>a(n+1),last(m+1);vector<long long>w(n+2,1),ans(m+1);for(int i=1;i<=n;i++){cin>>a[i];last[a[i]]=i;}for(int i=1;i<=n;i++){ans[a[i]]+=w[i];int j=last[a[i]]+1;if(j<=n)w[j]+=w[i];}for(int x=1;x<=m;x++)cout<<ans[x]<<(x==m?'\n':' ');}

本数据为GeekPi自建训练数据，非官方评测数据。