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, {A1A2, ... An}. 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 {Ax ... Ay}. 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 {Ax ... Ay}. 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 {Ax ... AyT 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 Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
  5. DELETE x: delete Ax. 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 {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 (≤ 100000).

The following n lines describe the sequence.

Then follows 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

【分析】
跟维修数列类似,不过多了几个操作,还需要合并。
还有点问题。
 #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 ;
}

最新文章

  1. Hibernate学习之hibernate.cfg.xml
  2. Hive 字符串操作[转]
  3. Android下常见动画
  4. 解决 Virtual Box 启动 Cannot load R0 module supLoadModule returned VERR_LDR_MISMATCH_NATIVE Failed to register ourselves as a PCI Bus (VERR_MODULE_NOT_FOUND)
  5. API爬虫--Twitter实战
  6. P1699: [Usaco2007 Jan]Balanced Lineup排队
  7. linux 安装xamp
  8. MYI 文件内容
  9. BZOJ 4291: [PA2015]Kieszonkowe 水题
  10. jQuery 参考手册 - 效果
  11. 【NOIP】OpenJudge - 15-02:财务管理
  12. Ionic3 遇到的一些错误-Error: Cannot find module &#39;reflect-metadata&#39;
  13. FiddlerCoreAPI开发(一)源码分析
  14. android注解入门 并来自己写一个框架
  15. VMware 虚拟机 linux执行 ifconfig 命令 eth0没有IP地址(intet addr、Bcast、Mask) UP BROADCAST MULTICAST 问题
  16. 《Android进阶之光》--RxJava结合Retrofit访问网络
  17. python --- 15 装饰器
  18. BZOJ2321 [BeiJing2011集训] 星器
  19. CCCC 月饼
  20. 干货分享:五大最适合学习AI开发的编程语言

热门文章

  1. 转 -- MVC+EF easyui dataGrid 动态加载分页表格
  2. (转载)JavaScript中的日期格式转换
  3. (转载)ubuntu安装pyton-pip问题解决
  4. Poj 2478-Farey Sequence 欧拉函数,素数,线性筛
  5. 《算法问题实战策略》-chaper15-计算几何-线段相交
  6. C++Primer第5版学习笔记(四)
  7. hdu 1081 矩阵最大连续子序列
  8. effective C++ 读后笔记
  9. there be 句型
  10. 还原dede数据后系统基本参数空白栏目无显示的解决方法