code vs 1343 蚱蜢

蚱蜢"/>

code vs 1343 蚱蜢

1343 蚱蜢

 

省队选拔赛湖南

 时间限制: 5 s  空间限制: 64000 KB  题目等级 : 大师 Master 题解  查看运行结果

题目描述 Description

有N个蚱蜢排成一排，它们按下列两种方式移动：

位置A上的蚱蜢向左跳过B个蚱蜢 （表示为A L B）

位置A上的蚱蜢向右跳过B个蚱蜢（表示为A D B）

所有蚱蜢的高度不一定相同，当一个蚱蜢跳跃时，不能碰到其它蚱蜢的腿，也就是说跳跃的高度不低于最高的一个蚱蜢。给出跳跃的顺序，输出它们跳跃的高度。

输入描述 Input Description

第一行为两个整数N和J (2 ≤ N ≤ 100 000, 1 ≤ J ≤ 100 000), 表示有N个蚱蜢排成一排，有J个蚱蜢跳跃。

第二行有N个整数（N<100000），表示蚱蜢高度。

后面有J行，每行为一个蚱蜢跳跃的信息，每行三个数，第一个是整数A表示跳跃蚱蜢的位置（相对位置，最左边的蚱蜢位置为1，最右边的蚱蜢位置为N）。第二个数为跳跃的方向( 'L' 向左， 'D' 向右)，第三个是整数B表示跳跃的蚱蜢所跃过的蚱蜢数，每个跳跃都是有效的（即B少于或等于蚱蜢A相应边的蚱蜢数）

输出描述 Output Description

输出共J行，每行一个数，表示蚱蜢跳跃的最少高度

样例输入 Sample Input

9 3

5 3 8 4 9 3 7 4 2

2 D 3

8 L 2

5 D 2

样例输出 Sample Output

9

7

4

数据范围及提示 Data Size & Hint

第一个蚱蜢跳过的高度为8, 4 和 9的蚱蜢。下一个蚱蜢跳过高度为 3 和 7的蚱蜢，最后一个蚱蜢跳过高度为 3 和 4的蚱蜢.

题解：平衡树splay

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000010
using namespace std;
int n,m,root,sz,a[100010];
int size[N],ch[N][3],fa[N],key[N],delta[N],tm[N],pos[N];
const int inf=1e9;
void clear(int x)
{size[x]=ch[x][0]=ch[x][1]=fa[x]=delta[x]=tm[x]=key[x]=0;
}
void update(int x)
{size[x]=size[ch[x][0]]+size[ch[x][1]]+1;tm[x]=max(key[x],max(tm[ch[x][0]],tm[ch[x][1]]));
}
int get(int x)
{return ch[fa[x]][1]==x;
}
void rotate(int x)
{int y=fa[x]; int z=fa[y]; int which=get(x);ch[y][which]=ch[x][which^1]; fa[ch[y][which]]=y;ch[x][which^1]=y; fa[y]=x; fa[x]=z;if (z) ch[z][ch[z][1]==y]=x;update(y); update(x);
}
void splay(int x,int tar)
{for (int f;(f=fa[x])!=tar;rotate(x))if (fa[f]!=tar) rotate(get(x)==get(f)?f:x);if (!tar) root=x;
}
int build(int l,int r,int f)
{if (l>r) return 0;int mid=(l+r)/2; int now=++sz; key[now]=tm[now]=a[mid]; fa[now]=f;int lson=build(l,mid-1,now); int rson=build(mid+1,r,now);ch[now][0]=lson; ch[now][1]=rson; update(now);return now;
}
int find(int x)
{int now=root; int temp=0;while (true){if (x<=size[ch[now][0]])now=ch[now][0];else{temp=(ch[now][0]?size[ch[now][0]]:0)+1;if (x==temp)  return now;x-=temp; now=ch[now][1];}}
}
int main()
{scanf("%d%d",&n,&m);a[1]=-inf; a[n+2]=inf;for (int i=1;i<=n;i++)scanf("%d",&a[i+1]);root=build(1,n+2,0);for (int i=1;i<=m;i++){char s[1]; int x,y; scanf("%d%s%d",&x,&s,&y);x++;if (s[0]=='L'){int l=find(x-y-1); int r=find(x);splay(l,0); splay(r,root);printf("%d\n",tm[ch[ch[root][1]][0]]);l=find(x-1); r=find(x+1); splay(l,0); splay(r,root); int num=key[ch[ch[root][1]][0]]; clear(ch[ch[root][1]][0]);ch[ch[root][1]][0]=0; update(ch[root][1]); update(root);l=find(x-y-1); r=find(x-y);splay(l,0); splay(r,root);ch[ch[root][1]][0]=++sz; clear(sz); size[sz]=1;key[sz]=tm[sz]=num; fa[sz]=ch[root][1]; update(ch[root][1]); update(root);}else{int l=find(x); int r=find(x+y+1);splay(l,0);splay(r,root);printf("%d\n",tm[ch[ch[root][1]][0]]);l=find(x-1); r=find(x+1);splay(l,0); splay(r,root); int num=key[ch[ch[root][1]][0]]; clear(ch[ch[root][1]][0]);ch[ch[root][1]][0]=0; update(ch[root][1]); update(root);l=find(x+y-1); r=find(x+y);splay(l,0); splay(r,root);ch[ch[root][1]][0]=++sz; clear(sz); size[sz]=1;key[sz]=tm[sz]=num; fa[sz]=ch[root][1]; update(ch[root][1]); update(root);	}}
}