#981753 (C++23) No.2002 Range Swap Query

• 問題: No.2002 Range Swap Query
• ユーザー: AC2K
• 提出日時: 2024-05-16 22:42:58
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: MLE
• 実行時間: -
• コード長: 9,775 bytes
• コンパイル時間: 3,200 ms
• コンパイル使用メモリ: 257,584 KB
• 実行使用メモリ: 713,892 KB
• 最終ジャッジ日時: 2024-12-20 11:13:23
• 合計ジャッジ時間: 25,368 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 13,640 KB
testcase_01	MLE	-
testcase_02	AC	2 ms; 13,640 KB
testcase_03	MLE	-
testcase_04	AC	2 ms; 13,636 KB
testcase_05	MLE	-
testcase_06	AC	2 ms; 13,632 KB
testcase_07	MLE	-
testcase_08	AC	3 ms; 13,636 KB
testcase_09	MLE	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	63 ms; 17,152 KB
testcase_21	MLE	-

ソースコード

#line 2 "Library/src/data-structure/segtree.hpp"
#include <cassert>
#include <vector>
namespace kyopro {


template <class S, auto op, auto e> class segtree {
    int lg, sz, n;
    std::vector<S> dat;

public:
    segtree() = default;
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& vec) : n((int)vec.size()) {
        sz = 1, lg = 0;
        while (sz <= n) {
            sz <<= 1;
            lg++;
        }

        dat = std::vector<S>(sz << 1, e());

        for (int i = 0; i < n; i++) {
            set(i, vec[i]);
        }
        build();
    }

    void set(int p, const S& v) {
        assert(0 <= p && p < sz);
        dat[sz + p] = v;
    }
    void build() {
        for (int i = sz - 1; i > 0; i--) {
            dat[i] = op(dat[i << 1 | 0], dat[i << 1 | 1]);
        }
    }

    S operator[](int p) const { return dat[sz + p]; }

    void update(int p, const S& v) {
        assert(0 <= p && p < sz);
        p += sz;
        dat[p] = v;
        while (p >>= 1) {
            dat[p] = op(dat[(p << 1) | 0], dat[(p << 1) | 1]);
        }
    }

    S fold(int l, int r) const {
        assert(0 <= l && l <= r && r <= sz);
        if (l == 0 && r == n) {
            return dat[1];
        }
        l += sz, r += sz;
        S sml = e(), smr = e();
        while (l != r) {
            if (l & 1) sml = op(sml, dat[l++]);
            if (r & 1) smr = op(dat[--r], smr);
            l >>= 1, r >>= 1;
        }
        return op(sml, smr);
    }
    void apply(int p, const S& v) {
        assert(0 <= p && p < sz);
        update(p, op(dat[sz + p], v));
    }
};
};  // namespace kyopro

/**
 * @brief Segment Tree
 */
#line 1 "Library/src/debug.hpp"
#ifdef ONLINE_JUDGE
#define debug(x) void(0)
#else
#define _GLIBCXX_DEBUG
#define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl
#endif

/**
 * @brief Debugger
*/
#line 2 "Library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 2 "Library/src/internal/type_traits.hpp"
#include <iostream>
#include <limits>
#include <numeric>
#include <typeinfo>
#include <cstdint>

namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};

template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
    using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
    : first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
    using type = T;
};

template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
                                 std::enable_if<dgt <= 16, std::int16_t>,
                                 std::enable_if<dgt <= 32, std::int32_t>,
                                 std::enable_if<dgt <= 64, std::int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t>>;
};

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
                                 std::enable_if<dgt <= 16, std::uint16_t>,
                                 std::enable_if<dgt <= 32, std::uint32_t>,
                                 std::enable_if<dgt <= 64, std::uint64_t>,
                                 std::enable_if<dgt <= 128, __uint128_t>>;
};

template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;

template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;

template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;

struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;


// is_integral
template <typename T>
using is_integral_t =
    std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
                   std::is_same_v<T, __uint128_t>>;
};  // namespace internal
};  // namespace kyopro

/**
 * @brief Type Traits
 * @see https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
 */
#line 6 "Library/src/stream.hpp"

namespace kyopro {

inline void single_read(char& c) {
    c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_read(T& a) {
    a = 0;
    bool is_negative = false;
    char c = getchar_unlocked();
    while (isspace(c)) {
        c = getchar_unlocked();
    }
    if (c == '-') is_negative = true, c = getchar_unlocked();
    while (isdigit(c)) {
        a = 10 * a + (c - '0');
        c = getchar_unlocked();
    }
    if (is_negative) a *= -1;
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_read(T& a) {
    long long x;
    single_read(x);
    a = T(x);
}
inline void single_read(std::string& str) noexcept {
    char c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
    while (!isspace(c)) {
        str += c;
        c = getchar_unlocked();
    }
}
template<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
    single_read(head), read(tail...);
}

inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
    if (!a) {
        putchar_unlocked('0');
        return;
    }
    if constexpr (std::is_signed_v<T>) {
        if (a < 0) putchar_unlocked('-'), a *= -1;
    }
    constexpr int d = std::numeric_limits<T>::digits10;
    char s[d + 1];
    int now = d + 1;
    while (a) {
        s[--now] = (char)'0' + a % 10;
        a /= 10;
    }
    while (now <= d) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_write(T a) noexcept {
    single_write(a.val());
}
inline void single_write(const std::string& str) noexcept {
    for (auto c : str) {
        putchar_unlocked(c);
    }
}
template <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
    single_write(head);
    putchar_unlocked(' ');
    write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
    write(x...);
    putchar_unlocked('\n');
}
};  // namespace kyopro

/**
 * @brief Fast IO(高速入出力)
 */
#line 2 "Library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) std::begin(x), std::end(x)
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::max() / 2;
const long double pi = acosl(-1);
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
    return a > b && (a = b, true);
}

/**
 * @brief Template
*/
#line 5 "a.cpp"

using namespace std;
using namespace kyopro;

int main() {
    int n, k, q;
    read(n, k, q);

    vector<P> swaps(k);
    rep(i, k) {
        read(swaps[i].first, swaps[i].second);
        --swaps[i].first, --swaps[i].second;
    }
    reverse(all(swaps));

    const int sq = sqrt(k);
    const int blocks = (k + sq - 1) / sq;
    vector agg(blocks, vector<int>(n));
    
    debug(sq);
    debug(blocks);

    rep(i, blocks) {
        iota(all(agg[i]), 0);
        int l = i * sq, r = min(k, (i + 1) * sq);
        for (int j = l; j < r; ++j) {
            swap(agg[i][swaps[j].first], agg[i][swaps[j].second]);
        }
    }

    while (q--) {
        int l, r, x;
        read(l, r, x);
        --x;
        --l, --r;
        r = k - r - 1, l = k - l - 1;
        swap(l, r);
        ++r;

        // debug(l);
        // debug(r);
        // debug(x + 1);

        int pos = 0;
        int lblock = l / sq, rblock = r / sq;
        int lp = l - lblock * sq, rp = r - rblock * sq;
        
        if (lblock == rblock) {
            int p = x;
            while (l < r) {
                auto [a, b] = swaps[l];
                if (p == a) {
                    p = b;
                } else if (p == b) {
                    p = a;
                }
                ++l;
            }
            put(p + 1);
        } else {
            int p = x;

            while (lp < sq) {
                auto [a, b] = swaps[l];
                if (p == a) {
                    p = b;
                } else if (p == b) {
                    p = a;
                }

                ++lp, ++l;
            }
            //debug(lblock);

            while (++lblock < rblock) {
                // debug(lblock);
                p = agg[lblock][p];
            }


            for (int j = sq * rblock; j < r; ++j) {
                auto [a, b] = swaps[j];
                if (p == a) {
                    p = b;
                } else if (p == b) {
                    p = a;
                }
            }
            
            
            put(p + 1);
        }
    }
}