#910191 (C++17(gcc12)) No.2454 Former < Latter

• 問題: No.2454 Former < Latter
• ユーザー: cutmdo
• 提出日時: 2023-09-01 23:18:24
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,351 ms / 2,000 ms
• コード長: 16,101 bytes
• コンパイル時間: 15,863 ms
• コンパイル使用メモリ: 337,124 KB
• 最終ジャッジ日時: 2025-02-16 17:23:31
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 1
other	AC * 23

ソースコード

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <cassert>
#include <memory>
#include <random>
#include <functional>
#include <complex>
#include <immintrin.h>
#include <stdexcept>
#ifdef DEBUG
#include "./CompetitiveProgrammingCpp/Utils/debug.hpp"
#include "./CompetitiveProgrammingCpp/Utils/Timer.hpp"
#include "./CompetitiveProgrammingCpp/Utils/sample.hpp"
#else
#define dump(...)
template<class T>constexpr inline auto d_val(T a, T b) { return a; }
#endif

/* macro */
#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)((e)-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, (n))
#define RREP(i, n) RFOR(i, 0, (n))
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
/* macro func */
template<class T>
inline auto sort(T& t) { std::sort(ALL(t)); }
template<class T>
inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); }
template<class T, class S>
inline auto chmax(T& t, const S& s) { if(s > t) { t = s; return true; } return false; }
template<class T, class S>
inline auto chmin(T& t, const S& s) { if(s < t) { t = s; return true; } return false; }
inline auto BR() { std::cout << "\n"; }

/* type define */
using ll = long long;
template<class T>
using V = std::vector<T>;
using VS = V<std::string>;
using VL = V<ll>;
using VVL = V<VL>;
template<class T = ll, class U = T>
using P = std::pair<T, U>;
using PAIR = P<ll>;

/* using std */
using std::cout;
using std::cin;
using std::cerr;
constexpr char endl = '\n';

/* Initial processing  */
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;

/* define hash */
constexpr unsigned int static_random() { return 1u * __TIME__[0] * __TIME__[1] * __TIME__[3] * __TIME__[4] * __TIME__[6] * __TIME__[7]; }
template<class T> struct Hash { auto operator()(T x) const { return std::hash<T>()(x) ^ static_random(); } };
template<> struct Hash<std::pair<int, int>> { auto operator()(const std::pair<int, int>& x) const { return Hash<long long>()(x.first << 31 | x.second); } };

/* input */
template<class T> std::istream& operator >> (std::istream& is, std::vector<T>& vec) { for(T& x : vec) is >> x; return is; }

/* constant value */
// constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;

//=============================================================================================




template <class Lambda>
auto binarySearch(long long mn, long long mx, const Lambda& judge, bool rev = false) {
    auto ok = mx + rev;
    auto ng = mn - 1;
    while(ok - ng > 1) {
        auto mid = (ok + ng) / 2;
        auto isOk = judge(mid);
        if((isOk && !rev) || (!isOk && rev)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok - rev;
}

class SuffixArray {
    enum class TYPE {
        L, S, LMS
    };

    const std::string m_str;
    const std::vector<int> m_suffixArray;

    /* string to vector<int> */
    static std::vector<int> toIntVec(const std::string& str) {
        std::vector<int> vec;
        vec.reserve(str.size() + 1);
        for(const auto& c : str) {
            vec.emplace_back(c - '0' + 1);
        }
        vec.emplace_back(0);
        return vec;
    }

    /* classify { L, S, LMS } */
    static std::vector<TYPE> classifying(const std::vector<int>& str) {
        auto sz = str.size();
        auto typeArray = std::vector<TYPE>(sz);
        typeArray[sz - 1] = TYPE::S;
        for(int i = sz - 2; i >= 0; --i) {
            if(str[i] == str[i + 1]) {
                typeArray[i] = typeArray[i + 1];
                continue;
            }
            typeArray[i] = (str[i] < str[i + 1]) ? TYPE::S : TYPE::L;
        }
        for(int i = 1; i < sz; ++i) {
            if(typeArray[i - 1] == TYPE::L && typeArray[i] == TYPE::S) {
                typeArray[i] = TYPE::LMS;
            }
        }
        return typeArray;
    }

    /* induced sort */
    static std::vector<int> inducedSort(const std::vector<int>& str, const std::vector<TYPE>& type, std::list<int>& lmsList) {
        auto sz = str.size();
        auto nList = std::set<int>();
        for(const auto& c : str) { nList.emplace(c); }

        auto befCheck = [&](int k, auto& addList, bool rev) {
            if(k == 0) { return; }
            if(!rev && type[k - 1] == TYPE::L) {
                addList[str[k - 1]].emplace_back(k - 1);
            }
            if(rev && type[k - 1] != TYPE::L) {
                addList[str[k - 1]].emplace_front(k - 1);
            }
        };

        auto checkAndUpdate = [&](int n, auto& checkList, auto& addList, bool rev) {
            auto& lst = checkList[n];
            if(rev) {
                for(auto itr = lst.rbegin(); itr != lst.rend(); ++itr) { befCheck(*itr, addList, rev); }
            } else {
                for(const auto& k : lst) { befCheck(k, addList, rev); }
            }
        };

        /* set LMS */
        auto tailList = std::unordered_map<int, std::list<int>>();
        for(const auto& i : lmsList) { tailList[str[i]].emplace_back(i); }

        /* set L-type */
        auto headList = std::unordered_map<int, std::list<int>>();
        for(const auto& n : nList) {
            checkAndUpdate(n, headList, headList, false);
            checkAndUpdate(n, tailList, headList, false);
        }

        /* set S-type*/
        tailList = std::unordered_map<int, std::list<int>>();
        for(auto itr_n = nList.rbegin(); itr_n != nList.rend(); ++itr_n) {
            auto n = *itr_n;
            checkAndUpdate(n, tailList, tailList, true);
            checkAndUpdate(n, headList, tailList, true);
        }

        /* merge */
        auto suffixArray = std::vector<int>();
        suffixArray.reserve(sz);
        for(const auto& n : nList) {
            for(const auto& c : headList[n]) { suffixArray.emplace_back(c); }
            for(const auto& c : tailList[n]) { suffixArray.emplace_back(c); }
        }

        return suffixArray;
    }

    /* order lms -> sorted lms */
    static std::unordered_map<int, int> getLmsChanger(const std::vector<int>& str, const std::vector<TYPE>& type, const std::list<int>& lms) {
        if(lms.size() == 1) { return std::unordered_map<int, int>{ { str.size() - 1, 0 }}; }
        std::unordered_map<int, int> changer{{static_cast<int>(str.size()) - 1,0},{*++lms.begin(),1}};
        int num = 1;
        for(auto itr = ++lms.begin(); itr != (--lms.end());) {
            auto f1 = *itr;
            auto f2 = *(++itr);

            bool isSame = false;
            for(int i = 0;; ++i) {
                if(str[f1 + i] != str[f2 + i]) { break; }
                auto b1 = (type[f1 + i] == TYPE::LMS);
                auto b2 = (type[f2 + i] == TYPE::LMS);
                if((b1 || b2) && i > 0) {
                    if(b1 && b2) { isSame = true; break; }
                    break;
                }
            }
            if(!isSame) { ++num; }
            changer.emplace(f2, num);
        }
        return changer;
    }

    /* calc Suffix Array*/
    static std::vector<int> constructSuffixArray(const std::vector<int>& str) {
        auto type = classifying(str);

        /* calc fake Suffix Array using order seed*/
        auto lmsOrder = [&type]() {
            auto lms = std::list<int>();
            for(int i = 0; i < type.size(); ++i) if(type[i] == TYPE::LMS) { lms.emplace_back(i); }
            return lms;
        }();
        auto fakeArray = inducedSort(str, type, lmsOrder);

        /* calc true seed */
        auto lmsFakeOrder = [&fakeArray, &type]() {
            auto lms = std::list<int>();
            lms.emplace_back(static_cast<int>(type.size()) - 1);
            for(const auto& i : fakeArray) if(type[i] == TYPE::LMS) { lms.emplace_back(i); }
            return lms;
        }();
        auto changer = getLmsChanger(str, type, lmsFakeOrder);
        auto& lmsTrueOrder = lmsFakeOrder;
        if(changer[*lmsFakeOrder.rbegin()] + 1 < lmsFakeOrder.size()) {
            /* exist same lms-substring */
            auto str = std::vector<int>();
            auto def = std::vector<int>();
            str.reserve(lmsOrder.size());
            def.reserve(lmsOrder.size());
            for(const auto& c : lmsOrder) {
                str.emplace_back(changer[c]);
                def.emplace_back(c);
            }
            auto lmsSuffixArray = constructSuffixArray(str);
            lmsTrueOrder = std::list<int>{static_cast<int>(type.size()) - 1};
            for(const auto& c : lmsSuffixArray) {
                lmsTrueOrder.emplace_back(def[c]);
            }
        }

        /* calc true Suffix Array using true seed */
        auto suffixArray = inducedSort(str, type, lmsTrueOrder);

        return suffixArray;
    }

public:
    SuffixArray(const std::string& str) :m_str(str), m_suffixArray(constructSuffixArray(toIntVec(str))) {}

    /**
     * 引数として与えられたpattern出現位置の区間を返す
     */
    std::pair<int, int> findPattern(const std::string& pattern) const {

        auto find = [&](const std::string& ptn) {
            int end = m_suffixArray.size();
            int ptn_sz = ptn.size();
            auto ret = binarySearch(0, end, [&](int mid) {
                int st = m_suffixArray[mid];
                int sub_sz = end - st;
                for(int k = 0; k < std::min(ptn_sz, sub_sz); ++k) {
                    if(ptn[k] < m_str[st + k]) { return true; }
                    if(ptn[k] > m_str[st + k]) { return false; }
                }
                return ptn_sz <= sub_sz;
            });
            return ret;
        };
        auto patternUpper = [&pattern]() {
            auto ptn = pattern;
            ++* ptn.rbegin();
            return ptn;
        }();
        auto fl = find(pattern);
        auto fu = find(patternUpper);
        return {fl,fu};
    }

    auto getSuffixArray() const {
        return m_suffixArray;
    }

    /* output fot debug */
    void debugOutput() const {
        for(const auto& x : m_suffixArray) {
            std::cout << x << " ";
        }std::cout << std::endl;
        auto end = m_str.size();
        for(const auto& x : m_suffixArray) {
            std::cout << m_str.substr(x, end) << std::endl;
        }
    }
};

class LCPArray {

    const std::vector<int> m_lcpArray;
    const std::vector<int> m_suffixArray;

    static std::vector<int> constructLcpArray(const std::string& str) {
        auto sz = str.size();
        const auto suffixArray = SuffixArray(str).getSuffixArray();

        auto rank = std::vector<int>(sz);
        for(int i = 0; i < sz; ++i) { rank[suffixArray[i]] = i; }

        auto lcpArray = std::vector<int>(sz - 1);
        for(int i = 0, h = 0; i < sz; ++i) {
            if(rank[i] == 0) { continue; }
            int j = suffixArray[rank[i] - 1];
            if(h > 0) { --h; }
            for(; j + h < sz && i + h < sz; ++h) {
                if(str[i + h] != str[j + h]) { break; }
            }
            lcpArray[rank[i] - 1] = h;
        }
        return lcpArray;
    }

public:
    LCPArray(const std::string& str) :
        m_suffixArray(SuffixArray(str).getSuffixArray()),
        m_lcpArray(constructLcpArray(str)) {
    }

    auto getLCPArray()const { return m_lcpArray; }
    auto getSuffixArray()const { return m_suffixArray; }
    auto getSuffixArrayIndexList()const {
        std::vector<int> sail(m_suffixArray.size());
        for(unsigned int i = 0; i < m_suffixArray.size(); ++i) {
            sail[m_suffixArray[i]] = i;
        }
        return sail;
    }
};

template <class SG>
class DisjointSparseTable {

    using S = decltype(SG::Type());

    const int m_n;
    const std::vector<std::vector<SG>> m_table;

    static auto accumulation(int n, const std::vector<S>& a, int l, int r) {
        auto mid = (r + l) >> 1;
        r = std::min(n, r);
        int size = r - l;
        std::vector<SG> acc; acc.reserve(size);
        for(int i = l; i < r; ++i) { acc.emplace_back(a[i]); }
        for(int i = mid - 2; i >= l; --i) if(i - l + 1 < size) {
            acc[i - l] = acc[i - l].binaryOperation(acc[i - l + 1]);
        }
        for(int i = mid + 1; i < r; ++i)if(i - l - 1 >= 0) {
            acc[i - l] = acc[i - l - 1].binaryOperation(acc[i - l]);
        }
        return acc;
    }

    static auto constructTable(int n, const std::vector<S>& a) {
        std::vector<std::vector<SG>> table; table.reserve(std::log2(n) + 1);
        table.emplace_back(a.begin(), a.end());

        auto size = 1;
        while(size < n) {
            size <<= 1;
            std::vector<SG> acc; acc.reserve(n);
            for(int l = 0; l < n; l += size) for(const auto& x : accumulation(n, a, l, l + size)) {
                acc.emplace_back(x);
            }
            table.emplace_back(acc);
        }
        return table;
    }

    static auto msb(int x) {
        auto idx = 0;
        while(x > 0) { ++idx; x >>= 1; }
        return idx;
    }
public:
    DisjointSparseTable(int n, const std::vector<S>& a) :m_n(n), m_table(constructTable(n, a)) {}

    auto get(int l, int r)const {
        if(r < l) { throw std::runtime_error("ERROR! `l` must less than `r`"); }
        l = std::max(l, 0); r = std::min(r, m_n - 1);
        if(l == r) { return m_table[0][l].m_val; }
        auto idx = msb(l ^ r);
        return m_table[idx][l].binaryOperation(m_table[idx][r]).m_val;
    }
};
template<
    class S,// 要素の型
    class T // 2項演算子
>
struct SemiGroup {
    static inline auto Type() { return S(); }
    S m_val;
    SemiGroup(S val) :m_val(val) {}
    SemiGroup binaryOperation(const SemiGroup& m2)const { return T()(m_val, m2.m_val); }
    friend std::ostream& operator<<(std::ostream& os, const SemiGroup<S, T>& m) {
        return os << m.m_val;
    }
};
struct Functor { auto operator()(int a, int b)const { return std::min(a, b); } };
using SG = SemiGroup<int, Functor>;

auto solve_c(ll n, const std::string& s) {
    ll ans = 0;
    FOR(i, 1, n) {
        auto a = s.substr(0, i);
        auto b = s.substr(i, n);
        ans += (a < b);
    }
    return ans;
}
auto solve(ll n, const std::string& s) {
    auto lcp_ = LCPArray(s);
    auto sai = lcp_.getSuffixArrayIndexList();
    auto lcpa = lcp_.getLCPArray();
    auto dst = DisjointSparseTable<SG>(n - 1, lcpa);

    ll ans = 0;
    FOR(i, 1, n) {
        if(sai[i] > sai[0]) {
            ++ans;
        } else if(i < ((n + 1) >> 1)) {
            auto lcp = dst.get(sai[i], sai[0] - 1);
            ans += lcp >= i;
        }
    }
    // SuffixArray(s).debugOutput();

    return ans;
}

signed main() {
    #ifndef TEST
    ll t;
    cin >> t;
    REP(_, t) {
        ll n;
        std::string s;
        cin >> n >> s;
        cout << solve(n, s) << endl;
    }
    #else
    auto gen = Sample::SampleGenerator();
    auto g = [&]() {
        constexpr ll size = 7;
        constexpr ll max = 3;
        auto [n, s] = gen.generate_string(PAIR{2,size}, max);
        return std::make_tuple(n, s);
    };
    auto out = [](ll n, const std::string& s) {
        cout << 1 << endl;
        cout << n << endl;
        cout << s << endl;
        cout << "-- solve --" << endl;
        cout << solve(n, s) << endl;
        cout << solve_c(n, s) << endl;
    };
    auto runner = Sample::RandomCaseDebugger();
    runner.compare(10000, g, out, solve, solve_c);
    #endif
}