Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <list>
- #include <unordered_map>
- #include <unordered_set>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef string str;
- //typedef __int128 ultraint;
- #define endl "\n"
- #define sqrt sqrtl
- #define F first
- #define S second
- #define all(vc666) vc666.begin(), vc666.end()
- #define pow binpow
- //#define Vec Point
- const ll inf = (ll)1e18 + 7;
- ld EPS = 1e-9;
- ld Pi = 3.1415926535897932384;
- const ll max_sz = 1e5 + 1;
- ll binpow(ll a, ll n) {
- ll res = 1;
- while (n) {
- if (n & 1) {
- res *= a;
- }
- a *= a;
- n >>= 1;
- }
- return res;
- }
- struct Node {
- ll priority;
- ll value, size = 1, sum = 0, add = 0;
- bool rev = false, swp = false;
- Node* l = nullptr;
- Node* r = nullptr;
- Node* pr = nullptr;
- Node(ll value) : priority(rand()), value(value), sum(value) {}
- } *root = nullptr;
- Node* sup[max_sz];
- struct dd2 {
- ll getSize(Node* n) {
- return n ? n->size : 0;
- }
- ll getSum(Node* n) {
- return n ? n->sum + n->add * n->size : 0;
- }
- void push(Node* n) {
- if (n) {
- if (n->add != 0) {
- n->value += n->add;
- n->sum += n->add;
- if (n->l) {
- n->l->add += n->add;
- }
- if (n->r) {
- n->r->add += n->add;
- }
- n->add = 0;
- }
- if (n->rev) {
- swap(n->l, n->r);
- if (n->l) {
- n->l->rev ^= 1;
- }
- if (n->r) {
- n->r->rev ^= 1;
- }
- n->rev = false;
- }
- }
- }
- void update(Node* n) {
- if (n) {
- n->size = getSize(n->l) + 1 + getSize(n->r);
- n->sum = getSum(n->l) + getSum(n->r) + n->value;
- if (n->l) {
- n->l->pr = n;
- }
- if (n->r) {
- n->r->pr = n;
- }
- }
- }
- Node* merge(Node* a, Node* b) {
- push(a);
- push(b);
- if (!a || !b) {
- return a ? a : b;
- }
- if (a->priority > b->priority) {
- b->pr = a;
- a->r = merge(a->r, b);
- update(a);
- return a;
- }
- else {
- a->pr = b;
- b->l = merge(a, b->l);
- update(b);
- return b;
- }
- }
- void split(Node* n, ll k, Node*& a, Node*& b) {
- push(n);
- if (!n) {
- a = b = nullptr;
- return;
- }
- if (getSize(n->l) < k) {
- split(n->r, k - getSize(n->l) - 1, n->r, b);
- a = n;
- }
- else {
- split(n->l, k, a, n->l);
- b = n;
- }
- update(a);
- update(b);
- }
- ll get(ll index) {
- Node* less, * equal, * greater;
- split(root, index, less, greater);
- split(greater, 1, equal, greater);
- ll result = equal->value;
- root = merge(merge(less, equal), greater);
- return result;
- }
- Node* getpos(ll index) {
- Node* less, * equal, * greater;
- split(root, index, less, greater);
- split(greater, 1, equal, greater);
- Node* res = equal;
- root = merge(merge(less, equal), greater);
- return res;
- }
- ll getid(Node* n) {
- return getSize(n->l);
- }
- void push_back(ll value) {
- root = merge(root, new Node(value));
- }
- void push_front(ll value) {
- root = merge(new Node(value), root);
- }
- void insert(ll index, ll value) {
- Node* less, * greater;
- split(root, index, less, greater);
- root = merge(merge(less, new Node(value)), greater);
- }
- void erase(ll index) {
- Node* less, * equal, * greater;
- split(root, index, less, greater);
- split(greater, 1, equal, greater);
- root = merge(less, greater);
- }
- void erase(ll l, ll r) {
- Node* less, * equal, * greater;
- split(root, l, less, greater);
- split(greater, r - l + 1, equal, greater);
- root = merge(less, greater);
- }
- void add(ll l, ll r,ll boost) {
- Node* less, * equal, * greater;
- split(root, l, less, greater);
- split(greater, r - l + 1, equal, greater);
- equal->add += boost;
- root = merge(merge(less, equal), greater);
- }
- void revolve(ll l, ll r, ll t) {
- Node* less, * equal, * greater;
- split(root, l, less, greater);
- split(greater, r - l + 1, equal, greater);
- ll len = getSize(equal);
- t %= len;
- Node *a, *b;
- split(equal, len - t, a, b);
- equal = merge(b, a);
- root = merge(merge(less, equal), greater);
- }
- ll size() {
- return getSize(root);
- }
- ll getSum(ll l, ll r) {
- Node* less, * equal, * greater;
- split(root, l, less, greater);
- split(greater, r - l + 1, equal, greater);
- ll result = getSum(equal);
- root = merge(merge(less, equal), greater);
- return result;
- }
- void reverse(ll l, ll r) {
- Node* less, * equal, * greater;
- split(root, l, less, greater);
- split(greater, r - l + 1, equal, greater);
- equal->rev ^= true;
- root = merge(merge(less, equal), greater);
- }
- void swapper(ll l1, ll r1, ll l2, ll r2) {
- Node* less, * equal, * greater, * less2, * equal2;
- split(root, l1, less, greater);
- split(greater, r1 - l1 + 1, equal, greater);
- split(greater, l2 - r1 - 1, less2, greater);
- split(greater, r2 - l2 + 1, equal2, greater);
- root = merge(merge(less, merge(equal2, merge(less2, equal))), greater);
- }
- pair <ll, Node*> next(Node* n) {
- Node* ans = nullptr;
- if (n) {
- if (n->r) {
- n = n->r;
- while (n) {
- ans = n;
- n = n->l;
- }
- return { ans->value,ans };
- }
- else {
- ll last_val = n->value;
- n = n->pr;
- while (n) {
- if (n->l && n->l->value == last_val) {
- return { n->value,n };
- }
- last_val = n->value;
- n = n->pr;
- }
- return { -1,n };
- }
- }
- else {
- return { -1,n };
- }
- }
- };
- signed main() {
- #ifdef _DEBUG
- freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- ll t = 1;
- //cin >> t;
- while (t--) {
- ll n, m, i, j, l1, r1, l2, r2, pos, x;
- cin >> n >> m;
- dd2 tree;
- for (i = 0; i < n; i++) {
- cin >> j;
- tree.push_back(j);
- sup[j] = tree.getpos(i);
- }
- for (i = 0; i < m; i++) {
- cin >> j;
- if (j == 1) {
- cin >> l1 >> r1 >> l2 >> r2;
- tree.swapper(l1 - 1, r1 - 1, l2 - 1, r2 - 1);
- }
- else {
- cin >> x;
- Node* it = sup[x];
- for (j = 0; j < 3; j++) {
- pair <ll, Node*> res = tree.next(it);
- cout << res.first << " ";
- it = res.second;
- }
- cout << endl;
- }
- }
- }
- }
- //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement