Perform the Combo

Perform the Combo

差分

\(p\) 数组的含义可以理解为\(1\sim p_i\) 之间的数都要被摁一遍，然后再从头开始

那么每次的开头都是\(1\) ，结尾都是\(p_i\) ，利用差分数组，\(O(1)\) 进行区间\(+1\)

最后全部的数字都要摁一遍打出\(combo\) 即 \([1, n] + 1\)

最后把差分数组求前缀和就是每个数字摁的次数，然后再映射到26个小写字母上

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define endl '\n'
typedef double db;
typedef long long LL;
const db EPS = 1e-9;
const int N = 2e5 + 100;
int p,tri[30],b[N];
char str[N];
void add(int l,int r,int v) {
    b[l] += v;
    b[r + 1] -= v;
}
int main() {
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    int t,n,m;
    cin >> t;
    while(t --) {
        memset(tri,0,sizeof tri);
        memset(b,0,sizeof b);
        memset(str,0,sizeof str);
        cin >> n >> m;
        for(int i = 1;i <= n; ++i) cin >> str[i];
        for(int i = 1;i <= m; ++i) {
            cin >> p;
            add(1,p,1);
        }
        add(1,n,1);
        for(int i = 1;i <= n; ++i) {
            b[i] += b[i - 1];
            tri[str[i] - 'a'] += b[i];
        }
        for(int i = 0;i < 26; ++i) cout << tri[i] << ' ';
        cout << endl;
    }
    return 0;
}

Perform the Combo

原文：https://www.cnblogs.com/lukelmouse/p/12544688.html