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 = ;
const int SIZE = ;
const int maxnode = 0x7fffffff + ;
using namespace std;
struct SPLAY{
struct Node{
int val, Min;//分别为值,最小值,大小和lazy下标
int size, lazy;
bool turn;
Node *parent, *ch[]; //初始化
void NEW(int x){
Min = val = x;
size = ;
lazy = turn = ;
parent = ch[] = ch[] = NULL;
}
int cmp(){
if (parent->ch[] == this) return ;
if (parent->ch[] == this) return ;
}
//还是不要写在里面了..
/*void pushdown(){ }
void update(){
size = 1;
if (x->ch[0] != NULL) size += x->ch[0]->size;
if (x->ch[1] != NULL) size += x->ch[0]->size;
}
*/
}mem[MAXN], *root;//mem为静态数组
int tot; int get(Node *&x){return (x == NULL ? : x->size);}
//————————————————————这一部分不能卸载里面
//更新
void update(Node *&x){
if (x == NULL) return;
x->size = ;
x->Min = x->val;
if (x->ch[] != NULL) {x->Min = min(x->Min, x->ch[]->Min);x->size += x->ch[]->size;}
if (x->ch[] != NULL) {x->Min = min(x->Min, x->ch[]->Min);x->size += x->ch[]->size;}
}
void pushdown(Node *&x){//标记下传
if (x == NULL) return;
if (x->lazy){
int tmp = x->lazy;
x->val += tmp;
if (x->ch[] != NULL) {x->ch[]->lazy += tmp;x->ch[]->Min += tmp;}
if (x->ch[] != NULL) {x->ch[]->lazy += tmp;x->ch[]->Min += tmp;}
x->lazy = ;
}
if (x->turn){//翻转
swap(x->ch[], x->ch[]);//swap内部用什么实现的呢？ if (x->ch[] != NULL) x->ch[]->turn ^= ;
if (x->ch[] != NULL) x->ch[]->turn ^= ;
x->turn = ;
}
} //————————————————————————————
//旋转，1为右旋, 0为左旋
void Rotate(Node *&x, int d){//不用引用也可以
Node *y = x->parent;
pushdown(y);//注意顺序
pushdown(x);
pushdown(x->ch[d]);//这个不要忘了 y->ch[d ^ ] = x->ch[d];
if (x->ch[d] != NULL) x->ch[d]->parent = y;
x->parent = y->parent;
if (y->parent != NULL){
if (y->parent->ch[] == y) y->parent->ch[] = x;
else y->parent->ch[] = x;
}
x->ch[d] = y;
y->parent = x;
update(y);
if (y == root) root = x;//如果是引用要小心root被传下去
}
void debug(){
Node *p = new Node;
root = new Node;
root->ch[] = p;
p->parent = root;
printf("%d", p->cmp());
}
//注意我写的这个跟下午那个不一样，下午那个好麻烦
void splay(Node *&x, Node *&y){
pushdown(x);
while (x != y){
if(x->parent == y){
if (y->ch[] == x) Rotate(x, );
else Rotate(x,);
break;
}else{
Node *y = x->parent, *z = y->parent;//注意一定要这样弄一下
if (z->ch[] == y)
if (y->ch[] == x) Rotate(y,),Rotate(x, );
else Rotate(x, ), Rotate(x, );
else if (y->ch[] == x) Rotate(y, ), Rotate(x, );
else Rotate(x, ), Rotate(x, );
if (z == y) break;
}
update(x);
}
update(x);
}
//寻找第k大
void find(Node *&t, int k){
int tmp;
Node *p = root;
while (){
pushdown(p);
tmp = get(p->ch[]);
if (k == (tmp + )) break;
if (k <= tmp) p = p->ch[];
else {k -= tmp + , p = p->ch[];}
}
pushdown(p);
splay(p, t);
}
//插入操作
void Insert(int pos, int val){
//还是卡出来
find(root, pos + );
find(root->ch[], pos + );
Node *t = &mem[tot++], *x = root->ch[];
pushdown(root);
pushdown(x);
t->NEW(val);
//直接拆开放中间,放在root->ch[1]->ch[0]应该也可以
t->ch[] = x;
x->parent = t;
root->ch[] = t;
t->parent = root;
splay(x, root);
}
//区间加
void Add(int l, int r, int x){
find(root, l);
find(root->ch[] , r + );
Node *t = root->ch[]->ch[];
pushdown(t);
update(t);
t->Min += x;
t->lazy += x;
splay(t, root);
}
//翻转操作
void Reverse(int l, int r){
find(root, l);
find(root->ch[], r + );
root->ch[]->ch[]->turn ^= ;
Node *x = root->ch[]->ch[];
splay(x, root);
}
//交换操作,这一段我是看别人的....
void Revolve(int l, int r, int t){
Node *p1, *p2; find(root, l);
find(root->ch[], r + );
find(root->ch[]->ch[], r + - t); p1 = root->ch[]->ch[];
pushdown(p1);
p2 = p1->ch[];
p1->ch[] = NULL;
find(root->ch[]->ch[], l + );
p1 = root->ch[]->ch[];
pushdown(p1);
p1->ch[] = p2;
p2->parent = p1;
splay(p2, root);
}
int getMin(int l, int r){
find(root, l);
find(root->ch[], r + );
Node *x = root->ch[];
pushdown(x);
x = x->ch[];
pushdown(x);
update(x);
return x->Min;
}
void Erase(int pos){//删除
find(root, pos);
find(root->ch[], pos + );
pushdown(root->ch[]);
root->ch[]->ch[] = NULL;
Node *x = root->ch[];
splay(x, root);
}
void init(){
//注意还要加一个正无穷
tot = ;
root = &mem[tot++];
root->NEW(INF);
root->ch[] = &mem[tot++];
root->ch[]->NEW(INF);
}
void print(Node *t){
if (t == NULL) return;
print(t->ch[]);
printf("%d ", t->val);
if (t->parent != NULL) printf("%d\n", t->parent->val);
print(t->ch[]);
}
}A; int n, m;
//注意在这里为了防止掉到0，所以每个位置都要+1
void init(){//初始化
A.init();
scanf("%d", &n);
for (int i = ; i < n; i++){
int x;
scanf("%d", &x);
A.Insert(i, x);
//printf("%d\n", A.root->val);
}
//A.print(A.root);
}
void work(){
scanf("%d", &m);
for (int i = ; i <= m; i++){//询问,按顺序来。。
char str[];
scanf("%s", str);
if (str[] == 'A'){
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
A.Add(l, r, x);
}else if (str[] == 'R'){
int l, r;
scanf("%d%d", &l, &r);
if (str[] == 'E') A.Reverse(l, r);
else{
int x, len;
scanf("%d", &x);
len = r - l + ;
x = (x % len + len) % len;
if (x == || l == r) continue;//我开始居然傻逼的写在前面....
A.Revolve(l, r, x);
}
}else if (str[] == 'I'){
int l, x;
scanf("%d%d", &l, &x);
A.Insert(l, x);
}else if (str[] == 'D'){
int l;
scanf("%d", &l);
A.Erase(l);
}else if (str[] == 'M'){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", A.getMin(l, r));
}
}
}
void debug(){ } int main(){ init();
work();
//debug();
//A.debug();
return ;
}