| #define _CRT_SECURE_NO_WARNINGS |
| #include <iostream> |
| #include <iomanip> |
| #include <stdio.h> |
| #include <algorithm> |
| #include <math.h> |
| #include <numeric> |
| #include <iterator> |
| #include <fstream> |
| #include <math.h> |
| #include <random> |
| #include <vector> |
| #include <string> |
| #include <stack> |
| #include <set> |
| #include <map> |
| #include <deque> |
| #include <queue> |
| #include <list> |
| #include <bitset> |
| #include <unordered_set> |
| #include <unordered_map> |
| #include <random> |
| #include <ctime> |
| #pragma GCC optimize("Ofast") |
| #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") |
| using namespace std; |
| typedef long long ll; |
| typedef unsigned long long ull; |
| typedef long double ld; |
| #define FOR(i, from, to) for (int i = from; i < to; i++) |
| #define ROF(i, from, to) for (int i = from; i > to; i--) |
| const long double PI = 3.141592653589793238463; |
| const int INF = 0x3f3f3f3f; |
| const int INFS = 1000000000; |
| const ll M = 1000000007; |
| const ll LLINF = 1000000000000000000; |
| const double EPS = 1e-8; |
| #define int long long |
| struct treap { |
| int y, sz, val, delta, pos; |
| treap * l, * r, * prev = nullptr; |
| treap(int _val) { |
| val = _val; |
| y = rand(); |
| sz = 1; |
| delta = 0; |
| pos = 0; |
| l = nullptr; |
| r = nullptr; |
| } |
| }; |
| int get_sz(treap * t) { |
| if (t == nullptr) |
| return 0; |
| return t->sz; |
| } |
| void push(treap * & t) { |
| if (t != nullptr) { |
| if (t->l != nullptr) |
| t->l->delta += t->delta; |
| if (t->r != nullptr) |
| t->r->delta += t->delta; |
| t->pos += t->delta; |
| t->delta = 0; |
| } |
| } |
| void update(treap * t) { |
| if (t == nullptr) { return; } |
| t->sz = 1 + get_sz(t->l) + get_sz(t->r); |
| if (t->l != nullptr) |
| t->l->prev = t; |
| if (t->r != nullptr) |
| t->r->prev = t; |
| } |
| treap * merge(treap * t1, treap * t2) { |
| push(t1); |
| push(t2); |
| if (t1 == nullptr) |
| return t2; |
| if (t2 == nullptr) |
| return t1; |
| if (t1->y > t2->y) { |
| t1->r = merge(t1->r, t2); |
| update(t1); |
| return t1; |
| } else { |
| t2->l = merge(t1, t2->l); |
| update(t2); |
| return t2; |
| } |
| } |
| void split(treap * t, int x, treap * & t1, treap * & t2) { |
| push(t); |
| if (t == nullptr) { |
| t1 = t2 = nullptr; |
| return; |
| } |
| if (get_sz(t->l) < x) { |
| split(t->r, x - get_sz(t->l) - 1, t->r, t2); |
| t1 = t; |
| } else { |
| split(t->l, x, t1, t->l); |
| t2 = t; |
| } |
| update(t); |
| } |
| void swp(treap * & t, int l1, int r1, int l2, int r2) { |
| treap * t1, * t2, * t3, * t4, * t5, * t6, * t7, * t8; |
| split(t, r2 + 1, t1, t2); |
| split(t1, l2, t3, t4); |
| split(t3, r1 + 1, t5, t6); |
| split(t5, l1, t7, t8); |
| t8->delta += l2 - l1; |
| t4->delta -= l2 - l1; |
| t = merge(merge(merge(merge(t7, t4), t6), t8), t2); |
| } |
| void update_up(treap * curr) { |
| if (curr == nullptr) |
| return; |
| update_up(curr->prev); |
| push(curr); |
| } |
| int get(treap * curr, int pos) { |
| if (get_sz(curr->l) == pos) { |
| return curr->val; |
| } else if (get_sz(curr->l) > pos) { |
| return get(curr->l, pos); |
| } else { |
| return get(curr->r, pos - get_sz(curr->l) - 1); |
| } |
| } |
| void upd(treap * & curr, int pos, int val) { |
| if (get_sz(curr->l) == pos) { |
| curr->val = val; |
| } else if (get_sz(curr->l) > pos) { |
| upd(curr->l, pos, val); |
| } else { |
| upd(curr->r, pos - get_sz(curr->l) - 1, val); |
| } |
| } |
| void print(treap * t) { |
| if (t == nullptr) |
| return; |
| print(t->l); |
| cout << t->val << ' '; |
| print(t->r); |
| } |
| signed main() { |
| ios_base::sync_with_stdio(0); |
| cin.tie(NULL); |
| cout.tie(NULL); |
| int n, m, k; |
| cin >> n >> m >> k; |
| vector<pair<int, int> > qs(k); |
| vector<int> x(n), a(n), b(n), d(m, 0); |
| treap * root = nullptr; |
| treap * root2 = nullptr; |
| FOR(i, 0, n) { |
| cin >> x; |
| root = merge(root, new treap(i)); |
| } |
| FOR(i, 0, m) |
| root2 = merge(root2, new treap(0)); |
| reverse(qs.begin(), qs.end()); |
| int curr = 0, c, c2, p, p2, c3, p3; |
| for (auto q : qs) { |
| if (q.first == 2) { |
| if (q.second < 0) { |
| c = (n - ((-q.second) % n)); |
| } else { |
| c = q.second % n; |
| } |
| p = n - c - 1; |
| c2 = (curr + get(root2, m)) % m; |
| if (c2 != 0) { |
| p2 = (p - (p % m)) + m - 1 - c2; |
| swp(root, p2 - (p2 % m), p2, p2 + 1, (p2 - (p2 % m)) + m - 1); |
| upd(root2, m, -curr); |
| } |
| c3 = (n - 1 - p); |
| if (c3 != 0) { |
| p3 = (m) - c3 - 1; |
| swp(root2, 0, p3, p3 + 1, (m) - 1); |
| } |
| if (c != 0) { |
| swp(root, 0, p, p + 1, n - 1); |
| } |
| } else { |
| if (q.second < 0) { |
| c = (m - ((-q.second) % m)); |
| } else { |
| c = q.second % m; |
| } |
| curr += c; |
| } |
| print(root); |
| cout << endl; |
| print(root2); |
| cout << endl; |
| cout << curr << endl; |
| } |
| FOR(i, 0, m) { |
| c2 = (curr + get(root2, i)) % m; |
| if (c2 != 0) { |
| p2 = (i + 1) * m - 1 - c2; |
| swp(root, p2 - (p2 % m), p2, p2 + 1, (p2 - (p2 % m)) + m - 1); |
| } |
| } |
| return 0; |
| } |
Комментарии