Kaito Nakano, [10/19/2024 7:54 PM]
#include <bits/stdc++.h>
using namespace std;

struct Interval
{
    int l, r;
    int min_p, max_p;
    bool operator<(const Interval &other) const
    {
        return l < other.l;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, q;
        cin >> n >> q;
        vector<int> p(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> p[i];
        // Build log table
        int LOG = 20;
        vector<vector<int>> st_min(LOG, vector<int>(n + 1));
        vector<vector<int>> st_max(LOG, vector<int>(n + 1));
        for (int i = 1; i <= n; i++)
        {
            st_min[0][i] = p[i];
            st_max[0][i] = p[i];
        }
        for (int k = 1; k < LOG; k++)
        {
            for (int i = 1; i + (1 << k) - 1 <= n; i++)
            {
                st_min[k][i] = min(st_min[k - 1][i], st_min[k - 1][i + (1 << (k - 1))]);
                st_max[k][i] = max(st_max[k - 1][i], st_max[k - 1][i + (1 << (k - 1))]);
            }
        }
        // Function to query min
        auto query_min = [&](int l, int r) -> int
        {
            int k = 31 - __builtin_clz(r - l + 1);
            return min(st_min[k][l], st_min[k][r - (1 << k) + 1]);
        };
        // Function to query max
        auto query_max = [&](int l, int r) -> int
        {
            int k = 31 - __builtin_clz(r - l + 1);
            return max(st_max[k][l], st_max[k][r - (1 << k) + 1]);
        };
        string s;
        cin >> s;
        // Initialize intervals
        set<Interval> intervals;
        int violation = 0;
        int l = 1;
        for (int i = 2; i <= n; i++)
        {
            if (s[i - 2] == 'R' s[i - 1] == 'L')
                continue;
            else
            {
                int r_i = i - 1;
                int mn = query_min(l, r_i);
                int mx = query_max(l, r_i);
                if (mn != l ||mx != r_i)
                {
                    violation++;
                }
                Interval itv = {l, r_i, mn, mx};
                intervals.insert(itv);
                l = i;
            }
        }
        // Last interval
        int r_i = n;
        int mn = query_min(l, r_i);
        int mx = query_max(l, r_i);
        if (mn != l  mx != r_i)
        {
            violation++;
        }
        Interval itv = {l, r_i, mn, mx};
        intervals.insert(itv);
        // Process queries
        while (q--)
        {
            int idx;
            cin >> idx;
            char old_s = s[idx - 1];
            s[idx - 1] = (s[idx - 1] == 'L') ? 'R' : 'L';
            // Connection between idx-1 and idx
            auto process = [&](int a, int b, bool add_conn) -> void
            {
                if (a < 1 or b > n or a >= b)
                    return;
                if (add_conn)
                {
                    // Merge intervals containing a and b
                    auto it1 = intervals.end();
                    auto it2 = intervals.end();
                    // Find interval containing a
                    auto it_a = intervals.lower_bound(Interval{a, 0, 0, 0});
                    if (it_a != intervals.end() && it_a->l == a)
                    {
                        it1 = it_a;
                    }
                    else
                    {
                        if (it_a == intervals.begin())
                            it1 = it_a;
                        else
                        {
                            it1 = prev(it_a);
                        }
                    }
                    if (!(it1->l <= a && a <= it1->r))
                        it1 = intervals.end();
                    // Find interval containing b
                    auto it_b = intervals.lower_bound(Interval{b, 0, 0, 0});
                    if (it_b != intervals.end() && it_b->l == b)
                    {
                        it2 = it_b;
                    }
                    else
                    {
                        if (it_b == intervals.begin())

Kaito Nakano, [10/19/2024 7:54 PM]
it2 = it_b;
                        else
                        {
                            it2 = prev(it_b);
                        }
                    }
                    if (!(it2->l <= b && b <= it2->r))
                        it2 = intervals.end();
                    if (it1 != intervals.end() && it2 != intervals.end() && it1 != it2)
                    {
                        // Check violation
                        if (it1->min_p != it1->l it1->max_p != it1->r)
                            violation--;
                        if (it2->min_p != it2->l   it2->max_p != it2->r)
                            violation--;
                        // Merge
                        int new_l = min(it1->l, it2->l);
                        int new_r = max(it1->r, it2->r);
                        int new_mn = query_min(new_l, new_r);
                        int new_mx = query_max(new_l, new_r);
                        Interval new_itv = {new_l, new_r, new_mn, new_mx};
                        if (new_mn != new_l new_mx != new_r)
                            violation++;
                        intervals.erase(it1);
                        intervals.erase(it2);
                        intervals.insert(new_itv);
                    }
                }
                else
                {
                    // Split intervals containing a and b
                    auto it = intervals.lower_bound(Interval{a, 0, 0, 0});
                    if (it == intervals.end() ||it->l > a)
                    {
                        if (it == intervals.begin())
                            return;
                        it = prev(it);
                    }
                    if (it->l <= a && a <= it->r)
                    {
                        if (it->l == it->r)
                            return;
                        // Split at a
                        Interval left = {it->l, a, query_min(it->l, a), query_max(it->l, a)};
                        Interval right = {a + 1, it->r, query_min(a + 1, it->r), query_max(a + 1, it->r)};
                        if (it->min_p != it->l   it->max_p != it->r)
                            violation--;
                            if (left.min_p != left.l  left.max_p != left.r)
                            violation++;
                        if (right.min_p != right.l  right.max_p != right.r)
                            violation++;
                        intervals.erase(it);
                        intervals.insert(left);
                        intervals.insert(right);
                    }
                }
            };
            // First connection: idx-1 and idx
            bool old_conn1 = (old_s == 'L')  (idx - 1 >= 1 && s[idx - 2] == 'R');
            bool new_conn1 = (s[idx - 1] == 'L')  (idx - 1 >= 1 && s[idx - 2] == 'R');
            if (old_conn1 != new_conn1)
            {
                if (new_conn1)
                {
                    process(idx - 1, idx, true);
                }
                else
                {
                    process(idx - 1, idx, false);
                }
            }
            // Second connection: idx and idx+1
            bool old_conn2 = (old_s == 'R')  (idx + 1 <= n && s[idx] == 'L');
            bool new_conn2 = (s[idx - 1] == 'R')  (idx + 1 <= n && s[idx] == 'L');
            if (old_conn2 != new_conn2)
            {
                if (new_conn2)
                {
                    // Merge
                    auto it1 = intervals.end();
                    auto it2 = intervals.end();
                    // Find interval containing idx
                    auto it_a = intervals.lower_bound(Interval{idx, 0, 0, 0});
                    if (it_a != intervals.end() && it_a->l == idx)
                    {
                        it1 = it_a;
                    }
                    else
                    {
                        if (it_a == intervals.begin())
                            it1 = it_a;
                        else
                        {

Kaito Nakano, [10/19/2024 7:54 PM]
it1 = prev(it_a);
                        }
                    }
                    if (!(it1->l <= idx && idx <= it1->r))
                        it1 = intervals.end();
                    // Find interval containing idx+1
                    auto it_b = intervals.lower_bound(Interval{idx + 1, 0, 0, 0});
                    if (it_b != intervals.end() && it_b->l == idx + 1)
                    {
                        it2 = it_b;
                    }
                    else
                    {
                        if (it_b == intervals.begin())
                            it2 = it_b;
                        else
                        {
                            it2 = prev(it_b);
                        }
                    }
                    if (!(it2->l <= idx + 1 && idx + 1 <= it2->r))
                        it2 = intervals.end();
                    if (it1 != intervals.end() && it2 != intervals.end() && it1 != it2)
                    {
                        // Check violation
                        if (it1->min_p != it1->l  it1->max_p != it1->r)
                            violation--;
                        if (it2->min_p != it2->l  it2->max_p != it2->r)
                            violation--;
                        // Merge
                        int new_l = min(it1->l, it2->l);
                        int new_r = max(it1->r, it2->r);
                        int new_mn = query_min(new_l, new_r);
                        int new_mx = query_max(new_l, new_r);
                        Interval new_itv = {new_l, new_r, new_mn, new_mx};
                        if (new_mn != new_l  new_mx != new_r)
                            violation++;
                        intervals.erase(it1);
                        intervals.erase(it2);
                        intervals.insert(new_itv);
                    }
                }
                else
                {
                    // Split
                    auto it = intervals.lower_bound(Interval{idx, 0, 0, 0});
                    if (it == intervals.end() ||it->l > idx)
                    {
                        if (it == intervals.begin())
                        {
                        }
                        else{
                            it = prev(it);
                        }
                    }
                    if (it->l <= idx && idx <= it->r)
                    {
                        if (it->l == it->r)
                        {
                        }
                        else
                        {
                            Interval left = {it->l, idx, query_min(it->l, idx), query_max(it->l, idx)};
                            Interval right = {idx + 1, it->r, query_min(idx + 1, it->r), query_max(idx + 1, it->r)};
                            if (it->min_p != it->l    it->max_p != it->r)
                                violation--;
                            if (left.min_p != left.l left.max_p != left.r)
                                violation++;
                            if (right.min_p != right.l  right.max_p != right.r)
                                violation++;
                            intervals.erase(it);
                            intervals.insert(left);
                            intervals.insert(right);
                        }
                    }
                }
            }
            // Check violation
            if (violation == 0)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
} Bu kodu elə yazki 0% plagiarism olsun, köçürdüyüm bilinməsin