Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 16524 | Accepted: 5214 | |
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
Source
POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu题意,模板,思路全都转自tabris大佬
题意:
给出一个数字序列,有6种操作:
(1) ADD x y d: 第x个数到第y个数加d 。
(2) REVERSE x y : 将区间[x,y]中的数翻转 。
(3) REVOLVE x y t :将区间[x,y]旋转t次,如1 2 3 4 5 旋转2次后就变成4 5 1 2 3 。
(4) INSERT x p :在第x个数后面插入p 。
(5)DELETE x :删除第x个数 。
(6) MIN x y : 查询区间[x,y]中的最小值 。
就是区间加,翻转,剪切,询问最值。点插入,删除。这几个操作
有翻转了 所以用SPLAY来维护一下
区间加 区间最小值就不说了 和普通的二叉搜索树一模一样.
点插入 删除
假如要插入的点在x
那么让x-1做为树根,x+1伸展到根节点下面,那么x+1的左儿子就是空出来的 加个值就好了
删除发过来一样的
区间操作
对于区间[l,r]
那么让l-1做为树根,r+1伸展到根节点下面,那么r+1的左儿子就是这个区间但为了更好的处理[1,n]这个区间 加上个0和n+1这两个节点
翻转
同样在一个二叉树中 翻转也就是让每个节点的两个儿子交换一下顺序就好了,, 打个标记 就行了,
旋转
总结下:splay 的区间操作,插入操作, 通常都是把左端-1旋转到根, 右端点+1旋转到根的右儿子, 那样 右端点+1 的左儿子就是区间 l-r 因为他要大于根 小于 他爸爸。 这些操作都是通过旋转,然后让一个节点变成一棵树,对这颗子树不断操作,lazy,rev什么的插入/删除节点的时候注意父节点要修改其实旋转说白了就是将这个区间分成两段然后交换一下子,
所以我们可以将后一个区间处理到一个子树上,然后放到 l−1,l 这两个节点之间,就好了,先减掉,然后在加上去就好了
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int INF = 1e9;
int n, m;
int ch[maxn][2]; //0做孩子, 1右孩子
int f[maxn]; //每个节点的父亲
int sz[maxn]; //每个节点为根子树的大小
int val[maxn]; //这个节点所表示的值
int cnt[maxn]; //这个节点所表示值的数量
int mi[maxn]; //这个节点子树的最小值
int rev[maxn]; //反转标记
int lazy[maxn]; //延迟标记
int root; // splay的根
int tot; //树所有的节点数量
void Swap(int &x, int &y)
{
x ^=y; y ^= x; x ^= y;
}
int Min(int x, int y)
{
return x < y ? x : y;
}
void update_rev(int x) //更新反转
{
if(!x) return;
Swap(ch[x][0], ch[x][1]);
rev[x] ^= 1; //如果这一层曾经被转过下面就不用转了, 把rev取消了
}
void update_add(int x, int v)
{
if(x) lazy[x] += v, val[x] += v, mi[x] += v;
}
void newnode(int rt, int v, int fa)
{
f[rt] = fa; sz[rt] = 1;
val[rt] = mi[rt] = v;
ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0; //加点的时候把所有的信息都更新了
}
void delnode(int rt) //为了回收空间,其实没什么太大的用处
{
f[rt] = val[rt] = sz[rt] = mi[rt] = 0;
ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0;
}
void pushup(int x) //跟线段树一样,从下往上不断更新
{
if(!x)return ;
sz[x] = 1, mi[x] = val[x];
if(ch[x][0]) sz[x] += sz[ch[x][0]], mi[x]= Min(mi[x],mi[ch[x][0]]); //更新个数跟当前子树最小值
if(ch[x][1]) sz[x] += sz[ch[x][1]], mi[x]= Min(mi[x],mi[ch[x][1]]);
}
void pushdown(int x) //向下传递lazy 跟 rev
{
if(!x) return;
if(lazy[x])
{
update_add(ch[x][0], lazy[x]);
update_add(ch[x][1], lazy[x]);
lazy[x] = 0;
}
if(rev[x])
{
update_rev(ch[x][0]);
update_rev(ch[x][1]);
rev[x] = 0;
}
}
void build(int &rt, int l, int r, int fa) //rt是节点编号,节点的大小代表了两个数位置的相对顺序
{ //一共tot个节点
if(l > r) return;
int mid = (r+l) >> 1;
rt = mid; newnode(rt, val[rt], fa);
build(ch[rt][0], l, mid-1, rt);
build(ch[rt][1], mid+1, r, rt);
pushup(rt);
}
void Rotate(int x, int k) // k = 0左旋, k = 1右旋
{
int y = f[x];int z = f[y];
pushdown(y); pushdown(x);
ch[y][!k] = ch[x][k];
if(ch[x][k]) f[ch[x][k]] = y;
f[x] = z;
if(z) ch[z][ch[z][1]==y] = x;
f[y] = x; ch[x][k] = y;
pushup(y), pushup(x);
}
void splay(int x, int goal)
{
pushdown(x);
while(f[x] != goal)
{
int y = f[x], z = f[y];
//在这里下传翻转标记,在rotate里下传标记可能会使树形改变导致旋转出错
pushdown(z); pushdown(y); pushdown(x);
if(f[y] == goal) Rotate(x, ch[y][0] == x);
else
{
int p = ch[f[y]][0] == y;
if(ch[y][p] == x) Rotate(x, !p), Rotate(x, p);
else Rotate(y, p), Rotate(x, p);
}
}
pushup(x);
if(goal == 0) root = x;
}
//以x为根的子树 的极值点 0 极小 1 极大
int extreme(int x,int k)
{
while(ch[x][k]) x = ch[x][k];
splay(x, 0); //所有操作之后都伸展下
return x;
}
//以节点编号x为根的子树 第k个数的节点编号
int kth(int x,int k)
{
pushdown(x);
if(sz[ch[x][0]]+1 == k) return x;
else if(sz[ch[x][0]] >= k) return kth(ch[x][0],k);
else return kth(ch[x][1], k-sz[ch[x][0]]-1);
}
//区间交换
void exchange(int l1,int r1,int l2,int r2)
{
int x = kth(root, l2-1), y = kth(root, r2+1);
splay(x,0), splay(y,x);
int tmp_right = ch[y][0]; ch[y][0]=0; //“剪贴下来”
x = kth(root, l1-1),y = kth(root, l1);
splay(x,0), splay(y,x);
ch[y][0] = tmp_right;
f[tmp_right] = y;
}
//区间翻转
void reversal(int l,int r)
{
int x = kth(root,l-1),y = kth(root,r+1);
splay(x,0); splay(y,x);
update_rev(ch[y][0]); //ch[y][0]就是l-r区间
}
//区间加
void add(int l,int r,int v)
{
int x = kth(root,l-1), y = kth(root,r+1);
// cout << 1 <<endl;
splay(x,0); splay(y,x);
update_add(ch[y][0],v); //ch[y][0]就是l-r区间
}
//在第k个数后插入值为x的节点
void Insert(int k,int x){
int r = kth(root, k),rr = kth(root, k+1);
splay(r,0), splay(rr,r);
newnode(++tot, x, rr); ch[rr][0] = tot; //节点个数增加
for(r = rr; r ; r = f[r]) pushdown(r), pushup(r);
splay(rr,0);
}
//删除第k位置的数
void Delete(int k)
{
splay(kth(root,k-1), 0);
splay(kth(root,k+1), root);
delnode(ch[ch[root][1]][0]);
ch[ch[root][1]][0] = 0;
pushup(ch[root][1]);
pushup(root);
}
// 获取区间最大值
//int get_max(int l,int r)
//{
// int x = kth(root,l-1), y = kth(root,r+1);
// splay(x,0); splay(y,x);
// return mx[ch[y][0]];
//}
//获取区间最小值
int get_min(int l,int r)
{
int x = kth(root,l-1), y = kth(root,r+1);
splay(x,0); splay(y,x);
return mi[ch[y][0]];
}
void init(int n)
{
root = 0;
//不断更新的, 不断插入的, 需要一个tot记录插入节点的编号
// tot = 0;
// newnode(++tot, -INF, 0);
// newnode(++tot, INF, root);
// ch[root][1] = tot;
f[0] = sz[0] = ch[0][0] = ch[0][1] = rev[0] = lazy[0] = 0; //rt编号多加两个,处理区间[1,n]
build(root, 1, n, 0);
pushup(root);
}
char s[12];
int main()
{
scanf("%d", &n);
val[1] = val[n+2] = INF; //多加两个编号0,n+1, 把区间1-n包起来
for(int i = 2;i <= n+1; i++) scanf("%d", &val[i]);
tot = n+2;
init(n+2);
scanf("%d",&m);
for(int i = 1; i <= m; i++){
int d, l, r;
scanf(" %s",s);
if(s[0]=='A')
{ //ADD
scanf("%d%d%d", &l, &r, &d);
add(l+1,r+1,d);
}
else if(s[0]=='I')
{ //INSERT
scanf("%d%d",&l,&d);
Insert(l+1,d);
}
else if(s[0]=='M')
{ //MIN
scanf("%d%d",&l,&r);
printf("%d\n",get_min(l+1,r+1));
}
else if(s[0]=='D')
{ //DELETE
scanf("%d",&l);
Delete(l+1);
}
else if(s[3]=='E')
{ //REVERSE
scanf("%d%d",&l,&r);
reversal(l+1, r+1); //增加了1一个节点全体后移一个
}
else
{ //REVOLVE
scanf("%d%d%d",&l,&r,&d);
d = d % (r-l+1);
if(d) exchange(l +1,r-d +1,r-d+1 +1,r +1);
}
}
return 0;
}
更多推荐
BZOJ 1895 & POJ 3580 supermemo (splay)
发布评论