传送门：点击打开链接
题意：一个序列，问所有的子序列的beauty操作之后的数字之和。beauty操作是将序列相邻多个相等的数字删除到只剩下一个
思路：设F[i]表示以A[i]结尾的子序列的答案，cnt[i]表示以A[i]的结尾的子序列个数。那么对于第i个，可以枚举以A[k]结尾(k<i)的子序列的个数，A[i]是可以从这些子序列转移过来的，想清楚转移方程。然后就是说还要维护以A[i]这个数字结尾的子序列个数，假如从这些子序列中转移过来，就不能加上A[i]，需要把从这些转移过来的A[I]再减去，这里用哈希来维护。上面转移的时候，F数组和cnt数组都要求和，这部分用前缀和来维护。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.in","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1e5 + 5;
const int mod = 1e9 + 7;int rear;
LL A[MX], B[MX], f, cnt;
LL S[MX], cntS[MX];
LL cntB[MX];int BS(int x) {int l = 1, r = rear, m;while(l <= r) {m = (l + r) >> 1;if(B[m] == x) return m;if(B[m] <= x) l = m + 1;else r = m - 1;}return -1;
}int main() {int T, n; //FIN;scanf("%d", &T);while(T--) {memset(cntB, 0, sizeof(cntB));scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%I64d", &A[i]);B[i] = A[i];}sort(B + 1, B + 1 + n);rear = unique(B + 1, B + 1 + n) - B - 1;S[0] = cntS[0] = 0;for(int i = 1; i <= n; i++) {int id = BS(A[i]);f = (S[i - 1] + A[i] * (cntS[i - 1] + 1) % mod) % mod;f = (f - cntB[id] * A[i] % mod + mod) % mod;cnt = (cntS[i - 1] + 1) % mod;cntB[id] = (cntB[id] + cnt) % mod;S[i] = (S[i - 1] + f) % mod;cntS[i] = (cntS[i - 1] + cnt) % mod;}printf("%I64d\n", S[n]);}return 0;
}