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;
- ll binpow(ll a, ll n) {
- ll res = 1;
- while (n) {
- if (n & 1) {
- res *= a;
- }
- a *= a;
- n >>= 1;
- }
- return res;
- }
- struct dd2 {
- struct Node {
- ll priority;
- ll value, size = 1, minValue, add = 0, rev = 0;
- Node* l = nullptr;
- Node* r = nullptr;
- Node(ll value) : priority(rand()), value(value),minValue(value) {}
- } *root = nullptr;
- ll getSize(Node* n) {
- return n ? n->size : 0;
- }
- ll getMinValue(Node* n) {
- return n ? n->minValue + n->add : inf;
- }
- void push(Node* n) {
- if (n) {
- if (n->add != 0) {
- n->value += n->add;
- n->minValue += 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 = 0;
- }
- }
- }
- void update(Node* n) {
- if (n) {
- n->size = getSize(n->l) + 1 + getSize(n->r);
- n->minValue = min(min(getMinValue(n->l), n->value), getMinValue(n->r));
- }
- }
- Node* merge(Node* a, Node* b) {
- push(a);
- push(b);
- if (!a || !b) {
- return a ? a : b;
- }
- if (a->priority > b->priority) {
- a->r = merge(a->r, b);
- update(a);
- return a;
- }
- else {
- 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;
- }
- 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 minValue(ll l, ll r) {
- Node* less, * equal, * greater;
- split(root, l, less, greater);
- split(greater, r - l + 1, equal, greater);
- ll result = getMinValue(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 ^= 1;
- root = merge(merge(less, equal), greater);
- }
- };
- 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, l, r;
- cin >> n >> m;
- dd2 tree;
- for (i = 0; i < n; i++) {
- cin >> j;
- tree.push_back(j);
- }
- while (m--) {
- cin >> j >> l >> r;
- if (j == 1) {
- tree.reverse(l - 1, r - 1);
- }
- else {
- cout << tree.minValue(l - 1, r - 1) << endl;
- }
- }
- }
- }
- //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement