Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 11004 | Accepted: 3461 | |
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
5 1 2 3 4 5 2 ADD 2 4 1 MIN 4 5
Sample Output
5
Splay的经典操作。注意revolve里的t可能为负数也可能很大,对b-a+1取模。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f
#define key_rt ch[ch[root][1]][0]
#define maxn 200010
#define lc ch[x][0]
#define rc ch[x][1]
typedef long long LL;
struct Splay
{
int ch[maxn][2],par[maxn],size[maxn];
LL key[maxn], mini[maxn], add[maxn];
bool rev[maxn];
int root, tot;
int a[maxn];
inline void push_up(int x)
{
size[x]=1+size[lc]+size[rc];
mini[x]=min(mini[lc], min(mini[rc], key[x]));
}
void update_rev(int x)
{
if(x==0) return;
rev[x]=1-rev[x];
swap(ch[x][0], ch[x][1]);
}
void update_add(int x, LL v)
{
if(x==0) return;
add[x]+=v;
key[x]+=v;
mini[x]+=v;
}
void push_down(int x)
{
if(rev[x]){
update_rev(lc);
update_rev(rc);
rev[x]=0;
}
if(add[x]){
update_add(lc, add[x]);
update_add(rc, add[x]);
add[x]=0;
}
}
void newnode(int &rt, int p, int k)
{
tot++;
rt=tot;
par[rt]=p;
ch[rt][0]=ch[rt][1]=0;
key[rt]=k;
mini[rt]=k;
size[rt]=1;
rev[rt]=0;
}
void build(int &rt, int l, int r, int p)
{
if(l>r){
rt=0;
return;
}
int m=(l+r)>>1;
newnode(rt, p, a[m]);
build(ch[rt][0], l, m-1, rt);
build(ch[rt][1], m+1, r, rt);
push_up(rt);
}
void init(int n)
{
for(int i=1; i<=n; i++) scanf("%d", a+i);
size[0]=par[0]=ch[0][0]=ch[0][1]=0;
key[0]=inf; mini[0]=inf;
tot=0;
newnode(root, 0, inf);
newnode(ch[root][1], root, inf);
build(key_rt, 1, n, ch[root][1]);
push_up(ch[root][1]);
push_up(root);
}
void rotate(int x, int k)
{
if(x==root) return;
int y=par[x];
push_down(y);
push_down(x);
ch[y][!k]=ch[x][k];
par[ch[x][k]]=y;
ch[x][k]=y;
if(par[y])
ch[par[y]][ch[par[y]][1]==y]=x;
par[x]=par[y];
par[y]=x;
if(y==root)
root=x;
push_up(y);
}
void splay(int x, int t)
{
int y,yy;
while(par[x]!=t){
y=par[x]; yy=par[y];
if(yy==t){
push_down(y);
rotate(x, ch[y][0]==x);
}
else{
push_down(yy); push_down(y);
int k= (ch[yy][0]==y);
if(ch[y][k]==x){
rotate(x,!k);
rotate(x, k);
}
else{
rotate(y, k);
rotate(x, k);
}
}
}
push_up(x);
}
int get_kth(int k)
{
int x=root;
push_down(x);
while(size[lc]!=k-1){
if(size[lc]>k-1)
x=lc;
else{
k-=size[lc]+1;
x=rc;
}
push_down(x);
}
return x;
}
void get(int a, int b)
{
splay(get_kth(a), 0);
splay(get_kth(b+2), root);
}
LL get_min(int a, int b)
{
get(a,b);
return mini[key_rt];
}
void Add(int a, int b, LL v)
{
get(a,b);
update_add(key_rt, v);
}
void Reverse(int a, int b)
{
get(a,b);
update_rev(key_rt);
}
void Insert(int k, LL v)
{
get(k+1, k);
newnode(key_rt, ch[root][1], v);
push_up(ch[root][1]);
push_up(root);
}
void Remove(int k)
{
get(k, k);
key_rt=0;
push_up(ch[root][1]);
push_up(root);
}
void Revolve(int a, int b, int t)
{
if(t==0 || t%(b-a+1)==0) return;
if(t>0){
t%=(b-a+1);
get(b-t+1, b); //向右revolve t次,相当于将尾部t个放到最前面,先删除再插入
int tmp=key_rt;
key_rt=0;
push_up(ch[root][1]);
push_up(root);
get(a,a-1); //插入到第a个前面把第a-1提到根节点,a提到根节点下,key_rt就是对应的插入位置
key_rt=tmp;
par[tmp]=ch[root][1];
push_up(ch[root][1]);
push_up(root);
}
else{
t=-t;
t%=(b-a+1);
get(a,a+t-1);
int tmp=key_rt;
key_rt=0;
push_up(ch[root][1]);
push_up(root);
get(b-t+1, b-t);
key_rt=tmp;
par[tmp]=ch[root][1];
push_up(ch[root][1]);
push_up(root);
}
}
void solve(int n)
{
init(n);
int m;
char s[20];
scanf("%d", &m);
int a,b,c;
while(m--){
scanf("%s", s);
if(s[0]=='A'){
scanf("%d%d%d", &a, &b, &c);
Add(a,b,c);
}
else if(s[0]=='R'&&s[3]=='E'){
scanf("%d%d", &a, &b);
Reverse(a,b);
}
else if(s[0]=='R'){
scanf("%d%d%d", &a, &b, &c);
Revolve(a,b,c);
}
else if(s[0]=='I'){
scanf("%d%d", &a, &b);
Insert(a,b);
}
else if(s[0]=='D'){
scanf("%d",&a);
Remove(a);
}
else{
scanf("%d%d",&a,&b);
printf("%I64d\n", get_min(a,b));
}
}
}
};
Splay tree;
int main()
{
int n;
while(scanf("%d", &n)==1 && n){
tree.solve(n);
}
return 0;
}
更多推荐
poj 3580 区间翻转、插入、删除、循环位移
发布评论