【bzoj1895】Pku3580 supermemo Splay

題目描述

給出一個初始序列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;
}
           

轉載于:https://www.cnblogs.com/GXZlegend/p/6764275.html