线段树只对hack求调
查看原帖
线段树只对hack求调
1129046
lkrkerry楼主2024/6/8 10:06
#include <bits/stdc++.h>

using namespace std;

#include <vector>
#include <cassert>

template <typename Value, typename Lazy>

class LazySegmentTree
{
    // Lazy: operator +=
    // Value: operator += +
    int n;
    std::vector<Value> value;
    std::vector<Lazy> lazy;

    constexpr inline int ls(const int x)
    {
        return x * 2 + 1;
    }
    constexpr inline int rs(const int x)
    {
        return x * 2 + 2;
    }

    constexpr void push_down(const int x)
    {
        value[ls(x)] += lazy[x]; // add(acatually need to add all the sons)
        value[rs(x)] += lazy[x];
        lazy[ls(x)] += lazy[x]; // push down
        lazy[rs(x)] += lazy[x];
        lazy[x] = Lazy(); // reset the lazy tag
    }

    void set(const int x, const int l, const int r, const int L, const int R, const Lazy &K)
    {
        if (L <= l && r <= R)
        {
            lazy[x] += K;
            value[x] += K;
            return;
        }
        int m = (l + r) / 2;
        push_down(x);
        if (L < m)
            set(ls(x), l, m, L, R, K);
        if (R > m)
            set(rs(x), m, r, L, R, K);
        value[x] = value[ls(x)] + value[rs(x)]; // update
    }
    Value get(const int x, const int l, const int r, const int L, const int R)
    {
        if (L <= l && r <= R)
            return value[x];
        int m = (l + r) / 2;
        push_down(x);
        if (R <= m)
            return get(ls(x), l, m, L, R);
        if (L >= m)
            return get(rs(x), m, r, L, R);
        return get(ls(x), l, m, L, R) + get(rs(x), m, r, L, R);
    }

public:
    void set(const int l, const int r, const Lazy &k)
    {
        set(0, 0, n, l, r, k);
    }
    void set(const int p, const Lazy &k)
    {
        set(p, p + 1, k);
    }
    void set(const Lazy &k)
    {
        value[0] += k, lazy[0] += k;
    }
    Value get(const int l, const int r)
    {
        return get(0, 0, n, l, r);
    }
    Value get(const int p)
    {
        return get(p, p + 1);
    }
    Value get()
    {
        return value[0];
    }

    LazySegmentTree(const int n)
        : LazySegmentTree(n, std::vector<Value>(n * 4)) {}
    LazySegmentTree(const int n, std::vector<Value> init)
        : n(n), value(n * 4), lazy(n * 4)
    {
        assert(init.size() == n);
        auto build = [&](auto self, const int x, const int l, const int r)
        {
            if (l + 1 == r)
            {
                value[x] = init[l];
                return;
            }
            int m = (l + r) / 2;
            self(self, this->ls(x), l, m), self(self, this->rs(x), m, r);
            value[x] = value[this->ls(x)] + value[this->rs(x)];
        };
        build(build, 0, 0, n);
    }
};

struct l
{
    int ta, tb, tc;
    l(char x = ' ') : ta(0), tb(0), tc(0)
    {
        switch (x)
        {
        case 'A':
            ta = 1;
            break;
        case 'B':
            tb = 1;
            break;
        case 'C':
            tc = 1;
            break;
        }
    }
    l operator+=(const l &rhs)
    {
        *this = rhs;
        return *this;
    }
};

struct v
{
    int va, vb, vc, sz;
    v(int va = 0, int vb = 0, int vc = 0, int sz = 1)
        : va(va), vb(vb), vc(vc), sz(sz) {}
    v(char c) : v(c == 'A', c == 'B', c == 'C', 1) {}
    v operator+=(const l &rhs)
    {
        if (rhs.ta || rhs.tb || rhs.tc)
        {
            va = rhs.ta * sz;
            vb = rhs.tb * sz;
            vc = rhs.tc * sz;
        }
        return *this;
    }
};

v operator+(const v &lhs, const v &rhs)
{
    return v(lhs.va + rhs.va, lhs.vb + rhs.vb, lhs.vc + rhs.vc, lhs.sz + rhs.sz);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<v> init;
    for (auto x : s)
    {
        init.emplace_back(x);
    }
    auto tree = LazySegmentTree<v, l>(n, init);
    int m;
    cin >> m;
    while (m--)
    {
        char op, k;
        int x, y;
        cin >> op >> x >> y;
        switch (op)
        {
        case 'A':
            cin >> k;
            tree.set(x - 1, y, l(k));
            break;
        case 'B':
            if (x > 1 && y < n)
            {
                auto be = tree.get(x - 2), en = tree.get(y);
                if ((be.va == en.va && be.va) || (be.vb == en.vb && be.vb) || (be.vc == en.vc && be.vc))
                {
                    cout << "No\n";
                    break;
                }
            }
            auto ans = tree.get(x - 1, y);
            if (max({ans.va, ans.vb, ans.vc}) == (y - x + 1))
            {
                cout << "Yes\n";
            }
            else
            {
                cout << "No\n";
            }
            break;
        }
    }
    return 0;
}
2024/6/8 10:06
加载中...