QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649554#9425. Generated Stringucup-team004TL 4ms4288kbC++2311.7kb2024-10-18 01:50:552024-10-18 01:50:56

Judging History

你现在查看的是最新测评结果

  • [2024-10-18 01:50:56]
  • 评测
  • 测评结果：TL
  • 用时：4ms
  • 内存：4288kb
查看
  • [2024-10-18 01:50:55]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
struct SuffixArray {
    int n;
    std::vector<int> sa, rk, lc;
    SuffixArray(const std::string &s) {
        n = s.length();
        sa.resize(n);
        lc.resize(n - 1);
        rk.resize(n);
        std::iota(sa.begin(), sa.end(), 0);
        std::sort(sa.begin(), sa.end(),
            [&](int a, int b) {
                return s[a] < s[b];
            });
        rk[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        }
        int k = 1;
        std::vector<int> tmp, cnt(n);
        tmp.reserve(n);
        while (rk[sa[n - 1]] < n - 1) {
            tmp.clear();
            for (int i = 0; i < k; i++) {
                tmp.push_back(n - k + i);
            }
            for (auto i : sa) {
                if (i >= k) {
                    tmp.push_back(i - k);
                }
            }
            std::fill(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; i++) {
                cnt[rk[i]]++;
            }
            for (int i = 1; i < n; i++) {
                cnt[i] += cnt[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
                sa[--cnt[rk[tmp[i]]]] = tmp[i];
            }
            std::swap(rk, tmp);
            rk[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
            }
            k *= 2;
        }
        for (int i = 0, j = 0; i < n; i++) {
            if (rk[i] == 0) {
                j = 0;
            } else {
                for (j -= (j > 0); i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; j++)
                    ;
                lc[rk[i] - 1] = j;
            }
        }
    }
};

template<class T,
    class Cmp = std::less<T>>
struct RMQ {
    const Cmp cmp = Cmp();
    static constexpr unsigned B = 64;
    using u64 = unsigned long long;
    int n;
    std::vector<std::vector<T>> a;
    std::vector<T> pre, suf, ini;
    std::vector<u64> stk;
    RMQ() {}
    RMQ(const std::vector<T> &v) {
        init(v);
    }
    void init(const std::vector<T> &v) {
        n = v.size();
        pre = suf = ini = v;
        stk.resize(n);
        if (!n) {
            return;
        }
        const int M = (n - 1) / B + 1;
        const int lg = std::__lg(M);
        a.assign(lg + 1, std::vector<T>(M));
        for (int i = 0; i < M; i++) {
            a[0][i] = v[i * B];
            for (int j = 1; j < B && i * B + j < n; j++) {
                a[0][i] = std::min(a[0][i], v[i * B + j], cmp);
            }
        }
        for (int i = 1; i < n; i++) {
            if (i % B) {
                pre[i] = std::min(pre[i], pre[i - 1], cmp);
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (i % B != B - 1) {
                suf[i] = std::min(suf[i], suf[i + 1], cmp);
            }
        }
        for (int j = 0; j < lg; j++) {
            for (int i = 0; i + (2 << j) <= M; i++) {
                a[j + 1][i] = std::min(a[j][i], a[j][i + (1 << j)], cmp);
            }
        }
        for (int i = 0; i < M; i++) {
            const int l = i * B;
            const int r = std::min(1U * n, l + B);
            u64 s = 0;
            for (int j = l; j < r; j++) {
                while (s && cmp(v[j], v[std::__lg(s) + l])) {
                    s ^= 1ULL << std::__lg(s);
                }
                s |= 1ULL << (j - l);
                stk[j] = s;
            }
        }
    } 
    T operator()(int l, int r) {
        if (l / B != (r - 1) / B) {
            T ans = std::min(suf[l], pre[r - 1], cmp);
            l = l / B + 1;
            r = r / B;
            if (l < r) {
                int k = std::__lg(r - l);
                ans = std::min({ans, a[k][l], a[k][r - (1 << k)]}, cmp);
            }
            return ans;
        } else {
            int x = B * (l / B);
            return ini[__builtin_ctzll(stk[r - 1] >> (l - x)) + l];
        }
    }
};
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;
    
    std::string s;
    std::cin >> s;
    
    std::vector<std::vector<std::array<int, 2>>> a1, a2;
    std::vector<std::array<int, 2>> qry(q);
    for (int i = 0; i < q; i++) {
        char o;
        std::cin >> o;
        
        if (o == '+') {
            int k;
            std::cin >> k;
            std::vector<std::array<int, 2>> b1(k), b2(k);
            for (int j = 0; j < k; j++) {
                int l, r;
                std::cin >> l >> r;
                l--;
                b1[j] = {l, r};
                b2[k - 1 - j] = {n - r, n - l};
            }
            qry[i] = {1, int(a1.size())};
            a1.push_back(b1);
            a2.push_back(b2);
        } else if (o == '-') {
            int t;
            std::cin >> t;
            t--;
            qry[i] = {2, qry[t][1]};
        } else {
            int k;
            std::cin >> k;
            std::vector<std::array<int, 2>> b1(k);
            for (int j = 0; j < k; j++) {
                int l, r;
                std::cin >> l >> r;
                l--;
                b1[j] = {l, r};
            }
            std::cin >> k;
            std::vector<std::array<int, 2>> b2(k);
            for (int j = 0; j < k; j++) {
                int l, r;
                std::cin >> l >> r;
                l--;
                b2[k - 1 - j] = {n - r, n - l};
            }
            qry[i] = {3, int(a1.size())};
            a1.push_back(b1);
            a2.push_back(b2);
        }
    }
    
    auto get = [&](auto &a) -> std::array<std::vector<int>, 2> {
        int m = a.size();
        std::vector<int> in(m), out(m);
        
        if (m == 0) {
            return {in, out};
        }
        
        SuffixArray sa(s);
        std::vector<int> ord(m);
        std::iota(ord.begin(), ord.end(), 0);
        std::sort(ord.begin(), ord.end(),
            [&](int i, int j) {
                return a[i].size() < a[j].size();
            });
        RMQ rmq(sa.lc);
        
        auto lcp = [&](int i, int j) {
            if (i == j) {
                return n - i;
            }
            i = sa.rk[i];
            j = sa.rk[j];
            if (i > j) {
                std::swap(i, j);
            }
            return rmq(i, j);
        };
        
        i64 len;
        auto cmp = [&](int x, int y) {
            int i = 0, j = 0;
            len = 0;
            int ex = 0, ey = 0;
            while (i < a[x].size() && j < a[y].size()) {
                auto [lx, rx] = a[x][i];
                auto [ly, ry] = a[y][j];
                lx += ex;
                ly += ey;
                int t = std::min({lcp(lx, ly), rx - lx, ry - ly});
                len += t;
                if (t < std::min(rx - lx, ry - ly)) {
                    return s[lx + t] < s[ly + t];
                }
                ex += t;
                ey += t;
                lx += t;
                ly += t;
                if (lx == rx) {
                    i++;
                    ex = 0;
                }
                if (ly == ry) {
                    j++;
                    ey = 0;
                }
            }
            if (j < a[y].size()) {
                return true;
            }
            if (i < a[x].size()) {
                return false;
            }
            return x < y;
        };
        std::set<int, decltype(cmp)> set(cmp);
        for (auto i : ord) {
            set.insert(i);
        }
        
        std::vector o(set.begin(), set.end());
        std::vector<i64> lc(m - 1);
        std::vector<i64> tot(m);
        for (int i = 0; i < m; i++) {
            for (auto [l, r] : a[i]) {
                tot[i] += r - l;
            }
        }
        for (int i = 0; i < m - 1; i++) {
            cmp(o[i], o[i + 1]);
            lc[i] = len;
        }
        
        std::vector<int> stk;
        for (int i = 0; i < m - 1; i++) {
            i64 l = tot[o[i + 1]];
            while (!stk.empty() && lc[i] <= lc[stk.back()]) {
                stk.pop_back();
            }
            in[o[i + 1]] = lc[i] < l ? i + 1 : stk.empty() ? 0 : stk.back() + 1;
            stk.push_back(i);
        }
        out[o[m - 1]] = m;
        stk.clear();
        for (int i = m - 2; i >= 0; i--) {
            i64 l = tot[o[i]];
            while (!stk.empty() && lc[i] <= lc[stk.back()]) {
                stk.pop_back();
            }
            out[o[i]] = lc[i] < l ? i + 1 : stk.empty() ? m : stk.back() + 1;
            stk.push_back(i);
        }
        
        return {in, out};
    };
    
    auto [in1, out1] = get(a1);
    std::reverse(s.begin(), s.end());
    auto [in2, out2] = get(a2);
    
    std::vector<int> ans(q);
    
    std::vector<std::array<int, 4>> e;
    
    for (int i = 0; i < q; i++) {
        auto [o, x] = qry[i];
        if (o == 1) {
            e.push_back({in1[x], in2[x], i, 1});
        } else if (o == 2) {
            e.push_back({in1[x], in2[x], i, -1});
        } else {
            e.push_back({in1[x], in2[x], i, 1});
            e.push_back({in1[x], out2[x], i, -1});
            e.push_back({out1[x], in2[x], i, -1});
            e.push_back({out1[x], out2[x], i, 1});
        }
    }
    
    Fenwick<int> fen(q);
    auto work = [&](auto &&self, int l, int r, int vl, int vr) -> void {
        if (vr - vl == 1 || l == r) {
            return;
        }
        int vm = (vl + vr) / 2;
        int m = std::stable_partition(e.begin(), e.end(),
            [&](auto &&a) {
                return a[0] < vm;
            }) - e.begin();
        int j = l;
        for (int i = m; i < r; i++) {
            if (qry[e[i][2]][0] != 3) {
                continue;
            }
            while (j < m && e[j][1] < e[i][1]) {
                if (qry[e[j][2]][0] != 3) {
                    fen.add(e[j][2], e[j][3]);
                }
                j++;
            }
            ans[e[i][2]] += fen.sum(e[i][2]) * e[i][3];
        }
        while (j > l) {
            j--;
            if (qry[e[j][2]][0] != 3) {
                fen.add(e[j][2], -e[j][3]);
            }
        }
        self(self, l, m, vl, vm);
        self(self, m, r, vm, vr);
    };
    std::sort(e.begin(), e.end(),
        [&](auto &&a, auto &&b) {
            return a[1] < b[1];
        });
    work(work, 0, e.size(), 0, a1.size() + 1);
    
    for (int i = 0; i < q; i++) {
        if (qry[i][0] == 3) {
            std::cout << ans[i] << "\n";
        }
    }
    
    return 0;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3552kb

input:

8 7
abcaabbc
+ 3 1 3 2 4 3 8
+ 2 1 4 1 8
+ 1 2 4
? 1 5 6 1 7 8
- 3
+ 1 2 5
? 1 2 3 1 5 5

output:

2
1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 4ms
memory: 4060kb

input:

5 2000
bbaab
+ 1 3 5
+ 2 5 5 3 5
- 2
? 1 1 3 3 3 3 4 5 2 5
- 1
? 3 1 1 2 4 1 5 1 3 4
? 1 1 2 2 2 4 4 4
? 1 1 5 1 5 5
+ 3 1 2 1 5 1 4
? 2 1 5 1 3 2 1 2 5 5
? 1 3 4 1 4 5
- 9
? 1 1 4 1 2 3
+ 2 1 5 1 2
+ 1 1 4
- 15
- 14
? 2 2 5 2 5 1 3 4
+ 1 2 3
- 19
+ 3 1 4 1 5 4 5
- 21
+ 1 2 5
? 3 1 5 5 5 1 5 1 3 5
?...

output:

0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
2
0
3
1
0
0
0
0
1
0
0
0
0
0
0
0
0
2
0
0
0
0
0
1
0
0
0
0
0
0
0
3
1
0
1
0
2
0
0
0
3
0
1
0
0
2
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
2
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
3
2
3
0
0
0
0
0
2
0
0
2
0
0
0
2
3
...

result:

ok 702 lines

Test #3:

score: 0
Accepted
time: 3ms
memory: 3996kb

input:

5 2000
ababa
+ 1 4 4
+ 1 2 2
? 1 1 2 2 3 3 3 3
? 2 3 3 1 2 1 3 4
+ 2 3 4 2 2
+ 1 3 3
+ 1 2 2
+ 1 1 2
- 7
- 1
- 2
? 2 4 4 3 3 2 2 2 4 4
- 5
+ 1 1 1
- 6
? 1 3 4 2 1 2 4 5
+ 1 4 5
- 17
? 2 1 1 1 2 2 1 1 1 2
- 8
+ 2 3 4 2 3
+ 1 4 5
+ 1 2 3
+ 1 3 4
- 21
+ 1 3 3
? 1 1 2 1 4 4
? 2 1 1 4 5 1 5 5
- 24
- 22
?...

output:

0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
2
0
3
1
0
1
0
0
2
0
0
2
0
2
0
3
3
2
4
0
0
0
0
0
0
4
0
0
4
2
1
1
0
0
1
3
2
0
0
0
2
2
0
2
0
0
0
0
0
1
0
3
1
1
0
2
9
0
1
1
1
0
5
8
1
1
1
0
0
5
4
4
4
6
6
0
6
6
1
5
0
3
5
1
0
0
1
8
0
5
0
5
0
3
0
0
0
1
0
1
1
1
1
1
0
0
0
1
5
2
0
2
6
5
1
4
0
0
7
0
2
6
1
5
0
5
0
9
0
0
0
0
1
0
0
...

result:

ok 647 lines

Test #4:

score: 0
Accepted
time: 3ms
memory: 4288kb

input:

5 2000
bbaba
+ 1 3 3
- 1
+ 2 2 2 1 1
- 3
+ 1 4 4
? 1 3 3 1 2 2
+ 2 2 2 1 1
- 5
? 2 4 4 1 1 2 3 3 3 3
- 7
+ 1 5 5
+ 2 2 2 2 2
+ 1 5 5
- 11
+ 2 2 2 1 1
? 1 3 3 1 2 2
+ 1 1 1
+ 1 2 2
+ 1 3 3
- 17
- 19
+ 1 1 1
+ 1 3 3
? 1 3 3 1 3 3
+ 1 5 5
? 1 4 4 1 4 4
- 22
+ 1 5 5
+ 1 1 1
? 2 5 5 3 3 1 1 1
? 1 5 5 1 1...

output:

0
0
0
2
4
0
0
2
5
0
4
0
1
8
0
0
1
6
0
4
7
0
2
0
4
0
0
0
6
1
1
0
0
6
0
9
1
7
0
1
1
0
0
1
7
1
0
1
2
9
0
1
2
2
0
0
2
7
0
4
2
8
2
8
0
1
0
2
0
9
10
1
1
2
1
1
0
0
10
0
0
0
6
0
0
2
4
0
5
4
5
5
5
0
4
0
3
2
2
5
5
5
5
0
0
0
4
0
3
5
5
6
9
6
6
4
6
0
4
6
0
4
4
2
2
12
0
5
6
6
6
13
0
13
2
1
0
1
10
10
5
8
1
8
8
1
1...

result:

ok 672 lines

Test #5:

score: -100
Time Limit Exceeded

input:

5 100000
bbabb
+ 1 2 5
? 5 4 5 3 5 4 5 2 4 4 5 3 1 5 3 4 3 4
? 2 4 4 1 5 1 1 3
? 1 3 5 5 1 1 1 3 1 1 4 4 3 5
? 1 2 5 2 2 5 2 5
+ 2 1 5 3 3
- 1
+ 4 1 5 1 5 1 5 2 3
? 4 3 5 1 5 1 5 2 5 1 2 4
? 1 1 5 3 4 4 3 4 1 5
- 6
- 8
+ 2 1 5 1 4
- 13
? 1 1 5 3 1 2 3 4 1 3
+ 5 2 4 1 2 1 4 2 2 1 5
- 16
+ 1 1 5
- 18
...

output:

result:
English 繁體中文 简体中文

伺服器時間: 2024-11-29 20:42:02 | 開源專案