模板 - 算法基础 - 数组处理

template<typename T>
void ShowArray(T *a, int n, string aname = "") {
    cout << "array " << aname << " = \n";
    for(int i = 1; i <= n; ++i)
        cout << a[i] << " ";
    cout << endl;
}

template<typename T>
int Discretization(T *a, T *b, int n) {
    for(int i = 1; i <= n; ++i)
        b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int cn = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + 1 + cn, a[i]) - b;
    return cn;
}

template<typename T>
int Unique(T *a, int n) {
    sort(a + 1, a + 1 + n);
    return unique(a + 1, a + 1 + n) - (a + 1);
}

template<typename T>
void Prefix(T *a, T *b, int n) {
    b[0] = 0;
    for(int i = 1; i <= n; ++i)
        b[i] = b[i - 1] + a[i];
}

template<typename T>
void Suffix(T *a, T *b, int n) {
    b[n + 1] = 0;
    for(int i = n; i >= 1; --i)
        b[i] = b[i + 1] + a[i];
}