【bzoj1895】Pku3580 supermemo Splay
Splay
2023-09-11 14:22:40 时间
题目描述
给出一个初始序列fA1;A2;:::Ang，要求你编写程序支持如下操作： 1. ADDxyD：给子序列fAx:::Ayg的每个元素都加上D。例如对f1,2, 3,4,5g执行"ADD 241" 会得到f1,3,4,5,5g。 2. REVERSExy：将子序列fAx:::Ayg翻转。例如对f1,2,3,4,5g执 行"REVERSE 24"会得到f1,4,3,2,5g。 3. REVOLVExyT：将子序列fAx:::Ayg旋转T个单位。例如， 对f1,2,3,4,5g执行"REVOLVE 242"会得到f1,3,4,2,5g。 4. INSERTxP：在Ax后插入P。例如，对f1,2,3,4,5g执行"INSERT 24"会得到f1,2,4,3,4,5g。 5. DELETEx：删去Ax。例如，对f1,2,3,4,5g执行"DELETE 2"会得 到f1,3,4,5g。 6. MINxy：查询子序列fAx:::Ayg中的最小元素。例如，对于序列f1, 2,3,4,5g，询问"MIN 24"的返回应为2。
输入
第一行包含一个整数n，表示初始序列的长度。 以下n行每行包含一个整数，描述初始的序列。 接下来一行包含一个整数m，表示操作的数目。 以下m行每行描述一个操作。
输出
对于所有"MIN"操作，输出正确的答案，每行一个。
样例输入
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
样例输出
5
题解
Splay裸题，省选前练习模板的好机会（尽管这次没考。。。）
写一个函数专门用来取出一段区间，可以大大减少代码量。
注意要开long long。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 300010
using namespace std;
typedef long long ll;
int fa[N] , c[2][N] , root , si[N] , rev[N] , tot;
ll v[N] , minn[N] , add[N];
char str[20];
void pushup(int k)
{
si[k] = si[c[0][k]] + si[c[1][k]] + 1;
minn[k] = min(v[k] , min(minn[c[0][k]] , minn[c[1][k]]));
}
void pushdown(int k)
{
int l = c[0][k] , r = c[1][k];
if(add[k])
{
v[l] += add[k] , minn[l] += add[k] , add[l] += add[k];
v[r] += add[k] , minn[r] += add[k] , add[r] += add[k];
add[k] = 0;
}
if(rev[k])
{
swap(c[0][l] , c[1][l]) , rev[l] ^= 1;
swap(c[0][r] , c[1][r]) , rev[r] ^= 1;
rev[k] = 0;
}
}
void build(int l , int r , int f)
{
if(l > r) return;
int mid = (l + r) >> 1;
build(l , mid - 1 , mid) , build(mid + 1 , r , mid);
fa[mid] = f , c[mid > f][f] = mid;
pushup(mid);
}
void rotate(int &k , int x)
{
int y = fa[x] , z = fa[y] , l , r;
l = (c[1][y] == x);
r = l ^ 1;
if(y == k) k = x;
else if(c[0][z] == y) c[0][z] = x;
else c[1][z] = x;
fa[x] = z , fa[y] = x , fa[c[r][x]] = y;
c[l][y] = c[r][x] , c[r][x] = y;
pushup(y) , pushup(x);
}
void splay(int &k , int x)
{
int y , z;
while(x != k)
{
y = fa[x] , z = fa[y];
if(y != k)
{
if(c[0][y] == x ^ c[0][z] == y) rotate(k , x);
else rotate(k , y);
}
rotate(k , x);
}
}
int find(int k , int x)
{
pushdown(k);
if(x <= si[c[0][k]]) return find(c[0][k] , x);
else if(x > si[c[0][k]] + 1) return find(c[1][k] , x - si[c[0][k]] - 1);
else return k;
}
int split(int l , int r)
{
int a = find(root , l - 1) , b = find(root , r + 1);
splay(root , a) , splay(c[1][root] , b);
return c[0][c[1][root]];
}
void update(int l , int r , int x)
{
int t = split(l + 1 , r + 1);
v[t] += x , minn[t] += x , add[t] += x;
pushup(c[1][root]) , pushup(root);
}
void rever(int l , int r)
{
int t = split(l + 1 , r + 1);
swap(c[0][t] , c[1][t]) , rev[t] ^= 1;
}
void revol(int l , int r , int x)
{
x %= r - l + 1;
int t = split(r - x + 2 , r + 1);
c[0][c[1][root]] = 0 , fa[t] = 0;
pushup(c[1][root]) , pushup(root);
split(l + 1 , l);
c[0][c[1][root]] = t , fa[t] = c[1][root];
pushup(c[1][root]) , pushup(root);
}
void ins(int p , int x)
{
split(p + 2 , p + 1);
c[0][c[1][root]] = ++tot;
fa[tot] = c[1][root];
v[tot] = x;
pushup(tot) , pushup(c[1][root]) , pushup(root);
}
void del(int p)
{
int t = split(p + 1 , p + 1);
c[0][c[1][root]] = 0 , fa[t] = 0;
pushup(c[1][root]) , pushup(root);
}
ll query(int l , int r)
{
int t = split(l + 1 , r + 1);
return minn[t];
}
int main()
{
int n , m , i , x , y , z;
ll k;
scanf("%d" , &n);
v[0] = v[1] = v[n + 2] = minn[0] = 0x3fffffff;
for(i = 2 ; i <= n + 1 ; i ++ ) scanf("%d" , &v[i]);
build(1 , n + 2 , 0);
root = (n + 3) >> 1 , tot = n + 2;
scanf("%d" , &m);
while(m -- )
{
scanf("%s" , str);
switch(str[0])
{
case 'A': scanf("%d%d%lld" , &x , &y , &k); update(x , y , k); break;
case 'I': scanf("%d%d" , &x , &y) , ins(x , y); break;
case 'D': scanf("%d" , &x) , del(x); break;
case 'M': scanf("%d%d" , &x , &y); printf("%lld\n" , query(x , y)); break;
default:
{
if(str[3] == 'E') scanf("%d%d" , &x , &y) , rever(x , y);
else scanf("%d%d%d" , &x , &y , &z) , revol(x , y , z);
}
}
}
return 0;
}