Problem
ADD x y D: x到y每个数加上D
REVERSE x y: 翻转x到y这个区间
REVOLVE x y T: x到y区间往后旋转T位
INSERT x P: 在第x个数后插入P
DELETE x: 删除第x个数
MIN x y: 求x到y的区间最小值
Solution
splay模板题
Notice
注意0的大坑。
Code
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define sqz main
#define ll long long
#define reg register int
#define rep(i, a, b) for (reg i = a; i <= b; i++)
#define per(i, a, b) for (reg i = a; i >= b; i--)
#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)
const int INF = 1e9, N = 400000;
const double eps = 1e-6, phi = acos(-1.0);
ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}
ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}
void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}
int point = 0, T[N + 5], root;
struct node
{
int val[N + 5], parent[N + 5], son[2][N + 5], Min[N + 5], Size[N + 5], tag[N + 5], add[N + 5];
inline void up(int u)
{
Min[u] = val[u];
if (son[0][u]) Min[u] = min(Min[u], Min[son[0][u]]);
if (son[1][u]) Min[u] = min(Min[u], Min[son[1][u]]);
Size[u] = Size[son[0][u]] + Size[son[1][u]] + 1;
}
inline void down(int u)
{
if (add[u])
{
if (son[0][u])
{
val[son[0][u]] += add[u];
add[son[0][u]] += add[u];
Min[son[0][u]] += add[u];
}
if (son[1][u])
{
val[son[1][u]] += add[u];
add[son[1][u]] += add[u];
Min[son[1][u]] += add[u];
}
add[u] = 0;
}
if (tag[u])
{
swap(son[0][u], son[1][u]);
tag[son[0][u]] ^= 1, tag[son[1][u]] ^= 1;
tag[u] = 0;
}
}
void Newnode(int &u, int from, int v)
{
u = ++point;
parent[u] = from;
son[0][u] = son[1][u] = 0;
tag[u] = add[u] = 0;
Min[u] = val[u] = v;
Size[u] = 1;
}
void Build(int l, int r, int &u, int from)
{
int mid = (l + r) >> 1;
Newnode(u, from, T[mid]);
if (l < mid) Build(l, mid - 1, son[0][u], u);
if (mid < r) Build(mid + 1, r, son[1][u], u);
up(u);
}
int Find(int u, int k)
{
down(u);
if (Size[son[0][u]] + 1 == k) return u;
if (Size[son[0][u]] >= k) return Find(son[0][u], k);
else return Find(son[1][u], k - Size[son[0][u]] - 1);
}
void Rotate(int x, int &rt)
{
int y = parent[x], z = parent[y];
down(y), down(x);
int l = (son[1][y] == x), r = 1 - l;
if (y == rt) rt = x;
else if (son[0][z] == y) son[0][z] = x;
else son[1][z] = x;
parent[x] = z;
parent[son[r][x]] = y, son[l][y] = son[r][x];
parent[y] = x, son[r][x] = y;
up(y);
up(x);
}
void Splay(int x, int &rt)
{
while (x != rt)
{
int y = parent[x], z = parent[y];
if (y != rt)
{
if ((son[0][z] == y) ^ (son[0][y] == x))
Rotate(x, rt);
else Rotate(y, rt);
}
Rotate(x, rt);
}
}
void Split(int l, int r)
{
int x = Find(root, l - 1 + 1);
int y = Find(root, r + 1 + 1);
Splay(x, root);
Splay(y, son[1][root]);
}
void Add(int l, int r, int v)
{
Split(l, r);
add[son[0][son[1][root]]] += v;
Min[son[0][son[1][root]]] += v;
val[son[0][son[1][root]]] += v;
up(son[1][root]);
up(root);
}
void Insert(int pos, int v)
{
Split(pos + 1, pos);
Newnode(son[0][son[1][root]], son[1][root], v);
up(son[1][root]);
up(root);
}
void Delete(int x)
{
Split(x, x);
son[0][son[1][root]] = 0;
up(son[1][root]);
up(root);
}
void Reverse(int l, int r)
{
Split(l, r);
tag[son[0][son[1][root]]] ^= 1;
}
void Revolve(int l, int r, int t)
{
t = (t % (r - l + 1) + r - l + 1) % (r - l + 1);
if (!t) return;
Split(r - t + 1, r);
int now = son[0][son[1][root]];
son[0][son[1][root]] = 0;
up(son[1][root]);
up(root);
Split(l, l - 1);
son[0][son[1][root]] = now;
parent[now] = son[1][root];
up(son[1][root]);
up(root);
}
int Query(int l, int r)
{
Split(l, r);
return Min[son[0][son[1][root]]];
}
}Splay_tree;
int sqz()
{
int n = read();
rep(i, 1, n) T[i] = read();
T[0] = INF, T[n + 1] = INF;
Splay_tree.Build(0, n + 1, root, 0);
int q = read();
while (q--)
{
char st[10]; int x, y, v;
scanf("%s", st);
switch (st[0])
{
case 'A': x = read(), y = read(), v = read(), Splay_tree.Add(x, y, v); break;
case 'R':
if (st[3] == 'E') x = read(), y = read(), Splay_tree.Reverse(x, y);
else x = read(), y = read(), v = read(), Splay_tree.Revolve(x, y, v);
break;
case 'I': x = read(), y = read(), Splay_tree.Insert(x, y); break;
case 'D': x = read(), Splay_tree.Delete(x); break;
case 'M': x = read(), y = read(), printf("%d
", Splay_tree.Query(x, y)); break;
}
}
return 0;
}