An interesting problem using suffix sum.
For each wrong tries that is correct until after index p[i], we add 1 to cnt[p[i]]. This represents that all characters before and including s[p[i]] have 1 more appearance. After processing all wrong tries, we sum up each cnt[i] backward, from right to left. The reason is that any wrong try always start from the first character. So cnt[j] <= cnt[i], if j > i. In other word, for a given cnt[i] that represents the count of s[i] for all wrong tries, it is equal to the number of wrong tries that goes correct at least as far as s[i], which is essentially the sum for all cnt[j], j >= i. Hence the name suffix sum.
private static void solve(int q, FastScanner in, PrintWriter out) { for (int qq = 0; qq < q; qq++) { int n = in.nextInt(); int m = in.nextInt(); String s = in.next(); int[] p = new int[m]; for(int i = 0; i < m; i++) { p[i] = in.nextInt() - 1; } long[] cnt = new long[n]; for(int i = 0; i < m; i++) { cnt[p[i]]++; } for(int i = n - 2; i >= 0; i--) { cnt[i] += cnt[i + 1]; } long[] ans = new long[26]; for(int i = 0; i < n; i++) { ans[s.charAt(i) - ‘a‘] += (cnt[i] + 1); } for(int j = 0; j < 26; j++) { out.print(ans[j] + " "); } out.println(); } out.close(); }
[CodeForces] Perform the Combo
原文：https://www.cnblogs.com/lz87/p/12388151.html