BZOJ 1895 & POJ 3580 supermemo （splay）

SuperMemo

Time Limit: 5000MS	Memory Limit: 65536K
Total Submissions: 16524	Accepted: 5214
Case Time Limit: 2000MS

Description

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1, A2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:

ADD x y D: Add D to each number in sub-sequence {Ax ... Ay}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
REVERSE x y: reverse the sub-sequence {Ax ... Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
REVOLVE x y T: rotate sub-sequence {Ax ... Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
MIN x y: query the participant what is the minimum number in sub-sequence {Ax ... Ay}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

Output

For each "MIN" query, output the correct answer.

Sample Input

Sample Output

Source

POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu

題意，模闆，思路全都轉自tabris大佬

題意：

　　給出一個數字序列，有6種操作：

　　　　（1） ADD x y d：第x個數到第y個數加d 。

　　　　（2） REVERSE x y ：将區間[x,y]中的數翻轉。

　　　　（3） REVOLVE x y t ：将區間[x,y]旋轉t次，如1 2 3 4 5 旋轉2次後就變成4 5 1 2 3 。

　　　　（4） INSERT x p ：在第x個數後面插入p 。

　　　　（5）DELETE x ：删除第x個數。

　　　　（6） MIN x y ：查詢區間[x,y]中的最小值。

就是區間加，翻轉，剪切，詢問最值。點插入，删除。這幾個操作

有翻轉了是以用SPLAY來維護一下

區間加區間最小值就不說了和普通的二叉搜尋樹一模一樣.

點插入删除

假如要插入的點在x

那麼讓x-1做為樹根,x+1伸展到根節點下面,那麼x+1的左兒子就是空出來的加個值就好了

删除發過來一樣的

區間操作

對于區間[l,r]

那麼讓l-1做為樹根,r+1伸展到根節點下面,那麼r+1的左兒子就是這個區間

但為了更好的處理[1,n]這個區間加上個0和n+1這兩個節點

翻轉

同樣在一個二叉樹中翻轉也就是讓每個節點的兩個兒子交換一下順序就好了,, 打個标記就行了,

旋轉

其實旋轉說白了就是将這個區間分成兩段然後交換一下子,

是以我們可以将後一個區間處理到一個子樹上,然後放到 l−1,l 這兩個節點之間,就好了,先減掉,然後在加上去就好了

總結下：splay 的區間操作，插入操作，通常都是把左端-1旋轉到根，右端點+1旋轉到根的右兒子，那樣右端點+1 的左兒子就是區間 l-r 因為他要大于根小于他爸爸。這些操作都是通過旋轉，然後讓一個節點變成一棵樹，對這顆子樹不斷操作，lazy，rev什麼的插入/删除節點的時候注意父節點要修改

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int INF = 1e9;
int n, m;
int ch[maxn][2]; //0做孩子， 1右孩子
int f[maxn]; //每個節點的父親
int sz[maxn]; //每個節點為根子樹的大小
int val[maxn]; //這個節點所表示的值
int cnt[maxn]; //這個節點所表示值的數量
int mi[maxn]; //這個節點子樹的最小值
int rev[maxn]; //反轉标記
int lazy[maxn]; //延遲标記
int root;  // splay的根
int tot; //樹所有的節點數量
void Swap(int &x, int &y)
{
    x ^=y; y ^= x; x ^= y;
}
int Min(int x, int y)
{
    return x < y ? x : y;
}
void update_rev(int x) //更新反轉
{
    if(!x) return;
    Swap(ch[x][0], ch[x][1]);
    rev[x] ^= 1;  //如果這一層曾經被轉過下面就不用轉了， 把rev取消了
}
void update_add(int x, int v)
{
    if(x) lazy[x] += v, val[x] += v, mi[x] += v;
}
void newnode(int rt, int v, int fa)
{
    f[rt] = fa; sz[rt] = 1;
    val[rt] = mi[rt] = v;
    ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0; //加點的時候把所有的資訊都更新了
}
void delnode(int rt) //為了回收空間，其實沒什麼太大的用處
{
    f[rt] = val[rt] = sz[rt] = mi[rt] = 0;
    ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0;
}
void pushup(int x)  //跟線段樹一樣，從下往上不斷更新
{
    if(!x)return ;
    sz[x] = 1, mi[x] = val[x];
    if(ch[x][0]) sz[x] += sz[ch[x][0]], mi[x]= Min(mi[x],mi[ch[x][0]]); //更新個數跟目前子樹最小值
    if(ch[x][1]) sz[x] += sz[ch[x][1]], mi[x]= Min(mi[x],mi[ch[x][1]]);
}
void pushdown(int x) //向下傳遞lazy 跟 rev
{
    if(!x) return;
    if(lazy[x])
    {
        update_add(ch[x][0], lazy[x]);
        update_add(ch[x][1], lazy[x]);
        lazy[x] = 0;
    }
    if(rev[x])
    {
        update_rev(ch[x][0]);
        update_rev(ch[x][1]);
        rev[x] = 0;
    }
}
void build(int &rt, int l, int r, int fa) //rt是節點編号，節點的大小代表了兩個數位置的相對順序
{                       //一共tot個節點
    if(l > r) return;
    int mid = (r+l) >> 1;
    rt = mid; newnode(rt, val[rt], fa);
    build(ch[rt][0], l, mid-1, rt);
    build(ch[rt][1], mid+1, r, rt);
    pushup(rt);
}
void Rotate(int x, int k) // k = 0左旋， k = 1右旋
{
    int y = f[x];int z = f[y];
    pushdown(y); pushdown(x);
    ch[y][!k] = ch[x][k];
    if(ch[x][k]) f[ch[x][k]] = y;
    f[x] = z;
    if(z) ch[z][ch[z][1]==y] = x;
    f[y] = x; ch[x][k] = y;
    pushup(y), pushup(x);
}
void splay(int x, int goal)
{
    pushdown(x);
    while(f[x] != goal)
    {
        int y = f[x], z = f[y];
         //在這裡下傳翻轉标記，在rotate裡下傳标記可能會使樹形改變導緻旋轉出錯
        pushdown(z); pushdown(y); pushdown(x);
        if(f[y] == goal) Rotate(x, ch[y][0] == x);
        else
        {
            int p = ch[f[y]][0] == y;
            if(ch[y][p] == x) Rotate(x, !p), Rotate(x, p);
            else Rotate(y, p), Rotate(x, p);
        }
    }
    pushup(x);
    if(goal == 0) root = x;
}

//以x為根的子樹 的極值點  0 極小 1 極大
int extreme(int x,int k)
{
    while(ch[x][k]) x = ch[x][k];
    splay(x, 0);  //所有操作之後都伸展下
    return x;
}
//以節點編号x為根的子樹 第k個數的節點編号
int kth(int x,int k)
{
    pushdown(x);
    if(sz[ch[x][0]]+1 == k) return x;
    else if(sz[ch[x][0]] >= k) return kth(ch[x][0],k);
    else return kth(ch[x][1], k-sz[ch[x][0]]-1);
}
//區間交換
void exchange(int l1,int r1,int l2,int r2)
{
    int x = kth(root, l2-1), y = kth(root, r2+1);
    splay(x,0), splay(y,x);
    int tmp_right = ch[y][0]; ch[y][0]=0; //“剪貼下來”
    x = kth(root, l1-1),y = kth(root, l1);
    splay(x,0), splay(y,x);
    ch[y][0] = tmp_right;
    f[tmp_right] = y;
}
//區間翻轉
void reversal(int l,int r)
{
    int x = kth(root,l-1),y = kth(root,r+1);
    splay(x,0); splay(y,x);
    update_rev(ch[y][0]);  //ch[y][0]就是l-r區間
}
//區間加
void add(int l,int r,int v)
{
    int x = kth(root,l-1), y = kth(root,r+1);
//    cout << 1 <<endl;
    splay(x,0); splay(y,x);
    update_add(ch[y][0],v); //ch[y][0]就是l-r區間
}
//在第k個數後插入值為x的節點
void Insert(int k,int x){
    int r = kth(root, k),rr = kth(root, k+1);
    splay(r,0), splay(rr,r);
    newnode(++tot, x, rr); ch[rr][0] = tot; //節點個數增加
    for(r = rr; r ; r = f[r]) pushdown(r), pushup(r);
    splay(rr,0);
}
//删除第k位置的數
void Delete(int k)
{
    splay(kth(root,k-1), 0);
    splay(kth(root,k+1), root);
    delnode(ch[ch[root][1]][0]);
    ch[ch[root][1]][0] = 0;
    pushup(ch[root][1]);
    pushup(root);
}
// 擷取區間最大值
//int get_max(int l,int r)
//{
//    int x = kth(root,l-1), y = kth(root,r+1);
//    splay(x,0); splay(y,x);
//    return mx[ch[y][0]];
//}
//擷取區間最小值
int get_min(int l,int r)
{
    int x = kth(root,l-1), y = kth(root,r+1);
    splay(x,0); splay(y,x);
    return mi[ch[y][0]];
}
void init(int n)
{
    root = 0;
    //不斷更新的， 不斷插入的， 需要一個tot記錄插入節點的編号
//    tot = 0;
//    newnode(++tot, -INF, 0);
//    newnode(++tot, INF, root);
//    ch[root][1] = tot;
    f[0] = sz[0] = ch[0][0] = ch[0][1] = rev[0] = lazy[0] = 0; //rt編号多加兩個，處理區間[1,n]
    build(root, 1, n, 0);
    pushup(root);
}
char s[12];
int main()
{
    scanf("%d", &n);
    val[1] = val[n+2] = INF; //多加兩個編号0,n+1， 把區間1-n包起來
    for(int i = 2;i <= n+1; i++) scanf("%d", &val[i]);
    tot = n+2;
    init(n+2);
    scanf("%d",&m);
    for(int i = 1; i <= m; i++){
        int d, l, r;
        scanf(" %s",s);
        if(s[0]=='A')
        { //ADD
            scanf("%d%d%d", &l, &r, &d);
            add(l+1,r+1,d);
        }
        else if(s[0]=='I')
        { //INSERT
            scanf("%d%d",&l,&d);
            Insert(l+1,d);
        }
        else if(s[0]=='M')
        { //MIN
            scanf("%d%d",&l,&r);
            printf("%d\n",get_min(l+1,r+1));
        }
        else if(s[0]=='D')
        { //DELETE
            scanf("%d",&l);
            Delete(l+1);
        }
        else if(s[3]=='E')
        { //REVERSE
            scanf("%d%d",&l,&r);
            reversal(l+1, r+1); //增加了1一個節點全體後移一個
        }
        else
        { //REVOLVE
            scanf("%d%d%d",&l,&r,&d);
            d = d % (r-l+1);
            if(d) exchange(l +1,r-d +1,r-d+1 +1,r +1);
        }
    }
    return 0;
}

BZOJ 1895 & POJ 3580 supermemo （splay）

繼續閱讀

POJ_1985_Cow Marathon(樹的直徑)

CF1394C 計算幾何

leetcode_17.Letter Combinations of a Phone Number

HDU 1286 找新朋友（歐拉函數模闆）

hdu 1286 找新朋友（歐拉函數）

哈理工oj Touring （最短路 dij算法鄰接表 + 隊列）

HDU 1286 找新朋友(歐拉函數)找新朋友

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

CF-346 D. Robot Control(反向建圖spfa)

ACMer成長之路

pat（B）1009. 說反話（逆疊代器）

關于多項式的一點研究及其在ACM競賽中的應用關于多項式的一點研究及其在ACM競賽中的應用

codeforces 838D D. Airplane Arrangements 構造法推公式

HDU Reorder the Books

POJ 1284 Primitive Roots (歐拉函數&原根定理)

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004

BZOJ 1895 &amp; POJ 3580 supermemo （splay）

繼續閱讀

BZOJ 1895 & POJ 3580 supermemo （splay）