省流：又又又又是毒瘤数据结构。
题目传送门
看到操作一我们想到线段树/树状数组，看到操作二我们想到文艺平衡树。
再结合后面的所有操作，这题就是文艺平衡树裸题。
我们需要维护两个 lazy tag，一个翻转标记，一个加法标记即可。
下面给出二十几行的 pushdown ：
void pushdown(ll u){if (rev[u]) {swap(ls[u], rs[u]);rev[ls[u]] ^= 1;rev[rs[u]] ^= 1;rev[u] = 0;}if (add[u]) {if (ls[u]) {add[ls[u]] += add[u];minn[ls[u]] += add[u];val[ls[u]] += add[u];}if (rs[u]) {add[rs[u]] += add[u];minn[rs[u]] += add[u];val[rs[u]] += add[u];}add[u] = 0;}
}
其他的就是文艺平衡树板子了。
code
#include <bits/stdc++.h>
#define pub public:
#define pri private:
#define fri friend:
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 998244353;
constexpr int maxn = 2e5 + 5;ll n, q;
ll x, y, z;
ll root, tot;
ll seed = 1;ll val[maxn];
ll priority[maxn];
ll siz[maxn];
ll minn[maxn];
ll ls[maxn];
ll rs[maxn];
ll rev[maxn];
ll add[maxn];string opt;void pushup(ll);
void pushdown(ll);
void split(ll, ll, ll &, ll &);
ll merge(ll, ll);
void ADD(ll, ll, ll);
void REVERSE(ll, ll);
void REVOLVE(ll, ll, ll);
void INSERT(ll, ll);
void DELETE(ll);
ll MIN(ll, ll);int main() {freopen("std.in", "r", stdin);freopen("std.out", "w", stdout);fast;srand(time(0));cin >> n;minn[0] = 1e18;for (int i = 1, u; i <= n; i++){cin >> u;INSERT(i - 1, u);}cin >> q;while (q--){cin >> opt;if (opt == "ADD"){cin >> x >> y >> z;ADD(x, y, z);}else if (opt == "REVERSE"){cin >> x >> y;REVERSE(x, y);}else if (opt == "REVOLVE"){cin >> x >> y >> z;REVOLVE(x, y, z);}else if (opt == "INSERT"){cin >> x >> y;INSERT(x, y);}else if (opt == "DELETE"){cin >> x;DELETE(x);}else {cin >> x >> y;cout << MIN(x, y) << endl;}}return 0;
}void pushup(ll u){siz[u] = siz[ls[u]] + siz[rs[u]] + 1;minn[u] = min(val[u], min(minn[ls[u]], minn[rs[u]]));
}void pushdown(ll u){if (rev[u]) {swap(ls[u], rs[u]);rev[ls[u]] ^= 1;rev[rs[u]] ^= 1;rev[u] = 0;}if (add[u]) {if (ls[u]) {add[ls[u]] += add[u];minn[ls[u]] += add[u];val[ls[u]] += add[u];}if (rs[u]) {add[rs[u]] += add[u];minn[rs[u]] += add[u];val[rs[u]] += add[u];}add[u] = 0;}
}void split(ll u, ll v, ll &rootl, ll &rootr){if (!u){rootl = rootr = 0;return ;}pushdown(u);if (siz[ls[u]] + 1 <= v){rootl = u;split(rs[u], v - siz[ls[u]] - 1, rs[u], rootr);}else {rootr = u;split(ls[u], v, rootl, ls[u]);}pushup(u);
}ll merge(ll rootl, ll rootr){if (!rootl)return rootr;if (!rootr)return rootl;pushdown(rootl);pushdown(rootr);if (priority[rootl] < priority[rootr]){rs[rootl] = merge(rs[rootl], rootr);pushup(rootl);return rootl;}else {ls[rootr] = merge(rootl, ls[rootr]);pushup(rootr);return rootr;}
}void ADD(ll x, ll y, ll z){ll a, b, c;split(root, y, b, c);split(b, x - 1, a, b);add[b] += z;minn[b] += z;val[b] += z;root = merge(merge(a, b), c);
}void REVERSE(ll x, ll y){ll a, b, c;split(root, y, b, c);split(b, x - 1, a, b);rev[b] ^= 1;root = merge(merge(a, b), c);
}void REVOLVE(ll x, ll y, ll z){ll a, b, c, d;split(root, y, c, d);split(c, x - 1, a, c);z %= (y - x + 1);split(c, y - x + 1 - z, b, c);root = merge(merge(merge(a, c), b), d);
}void INSERT(ll x, ll y){++tot;val[tot] = y;priority[tot] = rand();siz[tot] = 1;minn[tot] = y;ll a, b;split(root, x, a, b);root = merge(merge(a, tot), b);
}void DELETE(ll x){ll a, b, c;split(root, x - 1, a, b);split(b, 1, b, c);root = merge(a, c);
}ll MIN(ll x, ll y){ll a, b, c;split(root, y, b, c);split(b, x - 1, a, b);ll ans = minn[b];root = merge(merge(a, b), c);return ans;
}