首页 > 其他分享 >Solution Set 2023.12.25

Solution Set 2023.12.25

时间:2023-12-25 22:12:00浏览次数:46  
标签:std count Set const 2023.12 valueType Solution rank SA

【模板】后缀排序

考虑首先将所有长度为 \(1\) 的子串进行排序,然后将所有长度为 \(2\) 的子串排序,长度不足的以空字符补齐。以此类推,每次排序的子串长度均是上一次排序的子串长度的两倍。最后一次排序后,所有子串均已排序完毕,此时得到的序列即为后缀数组。

考虑如何快速进行排序,若我们已经完成对于长度为 \(2^k\) 的子串的排序,那么我们可以利用这个结果对长度为 \(2^{k+1}\) 的子串进行排序。我们可以将长度为 \(2^{k+1}\) 的子串看作长度为 \(2^k\) 的两个子串的组合,那么我们只需要对这两个子串的排序结果进行归并即可得到长度为 \(2^{k+1}\) 的子串的排序结果。

发现归并的实质是以前半部分和后半部分的排名分别为第一关键字和第二关键字进行排序,使用基数排序即可优化至 \(O(n)\)。

同时由于我们得到了排名数组的逆数组,我们可以利用这个逆数组快速完成第二关键字的排序,进而优化常数。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;

std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::string const &S) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(N + 1, 0), id, count;

    id.reserve(N);

    valueType M = 255;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);

    return std::make_pair(SA, rank);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    string S;

    std::cin >> S;

    valueType const N = S.size();

    S = '#' + S;

    auto const [SA, rank] = GetSuffixArray(N, S);

    for (valueType i = 1; i <= N; ++i)
        std::cout << SA[i] << ' ';

    std::cout << std::endl;

    return 0;
}

[JSOI2007] 字符加密

将字符串 \(S\) 复制一次后得到字符串 \(SS\),求出其后缀数组后按排名枚举所有长度大于等于 \(\left\lvert S \right\rvert\) 的后缀添加进答案中即可。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;

std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::string const &S) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(N + 1, 0), id, count;

    id.reserve(N);

    valueType M = 255;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);

    return std::make_pair(SA, rank);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    string S;

    std::cin >> S;

    valueType const N = S.size();

    S = '#' + S + S;

    auto const [SA, rank] = GetSuffixArray(2 * N, S);

    string ans;

    for (valueType i = 1; i <= 2 * N; ++i)
        if (SA[i] <= N)
            ans += S[SA[i] + N - 1];

    std::cout << ans << std::endl;

    return 0;
}

[USACO07DEC] Best Cow Line G / [USACO07NOV] Best Cow Line S

考虑如何暴力求解,对于当前的情况比较当前剩余的字符串的前缀和后缀的字典序大小关系并选择较小的那个即可,复杂度为 \(O(n^2)\)。

考虑如何优化,发现我们其实是需要求出字符串中所有前缀和后缀的字典序大小关系,将字符串反转后拼接到原字符串后,我们可以直接求出所有前缀和后缀的字典序大小关系,这样就可以将复杂度优化至 \(O(n \log n)\)。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;

std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::string const &S) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(N + 1, 0), id, count;

    id.reserve(N);

    valueType M = 255;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);

    return std::make_pair(SA, rank);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    string S;

    for (valueType i = 0; i < N; ++i) {
        char c;

        std::cin >> c;

        S.push_back(c);
    }

    S = '#' + S + '#' + string(S.rbegin(), S.rend());

    auto const [SA, rank] = GetSuffixArray(2 * N + 1, S);

    string ans;

    valueType l = 1, r = N;

    while (l <= r) {
        if (rank[l] < rank[2 * N + 2 - r])
            ans.push_back(S[l++]);
        else
            ans.push_back(S[r--]);
    }

    for (valueType i = 0; i < N; ++i) {
        std::cout << ans[i];

        if ((i + 1) % 80 == 0)
            std::cout << '\n';
    }

    std::cout << std::flush;

    return 0;
}

不同子串个数

考虑将所有后缀排序后枚举并考虑其贡献,发现其贡献为当前后缀长度减去与前一个后缀的最长公共前缀长度,因此我们可以利用后缀数组求出 \(\operatorname{height}\) 数组后求和即可。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;

std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::string const &S) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(N + 1, 0), id, count;

    id.reserve(N);

    valueType M = 255;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);

    return std::make_pair(SA, rank);
}

template<typename Container_>
ValueVector GetHeight(valueType N, Container_ const &S, ValueVector const &SA, ValueVector const &rank) {
    ValueVector height(N + 1, 0);

    valueType pos = 0;

    for (valueType i = 1; i <= N; ++i) {
        if (rank[i] == 1)
            continue;

        if (pos > 0)
            --pos;

        while (i + pos < S.size() && SA[rank[i] - 1] + pos < S.size() && S[i + pos] == S[SA[rank[i] - 1] + pos])
            ++pos;

        height[rank[i]] = pos;
    }

    return height;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    string S;

    std::cin >> S;

    S = '#' + S;

    auto const [SA, rank] = GetSuffixArray(N, S);

    auto const height = GetHeight(N, S, SA, rank);

    valueType ans = N * (N + 1) / 2 - std::accumulate(height.begin() + 1, height.end(), 0);

    std::cout << ans << std::endl;

    return 0;
}

[SDOI2008] Sandy 的卡片

考虑通过二分答案转化为判定问题。

将所有的字符串差分后拼接起来,然后求出其后缀数组。进而只需要判定是否存在长度为 \(k\) 的子串使得其在每个字符串中均出现,判定 \(\operatorname{height}\) 序列上是否存在一个区间满足其最小值大于等于 \(k\) 且出现了所有的字符串即可。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;

template<typename T>
std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::vector<T> const &S, valueType V) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(N + 1, 0), id, count;

    id.reserve(N);

    valueType M = V;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);

    return std::make_pair(SA, rank);
}

template<typename Container_>
ValueVector GetHeight(valueType N, Container_ const &S, ValueVector const &SA, ValueVector const &rank) {
    ValueVector height(N + 1, 0);

    valueType pos = 0;

    for (valueType i = 1; i <= N; ++i) {
        if (rank[i] == 1)
            continue;

        if (pos > 0)
            --pos;

        while (i + pos < S.size() && SA[rank[i] - 1] + pos < S.size() && S[i + pos] == S[SA[rank[i] - 1] + pos])
            ++pos;

        height[rank[i]] = pos;
    }

    return height;
}

constexpr valueType V = 5000, shift = 2000;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, minLength = std::numeric_limits<valueType>::max();

    std::cin >> N;

    ValueVector A, belong;

    for (valueType i = 1; i <= N; ++i) {
        valueType M;

        std::cin >> M;

        minLength = std::min(minLength, M);

        ValueVector S(M + 1, 0);

        for (valueType j = 1; j <= M; ++j)
            std::cin >> S[j];

        A.push_back(V - i);
        belong.push_back(0);

        for (valueType j = 2; j <= M; ++j) {
            A.push_back(S[j] - S[j - 1] + shift);
            belong.push_back(i);
        }
    }

    valueType const size = A.size() - 1;

    auto [SA, rank] = GetSuffixArray(size, A, V);
    auto height = GetHeight(size, A, SA, rank);

    auto check = [&](valueType limit) {
        valueType last = 1;
        ValueVector tag(N + 1, 0);

        for (valueType i = 1; i <= size; ++i) {
            if (height[i] < limit) {
                valueType count = 0;

                for (valueType j = last; j < i; ++j) {
                    if (tag[belong[SA[j]]] != i) {
                        tag[belong[SA[j]]] = i;

                        ++count;
                    }
                }

                if (count == N)
                    return true;

                last = i;

                continue;
            }
        }

        return false;
    };

    valueType ans = 0, l = 1, r = minLength - 1;

    while (l <= r) {
        valueType mid = (l + r) >> 1;

        if (check(mid)) {
            ans = mid;

            l = mid + 1;
        } else
            r = mid - 1;
    }

    std::cout << ans + 1 << std::endl;

    return 0;
}

[SCOI2012] 喵星球上的点名

首先将所有的字符串拼接起来并求出后缀数组,并通过后缀数组对于每个询问串确定出其在后缀数组中出现的区间。

现在问题转化为了求出区间内的颜色种类数和颜色出现次数,其中第一问可以通过莫队算法解决,考虑如何求解第二问。

我们可以将其贡献在时间序上差分,进而只需要求出每个时间点的贡献即可。我们可以发现,对于每个时间点,若某个颜色不再出现在莫队区间中,那么其产生剩余操作数的负贡献,若某个颜色在莫队区间中首次出现,那么其产生剩余操作数的正贡献。在莫队的过程中求解即可。

Code
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::pair<valueType, valueType> ValuePair;

namespace SuffixArray {
    template<typename T>
    std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::vector<T> const &S, valueType V) {// 1 - index
        ValueVector SA(2 * N + 1, 0), rank(2 * N + 1, 0), id, count;

        id.reserve(N);

        valueType M = V;

        count.resize(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[i] = S[i]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[i]]--] = i;

        for (valueType w = 1; w < N; w <<= 1) {
            id.clear();

            id.push_back(0);

            for (valueType i = N - w + 1; i <= N; ++i)
                id.push_back(i);

            for (valueType i = 1; i <= N; ++i)
                if (SA[i] > w)
                    id.push_back(SA[i] - w);

            count.assign(M + 1, 0);

            for (valueType i = 1; i <= N; ++i)
                ++count[rank[id[i]]];

            std::partial_sum(count.begin(), count.end(), count.begin());

            for (valueType i = N; i >= 1; --i)
                SA[count[rank[id[i]]]--] = id[i];

            id = rank;

            M = 0;

            for (valueType i = 1; i <= N; ++i)
                rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;

            if (M == N)
                break;
        }

        SA.resize(N + 1);
        rank.resize(N + 1);

        return std::make_pair(SA, rank);
    }

    template<typename Container_>
    ValueVector GetHeight(valueType N, Container_ const &S, ValueVector const &SA, ValueVector const &rank) {
        ValueVector height(N + 1, 0);

        valueType pos = 0;

        for (valueType i = 2; i <= N; ++i) {
            if (pos > 0)
                --pos;

            while (i + pos < S.size() && SA[rank[i] - 1] + pos < S.size() && S[i + pos] == S[SA[rank[i] - 1] + pos])
                ++pos;

            height[rank[i]] = pos;
        }

        return height;
    }

    template<typename Container_, typename Type_>
    ValuePair GetRange(valueType N, Container_ const &S, ValueVector const &SA, std::vector<Type_> const &T) {// find the first appearance and last appearance of T in S
        valueType l = 1, r = N, first = 1, last = 1;

        while (l <= r) {
            valueType const mid = (l + r) >> 1;

            if (std::lexicographical_compare(S.begin() + SA[mid], SA[mid] + T.size() > S.size() ? S.end() : S.begin() + SA[mid] + T.size(), T.begin(), T.end())) {
                l = mid + 1;

                first = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        // judge if T is not in S
        if (SA[first] + T.size() > S.size() || !std::equal(S.begin() + SA[first], S.begin() + SA[first] + T.size(), T.begin(), T.end()))
            return std::make_pair(0, 0);

        l = 1, r = N;

        while (l <= r) {
            valueType const mid = (l + r) >> 1;

            if (std::lexicographical_compare(S.begin() + SA[mid], SA[mid] + T.size() > S.size() ? S.end() : S.begin() + SA[mid] + T.size(), T.begin(), T.end(), std::greater<>())) {
                r = mid - 1;

                last = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return std::make_pair(first, last);
    }
}// namespace SuffixArray

namespace MoAlgorithm {
    class Recorder {
    private:
        valueType N, count;
        ValueVector bucket;

    public:
        explicit Recorder(valueType N) : N(N), count(0), bucket(N + 1, 0) {}

        valueType add(valueType x) {
            if (x < 1)
                return 0;

            if (++bucket[x] == 1) {
                ++count;

                return x;
            } else {
                return 0;
            }
        }

        valueType del(valueType x) {
            if (x < 1)
                return 0;

            if (--bucket[x] == 0) {
                --count;

                return x;
            } else {
                return 0;
            }
        }

        valueType get() const {
            return count;
        }
    };

    valueType N, M, L;
    ValueVector belong;
    TupleVector query;
    ValueVector color, queryAns, colorAns;

    bool compare(ValueTuple const &lhs, ValueTuple const &rhs) {
        valueType const l = std::get<0>(lhs), r = std::get<0>(rhs);

        return belong[l] == belong[r] ? std::get<1>(lhs) < std::get<1>(rhs) : belong[l] < belong[r];
    }

    void init(valueType n, valueType m, valueType l, ValueVector const &color_) {
        N = n;
        M = m;
        L = l;
        color = color_;
        belong.resize(L + 1, 0);
        query.reserve(M);
        queryAns.resize(M + 1, 0);
        colorAns.resize(N + 1, 0);

        valueType const B = std::sqrt(L);

        for (valueType i = 1; i <= L; ++i)
            belong[i] = (i - 1) / B + 1;
    }

    void addQuery(valueType l, valueType r, valueType id) {
        query.emplace_back(l, r, id);
    }

    std::pair<ValueVector, ValueVector> solve() {
        std::sort(query.begin(), query.end(), compare);

        Recorder recorder(N);

        valueType nowL = 1, nowR = 0, remain = M;

        for (auto const &[l, r, id] : query) {
            while (nowL < l)
                colorAns[recorder.del(color[nowL++])] -= remain;

            while (nowL > l)
                colorAns[recorder.add(color[--nowL])] += remain;

            while (nowR < r)
                colorAns[recorder.add(color[++nowR])] += remain;

            while (nowR > r)
                colorAns[recorder.del(color[nowR--])] -= remain;

            queryAns[id] = recorder.get();

            --remain;
        }

        return std::make_pair(queryAns, colorAns);
    }
}// namespace MoAlgorithm

constexpr valueType V = 2e5;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector A, belong;

    for (valueType i = 1; i <= N; ++i) {
        for (valueType k = 0; k <= 1; ++k) {
            valueType L;

            std::cin >> L;

            A.push_back(V - 2 * i - k);
            belong.push_back(0);

            for (valueType j = 1; j <= L; ++j) {
                valueType x;

                std::cin >> x;

                A.push_back(x);
                belong.push_back(i);
            }
        }
    }

    valueType const L = A.size() - 1;

    ValueVector S(M + 1, 0);

    auto const [SA, rank] = SuffixArray::GetSuffixArray(L, A, V);

    for (valueType i = 1; i <= M; ++i) {
        valueType len;

        std::cin >> len;

        ValueVector T(len, 0);

        for (auto &x : T)
            std::cin >> x;

        auto const [first, last] = SuffixArray::GetRange(L, A, SA, T);

        MoAlgorithm::addQuery(first, last, i);
    }

    ValueVector color(L + 1, 0);

    for (valueType i = 0; i <= L; ++i)
        color[i] = belong[SA[i]];

    MoAlgorithm::init(N, M, L, color);

    auto const [queryAns, colorAns] = MoAlgorithm::solve();

    for (valueType i = 1; i <= M; ++i)
        std::cout << queryAns[i] << '\n';

    for (valueType i = 1; i <= N; ++i)
        std::cout << colorAns[i] << ' ';

    std::cout << std::endl;

    return 0;
}

[HEOI2016/TJOI2016] 字符串

首先通过二分答案转化为判定问题。

接下来我们的问题转化为:

给定一个常数 \(k\),判定后缀 \(a\) 到后缀 \(b - k + 1\) 中是否存在一个后缀使得其与后缀 \(c\) 的最长公共前缀长度大于等于 \(k\)。

我们可以发现,与后缀 \(c\) 的最长公共前缀长度大于等于 \(k\) 的后缀在后缀数组上一定是连续的,因此我们可以通过二分求出其具体范围。

下面我们只需要判定是否存在一个 \(i \in \left[a, b - k + 1\right]\),满足其后缀数组的值在上文求出的范围内即可,此问题为二维数点问题,使用主席树求解即可。

总复杂度 \(O(n \log^2 n)\)。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;

class PersistentSegTree {
private:
    typedef valueType sizeType;

    struct NODE {
        typedef NODE *pointer;

        pointer leftSon, rightSon;
        sizeType count;

        NODE() : leftSon(nullptr), rightSon(nullptr), count(0){};

        void update() {
            count = 0;

            if (leftSon != nullptr)
                count += leftSon->count;

            if (rightSon != nullptr)
                count += rightSon->count;
        }
    };

    typedef typename NODE::pointer pointer;
    typedef std::vector<pointer> PointerVector;

    sizeType N;

    PointerVector root;

    static pointer newNode() {
        static sizeType const POOL_SIZE = 4500000;

        static sizeType const NODE_SIZE = sizeof(NODE) / sizeof(char);

        static char *memoryPool = new char[NODE_SIZE * POOL_SIZE];

        static sizeType memoryPoolSize = 0;

        if (memoryPoolSize + NODE_SIZE > POOL_SIZE * NODE_SIZE)
            throw std::bad_alloc();

        pointer result = reinterpret_cast<pointer>(memoryPool + memoryPoolSize);

        memoryPoolSize += NODE_SIZE;

        return result;
    }

    static pointer build(sizeType l, sizeType r) {
        pointer current = newNode();

        if (l == r) {
            current->count = 0;

            return current;
        }

        sizeType mid = (l + r) >> 1;

        current->leftSon = build(l, mid);
        current->rightSon = build(mid + 1, r);

        current->update();

        return current;
    }

    pointer insert(pointer const &current, sizeType nodeL, sizeType nodeR, sizeType pos) {
        pointer result = newNode();
        *result = *current;

        ++result->count;

        if (nodeL == nodeR)
            return result;

        sizeType const mid = (nodeL + nodeR) >> 1;

        if (pos <= mid)
            result->leftSon = insert(current->leftSon, nodeL, mid, pos);
        else
            result->rightSon = insert(current->rightSon, mid + 1, nodeR, pos);

        return result;
    }

    static sizeType query(pointer const &current, sizeType nodeL, sizeType nodeR, sizeType queryL, sizeType queryR) {
        if (queryL <= nodeL && nodeR <= queryR)
            return current->count;

        sizeType const mid = (nodeL + nodeR) >> 1;

        if (queryR <= mid)
            return query(current->leftSon, nodeL, mid, queryL, queryR);
        else if (queryL > mid)
            return query(current->rightSon, mid + 1, nodeR, queryL, queryR);
        else
            return query(current->leftSon, nodeL, mid, queryL, queryR) + query(current->rightSon, mid + 1, nodeR, queryL, queryR);
    }

public:
    PersistentSegTree() = default;

    PersistentSegTree(sizeType const n, std::vector<sizeType> const &source) : N(n), root(N + 1, nullptr) {
        root[0] = build(1, N);

        for (sizeType i = 1; i <= N; ++i)
            root[i] = insert(root[i - 1], 1, N, source[i]);
    }

    sizeType query(sizeType l, sizeType r, sizeType x, sizeType y) {
        return query(root[r], 1, N, x, y) - query(root[l - 1], 1, N, x, y);
    }

    bool check(sizeType l, sizeType r, sizeType x, sizeType y) {
        return query(l, r, x, y) > 0;
    }
};

template<typename _Compare = std::less<>>
class SparseTable {
private:
    valueType N, K;

    PairMatrix table;

    static valueType log2(valueType x) {
        return x == 0 ? 0 : std::__lg(x);
    }

public:
    SparseTable() = default;

    SparseTable(valueType const n, ValueVector const &source) : N(n), K(log2(N)), table(K + 1, PairVector(N + 1, std::make_pair(0, 0))) {
        for (valueType i = 1; i <= N; ++i)
            table[0][i] = std::make_pair(source[i], i);

        for (valueType k = 1; k <= K; ++k)
            for (valueType i = 1; i + (1 << (k - 1)) <= N; ++i)
                table[k][i] = std::min(table[k - 1][i], table[k - 1][i + (1 << (k - 1))], _Compare());
    }

    valueType query(valueType l, valueType r) {
        valueType const k = log2(r - l + 1);

        return std::min(table[k][l], table[k][r - (1 << k) + 1], _Compare()).first;
    }
};

std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::string const &S) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(2 * N + 1, 0), id, count;

    id.reserve(N);

    valueType M = 255;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);

    return std::make_pair(SA, rank);
}

template<typename Container_>
ValueVector GetHeight(valueType N, Container_ const &S, ValueVector const &SA, ValueVector const &rank) {
    ValueVector height(N + 1, 0);

    valueType pos = 0;

    for (valueType i = 1; i <= N; ++i) {
        if (rank[i] == 1)
            continue;
            
        if (pos > 0)
            --pos;

        while (i + pos < S.size() && SA[rank[i] - 1] + pos < S.size() && S[i + pos] == S[SA[rank[i] - 1] + pos])
            ++pos;

        height[rank[i]] = pos;
    }

    return height;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    std::string S;

    std::cin >> S;

    S = '#' + S;

    auto [SA, rank] = GetSuffixArray(N, S);
    auto height = GetHeight(N, S, SA, rank);

    PersistentSegTree Tree(N, rank);
    SparseTable<> ST(N, height);

    auto GetRange = [&](valueType x, valueType k) -> ValuePair {// found the max length range on height[] that contain x and all elements >= k
        valueType L = x, R = x;
        valueType l = 1, r = x - 1;

        while (l <= r) {
            valueType const mid = (l + r) >> 1;

            if (ST.query(mid + 1, x) >= k) {
                L = mid;

                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        l = x + 1, r = N;

        while (l <= r) {
            valueType const mid = (l + r) >> 1;

            if (ST.query(x + 1, mid) >= k) {
                R = mid;

                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return std::make_pair(L, R);
    };

    for (valueType m = 0; m < M; ++m) {
        valueType A, B, C, D;

        std::cin >> A >> B >> C >> D;

        valueType ans = 0;

        valueType l = 1, r = std::min(B - A + 1, D - C + 1);

        while (l <= r) {
            valueType mid = (l + r) >> 1;

            auto [L, R] = GetRange(rank[C], mid);

            if (Tree.check(A, B - mid + 1, L, R)) {
                ans = mid;

                l = mid + 1;
            } else
                r = mid - 1;
        }

        std::cout << ans << '\n';
    }

    std::cout << std::flush;

    return 0;
}

[AHOI2013] 差异

对于算式的前半部分可以化简为常数,对于后半部分可以转化为 \(\operatorname{height}\) 数组上的所有区间的最小值之和,使用单调栈维护即可。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::stack<ValuePair> PairStack;

std::pair<ValueVector, ValueVector> GetSuffixArray(valueType N, std::string const &S) {// 1 - index
    ValueVector SA(2 * N + 1, 0), rank(N + 1, 0), id, count;

    id.reserve(N);

    valueType M = 255;

    count.resize(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        ++count[rank[i] = S[i]];

    std::partial_sum(count.begin(), count.end(), count.begin());

    for (valueType i = N; i >= 1; --i)
        SA[count[rank[i]]--] = i;

    for (valueType w = 1; M != N || w == 1; w <<= 1) {
        id.clear();

        id.push_back(0);

        for (valueType i = N - w + 1; i <= N; ++i)
            id.push_back(i);

        for (valueType i = 1; i <= N; ++i)
            if (SA[i] > w)
                id.push_back(SA[i] - w);

        count.assign(M + 1, 0);

        for (valueType i = 1; i <= N; ++i)
            ++count[rank[id[i]]];

        std::partial_sum(count.begin(), count.end(), count.begin());

        for (valueType i = N; i >= 1; --i)
            SA[count[rank[id[i]]]--] = id[i];

        id = rank;

        M = 0;

        for (valueType i = 1; i <= N; ++i)
            rank[SA[i]] = (id[SA[i]] == id[SA[i - 1]] && id[SA[i] + w] == id[SA[i - 1] + w]) ? M : ++M;
    }

    SA.resize(N + 1);

    return std::make_pair(SA, rank);
}

template<typename Container_>
ValueVector GetHeight(valueType N, Container_ const &S, ValueVector const &SA, ValueVector const &rank) {
    ValueVector height(N + 1, 0);

    valueType pos = 0;

    for (valueType i = 1; i <= N; ++i) {
        if (rank[i] == 1)
            continue;

        if (pos > 0)
            --pos;

        while (i + pos < S.size() && SA[rank[i] - 1] + pos < S.size() && S[i + pos] == S[SA[rank[i] - 1] + pos])
            ++pos;

        height[rank[i]] = pos;
    }

    return height;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    string S;

    std::cin >> S;

    valueType const N = S.size();

    S = '#' + S;

    auto const [SA, rank] = GetSuffixArray(N, S);

    auto const height = GetHeight(N, S, SA, rank);

    valueType ans = (N + 1) * N * (N - 1) / 2;

    PairStack stack;
    valueType sum = 0;

    for (valueType i = 2; i <= N; ++i) {
        valueType count = 1;

        while (!stack.empty() && stack.top().first > height[i]) {
            auto const [h, c] = stack.top();

            stack.pop();

            sum -= h * c;

            count += c;
        }

        stack.emplace(height[i], count);

        sum += height[i] * count;

        ans -= 2 * sum;
    }

    std::cout << ans << std::endl;

    return 0;
}

标签:std,count,Set,const,2023.12,valueType,Solution,rank,SA
From: https://www.cnblogs.com/User-Unauthorized/p/2023-12-25.html

相关文章

  • 2023.12.25 近期练习
    CF1793F有一个朴素的想法,使用不删除莫队,使用一种数据结构维护相邻元素的差,\(O(n\sqrtq\logn)\)。可以通过链表加不增加莫队,维护最小值,使用值域分块,\(O(n\sqrtq+q\sqrtn)\)。即使如此,也因为常数过大无法通过。考虑使用扫描线,从右往左扫描区间,将询问挂到左端点上。大于小......
  • solution
    20232023.122023.12.25G2.LightBulbs(HardVersion)若干个区间的极小并,当且仅当这个区间包含了所有区间,当且仅当每个区间的左右点出现了一次,相当于某个标号恰好出现两次,可以用随机数来异或。因数个数小trick\[d(n)\%2=[n=k^2]\]当且仅当该数是完全平方数时,因数个数是奇......
  • 云原生周刊:Karmada 成为 CNCF 孵化项目 | 2023.12.25
    开源项目推荐kubernetes-reflectorReflector是一个Kubernetes的插件,旨在监视资源(secrets和configmaps)的变化,并将这些变化反映到同一命名空间或其他命名空间中的镜像资源中。LingoLingo是适用于K8s的OpenAI兼容LLM代理和自动缩放器。canary-checkercanary-checke......
  • 南外集训 2023.12.25 T1
    给定一个图,求\(s\)到\(t\)的最短路,其中路径的长度是其长度前\(k\)大边的长度和。\(n,k\le1000,m\le2000\)。做法枚举被算入的最小边权\(w\),所有小于\(w\)的边权都可以视为\(0\),而我们需要确保大于等于\(w\)的边至少走了\(k\)条。如何实现这一点呢?通过记录已......
  • collection List ArrayList HashSet
    1)collection实现子类可以存放多个元素,每个元素可以是Obiect2)有些Collection的实现类,可以存放重复的元素,有些不可以3)有些Collection的实现类,有些是有序的(List),有些不是有序(Set)4)Collection接口没有直接的实现子类,是通过它的子接口Set和List来实现的List接口基本介绍List接......
  • CF660E Different Subsets For All Tuples
    题意给定一个长度为\(n\)的序列。每个数字的范围为\([1,m]\)。求一共\(m^n\)种数列,每个数列种本质不同的子序列个数之和。Sol考虑用一种比较好的方式表示答案。枚举本质不同的子序列长度,枚举中间跳过的数的个数。\[m^n+\sum_{i=1}^n\sum_{j=0}^{n-i......
  • 控制台打印时显示的文件来源没有显示.vue文件,而是出现了一堆index.js??clonedRuleSet-
    控制台打印时显示的文件来源没有显示.vue文件,而是出现了一堆index.js??clonedRuleSet-40.use[0]!./node_modules/@vue/vue-loader-v15/lib/index.js??vue-loader-optio…,看不出来打印的语句来自哪个vue组件检查发现edge打印显示正常,谷歌打印是以上这样的,谷歌设置一下配置 ......
  • /opt/rh/devtoolset-9/root/usr/libexec/gcc/x86_64-redhat-linux/9/ld: 找不到 -lz
    我用的cmake命令是:target_link_libraries(${MyProjectName}-L/usr/lib64/mysql-lmysqlclient-lpthread-lz-lm-lssl-lcrypto-ldl) 将${MyProjectName}这个目标(可执行文件或库文件)链接到以下的库文件:/usr/lib64/mysql/libmysqlclient.so/usr/lib64/libpthread.so/usr/l......
  • ZROI 2023.12.24 T2
    很硬的题目!题意给出一棵\(n\)个点的树以及它以\(1\)为根时的一种DFS序,\(q\)组询问(强制在线):给定\(k\)个区间\([l_1,r_1],[l_2,r_2]\dots[l_k,r_k]\),问DFS序在这些区间内的点构成几个连通块。80分解法对\(k\)根号分治,\(k>\sqrt{n}\)直接暴力,\(k\le\sqrt{n}\)的......
  • 2023.12.24——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.软件案例分析明日计划:学习......