POJ 3580 SuperMemo

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, {A₁, A₂, ... A_n}. Then the host performs a series of operations and queries on the sequence which consists:

1. ADD x y D: Add D to each number in sub-sequence {A_x ... A_y}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
2. REVERSE x y: reverse the sub-sequence {A_x ... A_y}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
3. REVOLVE x y T: rotate sub-sequence {A_x ... A_y} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
4. INSERT x P: insert P after A_x. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
5. DELETE x: delete A_x. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
6. MIN x y: query the participant what is the minimum number in sub-sequence {A_x ... A_y}. 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

5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5

Sample Output

5

解决完splay终极boss以后这种题写起来就十分轻松了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e5 + 10;
int n, m, root, a[maxn], l, r, c;
char s[20];

struct Splays
{
  const static int maxn = 2e5 + 10;     //节点个数
  const static int INF = 0x7FFFFFFF;      //int最大值
  int ch[maxn][2], F[maxn], sz;       //左右儿子，父亲节点和节点总个数
  int A[maxn], S[maxn], C[maxn], R[maxn], I[maxn];
  int Node(int f, int a) { S[sz] = 1; C[sz] = A[sz] = a; R[sz] = I[sz] = ch[sz][0] = ch[sz][1] = 0; F[sz] = f; return sz++; }//申请一个新节点
  void clear(){ sz = 1; S[0] = ch[0][0] = ch[0][1] = F[0] = 0; C[0] = INF; }//清空操作
  void Pushdown(int x)
  {
    if (R[x])
    {
      R[ch[x][0]] ^= 1; R[ch[x][1]] ^= 1;
      swap(ch[x][0], ch[x][1]); R[x] = 0;
    }
    if (I[x])
    {
      if (ch[x][0]) A[ch[x][0]] += I[x], C[ch[x][0]] += I[x];
      if (ch[x][1]) A[ch[x][1]] += I[x], C[ch[x][1]] += I[x];
      I[ch[x][0]] += I[x]; I[ch[x][1]] += I[x];   I[x] = 0;
    }
  }
  void Count(int x)
  {
    C[x] = min(A[x], min(C[ch[x][0]], C[ch[x][1]])); 
    S[x] = S[ch[x][0]] + S[ch[x][1]] + 1;
  }
  void rotate(int x, int k)
  {
    int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
    if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
    F[x] = F[y];    F[y] = x; ch[x][k] = y;
    C[x] = C[y];  S[x] = S[y];    Count(y);
  }
  void Splay(int x, int r)
  {
    for (int fa = F[r]; F[x] != fa;)
    {
      if (F[F[x]] == fa) { rotate(x, x == ch[F[x]][0]); return; }
      int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
      y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
    }
  }
  void build(int fa, int &x, int l, int r)
  {
    if (l > r) return;
    int mid = l + r >> 1;
    x = Node(fa, a[mid]);
    build(x, ch[x][0], l, mid - 1);
    build(x, ch[x][1], mid + 1, r);
    Count(x);
  }
  void find(int &x, int k)
  {
    for (int i = x; i;)
    {
      Pushdown(i);
      if (S[ch[i][0]] > k) { i = ch[i][0]; continue; }
      if (S[ch[i][0]] == k){ Splay(i, x); x = i; return; }
      k -= S[ch[i][0]] + 1; i = ch[i][1];
    }
  }
  void Add(int&x)
  {
    scanf("%d%d%d", &l, &r, &c);
    find(x, l - 1); find(ch[x][1], r - l + 1);
    int g = ch[ch[x][1]][0];
    I[g] += c;  A[g] += c;  C[g] += c;
    Count(ch[x][1]);  Count(x);
  }
  void Reverse(int &x)
  {
    scanf("%d%d", &l, &r);
    find(x, l - 1); find(ch[x][1], r - l + 1);
    R[ch[ch[x][1]][0]] ^= 1;
  }
  void Revolve(int &x)
  {
    scanf("%d%d%d", &l, &r, &c);
    find(x, l - 1); find(ch[x][1], r - l + 1);
    int g = ch[ch[x][1]][0]; c %= (r - l + 1);
    if (!c) return;
    int s = r - l + 1 - c;  find(g, s);
    int t = ch[g][0]; ch[g][0] = 0; Count(g);
    find(g, S[g] - 1);  ch[g][1] = t; F[t] = g; Count(g);
  }
  void Insert(int &x)
  {
    scanf("%d%d", &l, &r);
    find(x, l); find(ch[x][1], 0);
    ch[ch[x][1]][0] = Node(ch[x][1], r);
    Count(ch[x][1]);  Count(x);
  }
  void Delete(int &x)
  {
    scanf("%d%d", &l);
    find(x, l - 1); find(ch[x][1], 1);
    ch[ch[x][1]][0] = 0;
    Count(ch[x][1]);  Count(x);
  }
  void Min(int &x)
  {
    scanf("%d%d", &l, &r);
    find(x, l - 1); find(ch[x][1], r - l + 1);
    printf("%d\n", C[ch[ch[x][1]][0]]);
  }
}solve;


int main()
{
  while (scanf("%d", &n) != EOF)
  {
    a[0] = a[n + 1] = root = 0; solve.clear();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    solve.build(0, root, 0, n + 1);
    scanf("%d", &m);
    while (m--)
    {
      scanf("%s", s);
      if (!strcmp(s, "ADD")) solve.Add(root);
      if (!strcmp(s, "REVERSE")) solve.Reverse(root);
      if (!strcmp(s, "REVOLVE")) solve.Revolve(root);
      if (!strcmp(s, "INSERT")) solve.Insert(root);
      if (!strcmp(s, "DELETE")) solve.Delete(root);
      if (!strcmp(s, "MIN")) solve.Min(root);
    }
  }
  return 0;
}