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
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
Sample Output
5
Source
POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu
【分析】
跟维修数列类似，不过多了几个操作，还需要合并。
还有点问题。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#define LOCAL
const int MAXN = + ;
const int INF = 0x7fffffff;
const int SIZE = ;
using namespace std;
struct Node{
int shu[SIZE + ];
int Min, addn, size;//块内最小值,需要加的n
Node *l, *r;
bool turn, add;//turn为翻转标记,add为增加标记 Node(){
Min = INF; addn = size = ;
l = r = NULL;
turn = add = ;
}
void update(){
if (turn){
for (int i = ; i <= (size>>); i++) swap(shu[i], shu[size - i + ]);
turn = ;
}
if (add){
add = ;
for (int i = ; i <= size; i++) shu[i] += addn;
Min += addn;
addn = ;
}
}
//统计最小值
void Count(){
update();
Min = INF;
for (int i = ; i <= size; i++) Min = min(shu[i], Min);
}
};
struct Block{
Node *head, *p;
int dir;//剩余的位置 Block(){head = new Node;}
//分裂p块
Node *split(Node *&t, int x){//从p的x位置开始分裂
t->update();
Node *p2 = new Node;
p2->r = t->r;
p2->l = t;
if (t->r != NULL) t->r->l = p2;
t->r = p2;
//[1,x]分到p中，[x+1,p->size]在p2中
memcpy(&p2->shu[], &t->shu[x + ], sizeof(int) * (t->size - x));
p2->size = t->size - x;//第一次写反了QAQ
t->size = x; t->Count();
p2->Count();
return p2;
}
Node *merge(Node *a, Node *b){
a->update();
b->update();
Node *t = new Node;
t->r = b->r;
t->l = a->l;
if (b->r != NULL) b->r->l = t;
if (a->l != NULL) a->l->r = t;
t->size = a->size + b->size;
memcpy(&t->shu[], &a->shu[], sizeof(int) * (a->size));
memcpy(&t->shu[a->size + ], &b->shu[], sizeof(int) * (b->size));
t->Count();
if (a->l == NULL)//说明是head
head = t;
delete a;
delete b;
return t;
}
void find(int x){
//路径压缩
int cnt = ;
p = head;
while (cnt + p->size < x){
cnt += p->size;
//if ((p->l != NULL) && (p->l->size + p->size <= (SIZE>>1)))
//p = merge(p->l, p);
if (p->size == && p != head){//删除空白块
p = p->l;
if (p->r != NULL) p->r = p->r->r;
else p->r = NULL;
if (p->r != NULL) p->r->l = p;
}
p = p->r;
}
dir = x - cnt;//注意这个值是直接在pos数组中的
}
//在pos位置插入num个数
void Insert(int pos, int num, int *data){
Node *p2;
find(pos);
if (pos == && head->size == ) goto w;
p->update();
//需要分裂
if (dir != p->size) {
p = split(p, dir);
p = p->l;
p = split(p, p->size);
}else p = split(p, dir); w:int i = ;
while (i <= num){
int tmp = min(SIZE - p->size, num - i + );
memcpy(&p->shu[p->size + ], &data[i], sizeof(int) * (tmp));
p->size += tmp;
i += tmp;
if (num >= i){
p->Count();
p = split(p, p->size);
}
}
p->Count();
}
void Delete(int pos, int num){//从pos位置开始删除num个数字
find(pos);
Node *p2;
while (num > ){
if ((dir == ) && (num >= p->size)){
num -= p->size;
if (p->l != NULL) p->l->r = p->r;
else head = p->r;
if (p->r != NULL) p->r->l = p->l;
p2 = p;
p = p->r;
delete p2;
}else{//不然就暴力删除
p->update();
int tmp = min(dir + num - , p->size);
num -= tmp - dir + ;
for (int i = ; i <= p->size - tmp; i++) p->shu[dir + i - ] = p->shu[tmp + i];
p->size -= tmp - dir + ;
p->Count();
p = p->r;
dir = ;
}
}
if (head == NULL) {head = new Node;}
}
//从pos位置开始给num个数字加上val
void add(int pos, int num, int val){
find(pos);
while (num > ){
if ((dir == ) && (num >= p->size)){
//p->update();
num -= p->size;
p->add = ;
p->addn += val;
p = p->r;
}else{
//打标记好像没必要update?
p->update();//会反转啊
int tmp = min(dir + num - , p->size);
num -= tmp - dir + ;
for (int i = ; i <= tmp - dir; i++) p->shu[i + dir] += val;
p->Count();
p = p->r;
dir = ;
}
}
}
int getMin(int pos, int num){
int Ans = INF;
find(pos);
while (num > ){
if ((dir == ) && (num >= p->size)){
p->Count();
num -= p->size;
Ans = min(Ans, p->Min);
p = p->r;
}else{//暴力判断
p->Count();
int tmp = min(dir + num - , p->size);
num -= tmp - dir + ;
for (int i = ; i <= tmp - dir; i++) Ans = min(p->shu[i + dir], Ans);
p = p->r;
dir = ;
}
}
return Ans;
}
//翻转
void Reverse(int pos, int num){
Node *ap, *bp, *cp, *dp;
Node *p2;
find(pos);
if (p->size >= dir + num - ){
p->update();
for (int i = ; i <= (num>>); i++)
swap(p->shu[dir + i - ], p->shu[num - i + dir]);
//p->Count();这样不会改变Min,不用改！
return;
}
if (dir > ){
num -= p->size - dir + ;
p2 = split(p, dir - );
ap = p2->l;
bp = p2;
p = p2->r; }else{//不然的话dir在一个整块上，
ap = p->l;
bp = p;
}
while (num > p->size){
num -= p->size;
p = p->r;
} //最后一块切割
if (num != p->size){
p2 = split(p, num);
cp = p2->l;
dp = p2;
}else{
cp = p;
dp = p->r;
}
p = bp;
while (){
swap(p->l, p->r);
p->turn = !p->turn;
if (p == cp) break;
p = p->l;
}
//大调换
if (dp != NULL) dp->l = bp;
bp->r = dp;
cp->l = ap;
if (ap != NULL) ap->r= cp;
else head = cp;
}
//旋转
//将[a,b]和[b+1, c]调换
void Revolve(int a, int b, int c){
if (b == c) return;
Node *z[], *y[];
Node *p2;
int L = c - a + ;//总长度
int L2 = b - a + ;//[a,b]的长度
find(a);
int num = L2;
//全部在一个块内
if (p->size >= dir + L - ){
int tmp[SIZE], cnt = ;
for (int i = dir + L2; i <= dir + L - ; i++) tmp[cnt++] = p->shu[i];
for (int i = dir; i <= dir + L2 - ; i++) tmp[cnt++] = p->shu[i];
for (int i = dir; i <= dir + L - ; i++) p->shu[i] = tmp[i - dir + ];
return;
}
//分割第一块
if (dir > ){
num -= p->size - dir + ;
p2 = split(p, dir - );
z[] = p2->l;
y[] = p2;
p = p2->r;
}else{
z[] = p->l;
y[] = p;
}
//中间的这一块
//num = L2;
while (num > p->size){
num -= p->size;
p = p->r;
}
int tmp = num;
num = L - L2;
if (tmp == p->size){
z[] = p;
y[] = p->r;
p = p->r;//这里还要走
}else if(tmp == ){
z[] = p->l;
y[] = p;
}else{
// num -= p->size - tmp;
p2 = split(p, tmp);
z[] = p2->l;
y[] = p2;
p = p2;
} while (num > p->size){
num -= p->size;
p = p->r;
} if (num == p->size){
z[] = p;
y[] = p->r;
}else if (num == ){
z[] = p->l;
y[] = p;
}else{
p2 = split(p, num);
z[] = p2->l;
y[] = p2;
}
//大调换!
if (z[] != NULL) z[]->r = y[];
else head = y[];y[]->l = z[];
if (y[] != NULL) y[]->l = z[];z[]->r = y[];
z[]->r = y[];
y[]->l = z[];
}
void print(){
Node *cur = head;
while (){
if (cur == NULL) break;
cur->update();
for (int i = ; i <= cur->size; i++) printf("%d ", cur->shu[i]);
cur = cur->r;
}
}
}A;
int n, data[MAXN];
char str[]; void debug();
void init(){
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &data[i]);
A.Insert(, n, data);
}
void work(){
//tot为数字总述
int m, tot = n;
scanf("%d", &m);
for (int i = ; i <= m; i++){
if (i == )
printf("");
scanf("%s", str);
if (str[] == 'A'){
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
if (r>= tot) A.add(l, r - l + , x);
}else if (str[] == 'I'){
int l, x;
scanf("%d%d", &l, &x);
data[] = x;
A.Insert(l, , data);
tot++;
}else if (str[] == 'M'){
int l, r;
scanf("%d%d", &l, &r);
if (r >= tot) printf("%d\n", A.getMin(l, r - l + ));
}else if (str[] == 'D'){
int l;
scanf("%d", &l);
tot--;
if (l >= tot) A.Delete(l, );
}else if (!strcmp(str, "REVERSE")){
int l, r;
scanf("%d%d", &l, &r);
if (l == r) continue;
if (r >= tot )A.Reverse(l, r - l + );
}else{
int l, r, t;
scanf("%d%d%d", &l, &r, &t);
//注意t可能为-
int len = r - l + ;
t = (t%len + len) % len;
if (t && r >= tot) A.Revolve(l, r - t, r);
}
}
}
void debug(){
data[] = ;
data[] = ;
data[] = ;
A.Insert(, , data);data[] = ; data[] = ;
A.Insert(, , data);data[] = ; data[] = ;
A.Insert(, , data);
//A.Reverse(2, 4);
//A.split(A.head, 1);
A.print();
printf("\n%d", A.getMin(, ));
} int main(){
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("std.txt", "w", stdout);
#endif
init();
work();
//debug();
return ;
}