結果
問題 | No.1787 Do Use Dynamic Tree |
ユーザー |
|
提出日時 | 2024-04-27 22:50:24 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,820 ms / 10,000 ms |
コード長 | 20,625 bytes |
コンパイル時間 | 3,196 ms |
コンパイル使用メモリ | 272,636 KB |
実行使用メモリ | 37,760 KB |
最終ジャッジ日時 | 2024-11-16 06:00:44 |
合計ジャッジ時間 | 29,484 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
/*** date : 2024-04-27 22:50:18* author : Nyaan*/#define NDEBUG#define PROBLEM "https://yukicoder.me/problems/no/1787"//using namespace std;// intrinstic#include <immintrin.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cfenv>#include <cfloat>#include <chrono>#include <cinttypes>#include <climits>#include <cmath>#include <complex>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <initializer_list>#include <iomanip>#include <ios>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <streambuf>#include <string>#include <tuple>#include <type_traits>#include <typeinfo>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>// utilitynamespace Nyaan {using ll = long long;using i64 = long long;using u64 = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;template <typename T>using V = vector<T>;template <typename T>using VV = vector<vector<T>>;using vi = vector<int>;using vl = vector<long long>;using vd = V<double>;using vs = V<string>;using vvi = vector<vector<int>>;using vvl = vector<vector<long long>>;template <typename T>using minpq = priority_queue<T, vector<T>, greater<T>>;template <typename T, typename U>struct P : pair<T, U> {template <typename... Args>P(Args... args) : pair<T, U>(args...) {}using pair<T, U>::first;using pair<T, U>::second;P &operator+=(const P &r) {first += r.first;second += r.second;return *this;}P &operator-=(const P &r) {first -= r.first;second -= r.second;return *this;}P &operator*=(const P &r) {first *= r.first;second *= r.second;return *this;}template <typename S>P &operator*=(const S &r) {first *= r, second *= r;return *this;}P operator+(const P &r) const { return P(*this) += r; }P operator-(const P &r) const { return P(*this) -= r; }P operator*(const P &r) const { return P(*this) *= r; }template <typename S>P operator*(const S &r) const {return P(*this) *= r;}P operator-() const { return P{-first, -second}; }};using pl = P<ll, ll>;using pi = P<int, int>;using vp = V<pl>;constexpr int inf = 1001001001;constexpr long long infLL = 4004004004004004004LL;template <typename T>int sz(const T &t) {return t.size();}template <typename T, typename U>inline bool amin(T &x, U y) {return (y < x) ? (x = y, true) : false;}template <typename T, typename U>inline bool amax(T &x, U y) {return (x < y) ? (x = y, true) : false;}template <typename T>inline T Max(const vector<T> &v) {return *max_element(begin(v), end(v));}template <typename T>inline T Min(const vector<T> &v) {return *min_element(begin(v), end(v));}template <typename T>inline long long Sum(const vector<T> &v) {return accumulate(begin(v), end(v), 0LL);}template <typename T>int lb(const vector<T> &v, const T &a) {return lower_bound(begin(v), end(v), a) - begin(v);}template <typename T>int ub(const vector<T> &v, const T &a) {return upper_bound(begin(v), end(v), a) - begin(v);}constexpr long long TEN(int n) {long long ret = 1, x = 10;for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);return ret;}template <typename T, typename U>pair<T, U> mkp(const T &t, const U &u) {return make_pair(t, u);}template <typename T>vector<T> mkrui(const vector<T> &v, bool rev = false) {vector<T> ret(v.size() + 1);if (rev) {for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];} else {for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];}return ret;};template <typename T>vector<T> mkuni(const vector<T> &v) {vector<T> ret(v);sort(ret.begin(), ret.end());ret.erase(unique(ret.begin(), ret.end()), ret.end());return ret;}template <typename F>vector<int> mkord(int N, F f) {vector<int> ord(N);iota(begin(ord), end(ord), 0);sort(begin(ord), end(ord), f);return ord;}template <typename T>vector<int> mkinv(vector<T> &v) {int max_val = *max_element(begin(v), end(v));vector<int> inv(max_val + 1, -1);for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;return inv;}vector<int> mkiota(int n) {vector<int> ret(n);iota(begin(ret), end(ret), 0);return ret;}template <typename T>T mkrev(const T &v) {T w{v};reverse(begin(w), end(w));return w;}template <typename T>bool nxp(T &v) {return next_permutation(begin(v), end(v));}// 返り値の型は入力の T に依存// i 要素目 : [0, a[i])template <typename T>vector<vector<T>> product(const vector<T> &a) {vector<vector<T>> ret;vector<T> v;auto dfs = [&](auto rc, int i) -> void {if (i == (int)a.size()) {ret.push_back(v);return;}for (int j = 0; j < a[i]; j++) v.push_back(j), rc(rc, i + 1), v.pop_back();};dfs(dfs, 0);return ret;}// F : function(void(T&)), mod を取る操作// T : 整数型のときはオーバーフローに注意するtemplate <typename T>T Power(T a, long long n, const T &I, const function<void(T &)> &f) {T res = I;for (; n; f(a = a * a), n >>= 1) {if (n & 1) f(res = res * a);}return res;}// T : 整数型のときはオーバーフローに注意するtemplate <typename T>T Power(T a, long long n, const T &I = T{1}) {return Power(a, n, I, function<void(T &)>{[](T &) -> void {}});}template <typename T>T Rev(const T &v) {T res = v;reverse(begin(res), end(res));return res;}template <typename T>vector<T> Transpose(const vector<T> &v) {using U = typename T::value_type;int H = v.size(), W = v[0].size();vector res(W, T(H, U{}));for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) {res[j][i] = v[i][j];}}return res;}template <typename T>vector<T> Rotate(const vector<T> &v, int clockwise = true) {using U = typename T::value_type;int H = v.size(), W = v[0].size();vector res(W, T(H, U{}));for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) {if (clockwise) {res[W - 1 - j][i] = v[i][j];} else {res[j][H - 1 - i] = v[i][j];}}}return res;}} // namespace Nyaan// bit operationnamespace Nyaan {__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {return __builtin_popcountll(a);}inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }template <typename T>inline int gbit(const T &a, int i) {return (a >> i) & 1;}template <typename T>inline void sbit(T &a, int i, bool b) {if (gbit(a, i) != b) a ^= T(1) << i;}constexpr long long PW(int n) { return 1LL << n; }constexpr long long MSK(int n) { return (1LL << n) - 1; }} // namespace Nyaan// inoutnamespace Nyaan {template <typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &p) {os << p.first << " " << p.second;return os;}template <typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p) {is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &v) {int s = (int)v.size();for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v) {for (auto &x : v) is >> x;return is;}istream &operator>>(istream &is, __int128_t &x) {string S;is >> S;x = 0;int flag = 0;for (auto &c : S) {if (c == '-') {flag = true;continue;}x *= 10;x += c - '0';}if (flag) x = -x;return is;}istream &operator>>(istream &is, __uint128_t &x) {string S;is >> S;x = 0;for (auto &c : S) {x *= 10;x += c - '0';}return is;}ostream &operator<<(ostream &os, __int128_t x) {if (x == 0) return os << 0;if (x < 0) os << '-', x = -x;string S;while (x) S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}ostream &operator<<(ostream &os, __uint128_t x) {if (x == 0) return os << 0;string S;while (x) S.push_back('0' + x % 10), x /= 10;reverse(begin(S), end(S));return os << S;}void in() {}template <typename T, class... U>void in(T &t, U &...u) {cin >> t;in(u...);}void out() { cout << "\n"; }template <typename T, class... U, char sep = ' '>void out(const T &t, const U &...u) {cout << t;if (sizeof...(u)) cout << sep;out(u...);}struct IoSetupNya {IoSetupNya() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(15);cerr << fixed << setprecision(7);}} iosetupnya;} // namespace Nyaan// debug#ifdef NyaanDebug#define trc(...) (void(0))#else#define trc(...) (void(0))#endif#ifdef NyaanLocal#define trc2(...) (void(0))#else#define trc2(...) (void(0))#endif// macro#define each(x, v) for (auto&& x : v)#define each2(x, y, v) for (auto&& [x, y] : v)#define all(v) (v).begin(), (v).end()#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)#define reg(i, a, b) for (long long i = (a); i < (b); i++)#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)#define fi first#define se second#define ini(...) \int __VA_ARGS__; \in(__VA_ARGS__)#define inl(...) \long long __VA_ARGS__; \in(__VA_ARGS__)#define ins(...) \string __VA_ARGS__; \in(__VA_ARGS__)#define in2(s, t) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i]); \}#define in3(s, t, u) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i]); \}#define in4(s, t, u, v) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i], v[i]); \}#define die(...) \do { \Nyaan::out(__VA_ARGS__); \return; \} while (0)namespace Nyaan {void solve();}int main() { Nyaan::solve(); }//namespace DynamicRerootingImpl {template <typename Point, Point (*rake)(const Point &, const Point &)>struct SplayTreeforDashedEdge {struct Node {Node *l, *r, *p;Point key, sum;explicit Node(const Point &_key): l(nullptr), r(nullptr), p(nullptr), key(_key), sum(_key) {}};SplayTreeforDashedEdge() {}using NP = Node *;void rotr(NP t) {NP x = t->p, y = x->p;if ((x->l = t->r)) t->r->p = x;t->r = x, x->p = t;update(x), update(t);if ((t->p = y)) {if (y->l == x) y->l = t;if (y->r == x) y->r = t;}}void rotl(NP t) {NP x = t->p, y = x->p;if ((x->r = t->l)) t->l->p = x;t->l = x, x->p = t;update(x), update(t);if ((t->p = y)) {if (y->l == x) y->l = t;if (y->r == x) y->r = t;}}void update(NP t) {t->sum = t->key;if (t->l) t->sum = rake(t->sum, t->l->sum);if (t->r) t->sum = rake(t->sum, t->r->sum);}NP get_right(NP t) {while (t->r) t = t->r;return t;}NP alloc(const Point &v) {auto t = new Node(v);update(t);return t;}void splay(NP t) {while (t->p) {NP q = t->p;if (!q->p) {if (q->l == t)rotr(t);elserotl(t);} else {NP r = q->p;if (r->l == q) {if (q->l == t)rotr(q), rotr(t);elserotl(t), rotr(t);} else {if (q->r == t)rotl(q), rotl(t);elserotr(t), rotl(t);}}}}NP insert(NP t, const Point &v) {if (not t) {t = alloc(v);return t;} else {NP cur = get_right(t), z = alloc(v);splay(cur);z->p = cur;cur->r = z;update(cur);splay(z);return z;}}NP erase(NP t) {splay(t);NP x = t->l, y = t->r;delete t;if (not x) {t = y;if (t) t->p = nullptr;} else if (not y) {t = x;t->p = nullptr;} else {x->p = nullptr;t = get_right(x);splay(t);t->r = y;y->p = t;update(t);}return t;}};template <typename Path, typename Point, typename Info,Path (*vertex)(const Info &),Path (*compress)(const Path &, const Path &),Point (*rake)(const Point &, const Point &),Point (*add_edge)(const Path &),Path (*add_vertex)(const Point &, const Info &)>struct TopTree {private:struct Node {Node *l, *r, *p;Info info;Path key, sum, mus;typename SplayTreeforDashedEdge<Point, rake>::Node *light, *belong;bool rev;bool is_root() const { return not p or (p->l != this and p->r != this); }explicit Node(const Info _info): l(nullptr),r(nullptr),p(nullptr),info(_info),light(nullptr),belong(nullptr),rev(false) {}};public:using NP = Node *;SplayTreeforDashedEdge<Point, rake> splay_tree;private:void toggle(NP t) {swap(t->l, t->r);swap(t->sum, t->mus);t->rev ^= true;}void rotr(NP t) {NP x = t->p, y = x->p;push(x), push(t);if ((x->l = t->r)) t->r->p = x;t->r = x, x->p = t;update(x), update(t);if ((t->p = y)) {if (y->l == x) y->l = t;if (y->r == x) y->r = t;}}void rotl(NP t) {NP x = t->p, y = x->p;push(x), push(t);if ((x->r = t->l)) t->l->p = x;t->l = x, x->p = t;update(x), update(t);if ((t->p = y)) {if (y->l == x) y->l = t;if (y->r == x) y->r = t;}}public:TopTree() : splay_tree{} {}void push(NP t) {if (t->rev) {if (t->l) toggle(t->l);if (t->r) toggle(t->r);t->rev = false;}}void push_rev(NP t) {if (t->rev) {if (t->l) toggle(t->l);if (t->r) toggle(t->r);t->rev = false;}}void update(NP t) {Path key = t->light ? add_vertex(t->light->sum, t->info) : vertex(t->info);Path sum = key, mus = key;if (t->l) sum = compress(t->l->sum, sum), mus = compress(mus, t->l->mus);if (t->r) sum = compress(sum, t->r->sum), mus = compress(t->r->mus, mus);t->key = key, t->sum = sum, t->mus = mus;}void splay(NP t) {push(t);{NP rot = t;while (not rot->is_root()) rot = rot->p;t->belong = rot->belong;if (t != rot) rot->belong = nullptr;}while (not t->is_root()) {NP q = t->p;if (q->is_root()) {push_rev(q), push_rev(t);if (q->l == t)rotr(t);elserotl(t);} else {NP r = q->p;push_rev(r), push_rev(q), push_rev(t);if (r->l == q) {if (q->l == t)rotr(q), rotr(t);elserotl(t), rotr(t);} else {if (q->r == t)rotl(q), rotl(t);elserotr(t), rotl(t);}}}}NP expose(NP t) {NP rp = nullptr;for (NP cur = t; cur; cur = cur->p) {splay(cur);if (cur->r) {cur->light = splay_tree.insert(cur->light, add_edge(cur->r->sum));cur->r->belong = cur->light;}cur->r = rp;if (cur->r) {splay_tree.splay(cur->r->belong);push(cur->r);cur->light = splay_tree.erase(cur->r->belong);}update(cur);rp = cur;}splay(t);return rp;}void link(NP child, NP parent) {expose(parent);expose(child);child->p = parent;parent->r = child;update(parent);}void cut(NP child) {expose(child);NP parent = child->l;child->l = nullptr;parent->p = nullptr;update(child);}void evert(NP t) {expose(t);toggle(t);push(t);}NP alloc(const Info &info) {NP t = new Node(info);update(t);return t;}bool is_connected(NP u, NP v) {expose(u), expose(v);return u == v or u->p;}NP lca(NP u, NP v) {if (not is_connected(u, v)) return nullptr;expose(u);return expose(v);}void set_key(NP t, const Info &v) {expose(t);t->info = v;update(t);}// u を根とする sumPath query(NP u) {evert(u);return u->sum;}// root を根, u を部分木の根とする sumPath query_subtree(NP root, NP u) {evert(root);expose(u);NP l = u->l;u->l = nullptr;update(u);auto ret = u->sum;u->l = l;update(u);return ret;}};template <typename Path, typename Point, typename Info,Path (*vertex)(const Info &),Path (*compress)(const Path &, const Path &),Point (*rake)(const Point &, const Point &),Point (*Add_edge)(const Path &),Path (*add_vertex)(const Point &, const Info &)>struct DynamicRerooting {int n;TopTree<Path, Point, Info, vertex, compress, rake, Add_edge, add_vertex> tt;using NP = typename decltype(tt)::NP;vector<NP> vs;DynamicRerooting(int _n, const vector<Info> &info) : n(_n), vs(n) {for (int i = 0; i < n; i++) vs[i] = tt.alloc(info[i]);}// u-v 間に辺を追加void add_edge(int u, int v) {tt.evert(vs[u]);tt.link(vs[u], vs[v]);}// u-v 間の辺を削除void del_edge(int u, int v) {tt.evert(vs[u]);tt.cut(vs[v]);}// 頂点 u の情報を取得Info get_info(int u) { return vs[u]->info; }// 頂点 u の情報を設定void set_info(int u, const Info &info) { tt.set_key(vs[u], info); }// 頂点 u を根とするクエリPath query(int u) { return tt.query(vs[u]); }// 頂点 root を根, 頂点 u を部分木の根とするクエリPath query_subtree(int root, int u) {return tt.query_subtree(vs[root], vs[u]);}};} // namespace DynamicRerootingImplusing DynamicRerootingImpl::DynamicRerooting;using DynamicRerootingImpl::TopTree;/*struct Path {};struct Point {};struct Info {};Path vertex(const Info &i) {}Path compress(const Path &p, const Path &c) {}Point rake(const Point &a, const Point &b) {}Point add_edge(const Path &a) {}Path add_vertex(const Point &a, const Info &i) {}using DR = DynamicRerooting<Path, Point, Info, vertex, compress, rake, add_edge,add_vertex>;*/using namespace Nyaan;struct Path {int val, idx, all, tail;};struct Point {int val, idx;};struct Info {int val, idx;};Path vertex(const Info &i) {Path r;r.val = i.val;r.idx = i.idx;r.all = true;r.tail = -1;return r;}Path compress(const Path &p, const Path &c) {Path r;r.val = p.val;r.tail = c.tail;if (p.all) {if (p.tail > c.val) {r.idx = p.idx;r.all = false;} else {r.idx = c.idx;r.all = c.all;}} else {r.idx = p.idx;r.all = false;}return r;}Point rake(const Point &a, const Point &b) { return a.val > b.val ? a : b; }Point add_edge(const Path &a) { return {a.val, a.idx}; }Path add_vertex(const Point &a, const Info &i) {return {i.val, a.idx, true, a.val};}using DR = DynamicRerooting<Path, Point, Info, vertex, compress, rake, add_edge,add_vertex>;void q() {ini(N);V<Info> init(N);rep(i, N) init[i].idx = init[i].val = i;DR dr(N, init);rep(i, N - 1) {ini(a, b);--a, --b;dr.add_edge(a, b);}ini(Q);int x = 0;rep(_, Q) {ini(u, v);u = (u + N - 1 + x) % N;v = (v + N - 1 + x) % N;auto uinfo = dr.get_info(u);auto vinfo = dr.get_info(v);swap(uinfo.val, vinfo.val);dr.set_info(v, vinfo);dr.set_info(u, uinfo);auto p = dr.query(u);out(x = p.idx + 1);}}void Nyaan::solve() {int t = 1;// in(t);while (t--) q();}