北京化工大学1/17寒假集训题解（＞1800）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
A - 文艺平衡树
这里的Splay维护是按照的是序列中的编号排序
那么继续考虑其实最终的结果也就是整颗Splay的中序遍历平衡树的性质诶
那么现在如果按照权值来维护显然是不正确的
继续找找规律发现如果一个点在序列中的位置为第K个
那么他就是平衡树的第K大就当做普通的Splay来看的话
所以序列中的位置就变成了区间的第K大点
继续考虑如何翻转
翻转也就是整颗子树的每一个节点的左右儿子交换
因此只要在根节点的地方打一个标记
在旋转之前下方一下标记就行了
最后输出的时候输出的就是Splay的中序遍历
至于初始的Splay怎么建立可以直接构造完美的Splay
像我这种比较懒得直接弄了一个insert。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 200000
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Node
{
int ch[2];
int ff,v;
int size;
int mark;
void init(int x,int fa)
{
ff=ch[0]=ch[1]=0;
size=1;v=x;ff=fa;
}
}t[MAX];
int N,root,M,tot;
inline void pushup(int x)
{
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
}
inline void pushdown(int x)
{
if(t[x].mark)
{
t[t[x].ch[0]].mark^=1;
t[t[x].ch[1]].mark^=1;
t[x].mark=0;
swap(t[x].ch[0],t[x].ch[1]);
}
}
inline void rotate(int x)
{
int y=t[x].ff;
int z=t[y].ff;
int k=t[y].ch[1]==x;
t[z].ch[t[z].ch[1]==y]=x;
t[x].ff=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].ff=y;
t[x].ch[k^1]=y;
t[y].ff=x;
pushup(y);pushup(x);
}
inline void Splay(int x,int goal)
{
while(t[x].ff!=goal)
{
int y=t[x].ff;int z=t[y].ff;
if(z!=goal)
(t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
rotate(x);
}
if(goal==0)root=x;
}
inline void insert(int x)
{
int u=root,ff=0;
while(u)ff=u,u=t[u].ch[x>t[u].v];
u=++tot;
if(ff)t[ff].ch[x>t[ff].v]=u;
t[u].init(x,ff);
Splay(u,0);
}
inline int Kth(int k)
{
int u=root;
while(233)
{
pushdown(u);
if(t[t[u].ch[0]].size>=k)u=t[u].ch[0];
else if(t[t[u].ch[0]].size+1==k)return u;
else k-=t[t[u].ch[0]].size+1,u=t[u].ch[1];
}
}
void write(int u)
{
pushdown(u);
if(t[u].ch[0])write(t[u].ch[0]);
if(t[u].v>1&&t[u].v<N+2)printf("%d ",t[u].v-1);
if(t[u].ch[1])write(t[u].ch[1]);
}
inline void Work(int l,int r)
{
l=Kth(l);
r=Kth(r+2);
Splay(l,0);
Splay(r,l);
t[t[t[root].ch[1]].ch[0]].mark^=1;
}
int main()
{
N=read();M=read();
for(int i=1;i<=N+2;++i)insert(i);
while(M--)
{
int l=read(),r=read();
Work(l,r);
}
write(root);
printf("\n");
return 0;
}
B - 可持久化文艺平衡树
FHQ Treap其实是一种加强版的Treap。与一般的Treap树不同FHQ Treap不依赖旋转操作保持自身结构的平衡而是依赖分裂和合并操作维持树的平衡性质。
我们先来介绍一下关键操作:
代码如下
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define INF 0x3f3f3f3f
#define ls(p) tree[p].lson
#define rs(p) tree[p].rson
#define tls(p) tree[ls(p)]
#define trs(p) tree[rs(p)]
#define t(p) tree[p]
#define tpi t(++tot)
#define tp t(tot)
using namespace std;
const int N(2e5);
int n;ll lastans;
struct node
{
int rand,size,tag;
ll val,sum;
int lson,rson;
}tree[(N<<7)+10];
int rt[N+10];
inline int new_node(long long v=0)
{
static int tot(0);
tpi.val=v;tp.sum=v;
tp.rand=rand();tp.size=1;
return tot;
}
inline int copy_node(int p)
{
int ret=new_node();
tree[ret]=tree[p];
return ret;
}
inline void push_up(int p)
{
tree[p].size=tls(p).size+trs(p).size+1;
tree[p].sum=tls(p).sum+trs(p).sum+t(p).val;
}
inline void push_down(int p)
{
if(!t(p).tag)return;
if(ls(p))ls(p)=copy_node(ls(p));
if(rs(p))rs(p)=copy_node(rs(p));
swap(ls(p),rs(p));
if(ls(p))tls(p).tag^=1;
if(rs(p))trs(p).tag^=1;
tree[p].tag=0;
}
void split(int p,int k,int &x,int &y)
{
if(!p){x=y=0;return;}
push_down(p);
if(tls(p).size<k){x=copy_node(p);split(rs(x),k-tls(p).size-1,rs(x),y);push_up(x);}
else{y=copy_node(p);split(ls(y),k,x,ls(y));push_up(y);}
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
push_down(x);push_down(y);
if(t(x).rand<t(y).rand){rs(x)=merge(rs(x),y);push_up(x);return x;}
else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}
int main()
{
srand(224144);scanf("%d",&n);
int cnt(0);int v,op;ll a,b;int x,y,z;
while(n--)
{
scanf("%d%d",&v,&op);
if(op==1)
{
scanf("%lld%lld",&a,&b);
a^=lastans;b^=lastans;
split(rt[v],a,x,y);
rt[++cnt]=merge(merge(x,new_node(b)),y);
}
if(op==2)
{
scanf("%lld",&a);
a^=lastans;
split(rt[v],a,x,z);
split(x,a-1,x,y);
rt[++cnt]=merge(x,z);
}
if(op==3)
{
scanf("%lld%lld",&a,&b);
a^=lastans;b^=lastans;
split(rt[v],b,x,z);
split(x,a-1,x,y);
t(y).tag^=1;
rt[++cnt]=merge(merge(x,y),z);
}
if(op==4)
{
scanf("%lld%lld",&a,&b);
a^=lastans;b^=lastans;
split(rt[v],b,x,z);
split(x,a-1,x,y);
printf("%lld\n",lastans=t(y).sum);
rt[++cnt]=merge(merge(x,y),z);
}
}
return 0;
}C - 可持久化平衡树
主要思路FHQ Treap + 可持久化
普通FHQ Treap加上一点可持久化的东西如下(打上注释的代码是可持久化的特殊操作)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<stack>
using namespace std;
#define go(i,j,n,k) for(int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(int i=j;i>=n;i-=k)
#define rep(i,x) for(int i=h[x];i;i=e[i].nxt)
#define mn 500010
#define ld long double
#define fi first
#define se second
#define inf 1<<30
#define ll long long
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define bson l,r,rt
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct edge{
int ch[2], sze, pri;
ll w;
} z[mn * 50];
int rot[mn], xx, yy, zz, n, cnt;
inline void update(int rt) {
z[rt].sze = 1;
if(z[rt].ch[0]) z[rt].sze += z[z[rt].ch[0]].sze;
if(z[rt].ch[1]) z[rt].sze += z[z[rt].ch[1]].sze;
}
inline int newnode(ll w = 0) {
z[++cnt].w = w;
z[cnt].sze = 1;
z[cnt].pri = rand();
return cnt;
}
inline int merge(int x, int y) {
if(!x || !y) return x + y;
if(z[x].pri < z[y].pri) {
int rt = newnode();
z[rt] = z[x];
z[rt].ch[1] = merge(z[rt].ch[1], y);
update(rt);
return rt;
} else {
int rt = newnode();
z[rt] = z[y];
z[rt].ch[0] = merge(x, z[rt].ch[0]);
update(rt);
return rt;
}
}
inline void split(int rt, ll k, int &x, int &y) {
if(!rt) x = y = 0;
else {
if(z[rt].w <= k) {
x = newnode();
z[x] = z[rt];
split(z[x].ch[1], k, z[x].ch[1], y);
update(x);
} else {
y = newnode();
z[y] = z[rt];
split(z[y].ch[0], k, x, z[y].ch[0]);
update(y);
}
}
}
inline int findkth(int rt, int k) {
while(1119) {
if(k <= z[z[rt].ch[0]].sze)
rt = z[rt].ch[0];
else {
if(z[rt].ch[0]) k -= z[z[rt].ch[0]].sze;
if(!--k) return rt;
rt = z[rt].ch[1];
}
}
}
int main(){
n = read();
go(i, 1, n, 1) {
xx = yy = zz = 0;
int tmp = read(), s = read(); ll a = read();
rot[i] = rot[tmp];
if(s == 1) {
split(rot[i], a, xx, yy);
rot[i] = merge(merge(xx, newnode(a)), yy);
} else if(s == 2) {
split(rot[i], a, xx, zz);
split(xx, a - 1, xx, yy);
yy = merge(z[yy].ch[0], z[yy].ch[1]);
rot[i] = merge(merge(xx, yy), zz);
} else if(s == 3) {
split(rot[i], a - 1, xx, yy);
printf("%lld\n", z[xx].sze + 1);
rot[i] = merge(xx, yy);
} else if(s == 4) {
printf("%lld\n", z[findkth(rot[i], a)].w);
} else if(s == 5) {
split(rot[i], a - 1, xx, yy);
if(xx == 0) {
printf("-2147483647\n");
continue;
}
printf("%lld\n", z[findkth(xx, z[xx].sze)].w);
rot[i] = merge(xx, yy);
} else if(s == 6) {
split(rot[i], a, xx, yy);
if(yy == 0) {
printf("2147483647\n");
continue;
}
printf("%lld\n", z[findkth(yy, 1)].w);
rot[i] = merge(xx, yy);
}
}
return 0;
}D - 维护数列
首先要有一点splay维护区间操作的基础。
splay维护区间的基本原理就是将区间[l,r]的端点l-1,和r+1不断的通过伸展操作即splay到根将l-1伸展到根将r+1伸展到根的右儿子那么[l,r]这段区间就在根的右儿子的左儿子上了。
特别要注意的是==这里的l,r不是给出的区间端点的编号而是我们在平衡树的中序遍历中区间端点的编号。即在平衡树中排名(rank)为l,r的两个节点的真实编号而对于l=1或r=n的情况就非常特殊了我们有两种解决方案一种就是分类讨论将这4种情况枚举然后进行操作这么做固然可行但是当操作变多时会使整个程序显得繁琐并且难于调试。另一种解决方案就是建立虚拟节点我们把需要维护的区间全部变成[l+1,r+1]那么我们虚拟出一个1号节点和一个n+2号节点那么整个操作就显得十分自然了==。
那么问题就明显是一个splay的基本模板题了。而维护区间翻转在洛谷的P3391文艺平衡树中有更裸的题目。
这里一个操作一个操作的解决。
初始化
首先对于原序列我们不应该一个一个读入然后插入那么效率就是O(nlogn),而splay的常数本身就很大所以考虑一个优化就是把原序列一次性读入后直接类似线段树的build搞一个整体建树即不断的将当前点维护的区间进行二分到达单元素区间后就把对应的序列值插入进去这样我们一开始建的树就是一个非常平衡的树可以使后续操作的常数更小并且建树整个复杂度只是O(2n)的。
Insert操作
其次我们来考虑一下如何维护一个insert操作。我们可以这么做首先如上将需要insert的区间变成节点数目为tot的平衡树,然后把k+1注意我们将需要操作的区间右移了一个单位所以题目所给k就是我们需要操作的k+1移到根节点的位置把原树中的k+2移到根节点的右儿子的位置。然后把需要insert的区间先build成一个平衡树把需要insert的树的根直接挂到原树中k+1的左儿子上就行了。
Delete操作
再然后我们来考虑一下delete操作我们同样的把需要delete的区间变成[k+1,k+tot]注意是删去k后面的tot个数那么可以发现我们需要操作的原区间是[k,k+tot-1]!然后把k号节点移到根节点的位置把k+tot+2移到根节点的右儿子位置然后直接把k+tot+2的左儿子的指针清为0就把这段区间删掉了。可以发现比insert还简单一点。
Reverse操作
接下来这道题的重头戏就要开始了。splay的区间操作基本原理还类似于线段树的区间操作即延迟修改又称打懒标记。
对于翻转reverse操作我们依旧是将操作区间变成[k+1,k+tot]然后把k和k+tot+1分别移到对应根的右儿子的位置然后对这个右儿子的左儿子打上翻转标记即可。
Make-Same操作
对于Make-Same操作我们同样需要先将需要操作的区间变成[k+1,k+tot]然后把k和k+tot+1分别移到根和右儿子的位置然后对这个右儿子的左儿子打上修改标记即可。
Get-Sum操作
对于Get-Sum操作我们还是将操作区间变成[k+1,k+tot],然后把k和k+tot+1分别移到根和右儿子的位置然后直接输出这个右儿子的左儿子上的sum记录的和。
Max-Sum操作
对于这个求最大子序列的操作即Max-Sum操作我们不能局限于最开始学最大子序列的线性dp方法而是要注意刚开始基本很多书都会介绍一个分治的O(nlogn)的方法但是由于存在O(n)的方法导致这个方法并不受重视但是这个方法确实很巧妙当数列存在修改操作时线性的算法就不再适用了。
这种带修改的最大子序列的问题最开始是由线段树来维护具体来说就是对于线段树上的每个节点所代表的区间维护3个量lx表示从区间左端点l开始的连续的前缀最大子序列。rx表示从区间右端点r开始的连续的后缀最大子序列。mx表示这个区间中的最大子序列。
那么在合并[l,mid]和[mid+1,r]时就类似一个dp的过程了
懒标记的处理
最后相信认真看了的童鞋会有疑问这个标记怎么下传呢首先我们在每次将k和k+tot+1移到对应的位置时需要一个类似查找k大值的find操作即找出在平衡树中实际编号为k在树中中序遍历的编号这个才是我们真正需要处理的区间端点编号那么就好了我们只需在查找的过程中下传标记就好了其实线段树中也是这么做的因为我们所有的操作都需要先find一下所以我们可以保证才每次操作的结果计算出来时对应的节点的标记都已经传好了。而我们在修改时直接修改对应节点的记录标记和懒标记因为我们的懒标记记录的都是已经对当前节点产生贡献但是还没有当前节点的子树区间产生贡献然后就是每处有修改的地方都要pushup一下就好了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define rint register int
#define For(i,a,b) for (rint i=a;i<=b;++i)
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+17;
int n,m,rt,cnt;
int a[N],id[N],fa[N],c[N][2];
int sum[N],sz[N],v[N],mx[N],lx[N],rx[N];
bool tag[N],rev[N];
//tag表示是否有统一修改的标记rev表示是否有统一翻转的标记
//sum表示这个点的子树中的权值和v表示这个点的权值
queue<int> q;
inline int read(){
rint x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
inline void pushup(rint x){
rint l=c[x][0],r=c[x][1];
sum[x]=sum[l]+sum[r]+v[x];
sz[x]=sz[l]+sz[r]+1;
mx[x]=max(mx[l],max(mx[r],rx[l]+v[x]+lx[r]));
lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
}
//上传记录标记
inline void pushdown(rint x){
rint l=c[x][0],r=c[x][1];
if (tag[x]){
rev[x]=tag[x]=0;//我们有了一个统一修改的标记再翻转就没有什么意义了
if (l)tag[l]=1,v[l]=v[x],sum[l]=v[x]*sz[l];
if (r)tag[r]=1,v[r]=v[x],sum[r]=v[x]*sz[r];
if (v[x]>=0){
if (l)lx[l]=rx[l]=mx[l]=sum[l];
if (r)lx[r]=rx[r]=mx[r]=sum[r];
}else{
if (l)lx[l]=rx[l]=0,mx[l]=v[x];
if (r)lx[r]=rx[r]=0,mx[r]=v[x];
}
}
if (rev[x]){
rev[x]=0;rev[l]^=1;rev[r]^=1;
swap(lx[l],rx[l]);swap(lx[r],rx[r]);
//注意在翻转操作中前后缀的最长上升子序列都反过来了很容易错
swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);
}
}
//下传标记
inline void rotate(rint x,rint &k){
rint y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
if (y==k)k=x;else c[z][c[z][1]==y]=x;
fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
//旋转操作一定要上传记录标记
}
inline void splay(rint x,rint &k){
while (x!=k){
int y=fa[x],z=fa[y];
if (y!=k){
if (c[z][0]==y ^ c[y][0]==x)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
//这是整个程序的核心之一毕竟是伸展操作嘛
inline int find(rint x,rint rk){
pushdown(x);
//因为所有的操作都需要find所以我们只需在这里下传标记就行了
rint l=c[x][0],r=c[x][1];
if (sz[l]+1==rk)return x;
if (sz[l]>=rk)return find(l,rk);
else return find(r,rk-sz[l]-1);
}
//这个find是我们整个程序的核心之二
//因为我们的区间翻转和插入及删除的操作的存在
//我们维护的区间的实际编号并不是连续的
//而我们需要操作的区间又对应着平衡树的中序遍历中的那段区间
//所以这个find很重要
inline void recycle(rint x){
rint &l=c[x][0],&r=c[x][1];
if (l)recycle(l);
if (r)recycle(r);
q.push(x);
fa[x]=l=r=tag[x]=rev[x]=0;
}
//这就是用时间换空间的回收冗余编号机制很好理解
inline int split(rint k,rint tot){
rint x=find(rt,k),y=find(rt,k+tot+1);
splay(x,rt);splay(y,c[x][1]);
return c[y][0];
}
//这个split操作是整个程序的核心之三
//我们通过这个split操作找到[k+1,k+tot]并把k,和k+tot+1移到根和右儿子的位置
//然后我们返回了这个右儿子的左儿子这就是我们需要操作的区间
inline void query(rint k,rint tot){
rint x=split(k,tot);
printf("%d\n",sum[x]);
}
inline void modify(rint k,rint tot,rint val){
rint x=split(k,tot),y=fa[x];
v[x]=val;tag[x]=1;sum[x]=sz[x]*val;
if (val>=0)lx[x]=rx[x]=mx[x]=sum[x];
else lx[x]=rx[x]=0,mx[x]=val;
pushup(y);pushup(fa[y]);
//每一步的修改操作由于父子关系发生改变
//及记录标记发生改变我们需要及时上传记录标记
}
inline void rever(rint k,rint tot){
rint x=split(k,tot),y=fa[x];
if (!tag[x]){
rev[x]^=1;
swap(c[x][0],c[x][1]);
swap(lx[x],rx[x]);
pushup(y);pushup(fa[y]);
}
//同上
}
inline void erase(rint k,rint tot){
rint x=split(k,tot),y=fa[x];
recycle(x);c[y][0]=0;
pushup(y);pushup(fa[y]);
//同上
}
inline void build(rint l,rint r,rint f){
rint mid=(l+r)>>1,now=id[mid],pre=id[f];
if (l==r){
mx[now]=sum[now]=a[l];
tag[now]=rev[now]=0;
//这里这个tag和rev的清0是必要因为这个编号可能是之前冗余了
lx[now]=rx[now]=max(a[l],0);
sz[now]=1;
}
if (l<mid)build(l,mid-1,mid);
if (mid<r)build(mid+1,r,mid);
v[now]=a[mid]; fa[now]=pre;
pushup(now);
//上传记录标记
c[pre][mid>=f]=now;
//当mid>=f时now是插入到又区间取了所以c[pre][1]=now当mid<f时同理
}
inline void insert(rint k,rint tot){
For(i,1,tot)a[i]=read();
For(i,1,tot)
if (!q.empty())id[i]=q.front(),q.pop();
else id[i]=++cnt;//利用队列中记录的冗余节点编号
build(1,tot,0);//将读入的tot个树建成一个平衡树
rint z=id[(1+tot)>>1];//取中点为根
rint x=find(rt,k+1),y=find(rt,k+2);
//首先依据中序遍历找到我们需要操作的区间的实际编号
splay(x,rt);splay(y,c[x][1]);
//把k+1(注意我们已经右移了一个单位和(k+1)+1移到根和右儿子
fa[z]=y;c[y][0]=z;
//直接把需要插入的这个平衡树挂到右儿子的左儿子上去就好了
pushup(y);pushup(x);
//上传记录标记
}
//对于具体在哪里上传标记和下传标记
//可以这么记只要用了split就要重新上传标记
//只有find中需要下传标记
//但其实你多传几次是没有关系的但是少传了就不行了
int main(){
n=read(),m=read();
mx[0]=a[1]=a[n+2]=-inf;
For(i,1,n)a[i+1]=read();
For(i,1,n+2)id[i]=i;//虚拟了两个节点1和n+2然后把需要操作区间整体右移一个单位
build(1,n+2,0);//建树
rt=(n+3)>>1;cnt=n+2;//取最中间的为根
rint k,tot,val;char ch[10];
while (m--){
scanf("%s",ch);
if (ch[0]!='M' || ch[2]!='X') k=read(),tot=read();
if (ch[0]=='I')insert(k,tot);
if (ch[0]=='D')erase(k,tot);
if (ch[0]=='M'){
if (ch[2]=='X')printf("%d\n",mx[rt]);
else val=read(),modify(k,tot,val);
}
if (ch[0]=='R')rever(k,tot);
if (ch[0]=='G')query(k,tot);
}
return 0;
}E - 文本编辑器
平衡树的模板题。这里使用的是非旋Treap。由于这道题用平衡树维护的是文本所以只需要考虑文字之间的相对顺序因此之后所有对于树的split操作指的都是按照排名进行split。
不难想到用一个变量p存下来光标前面一个字符的下标下标从11开始。下面考虑对于题目中各个操作的处理
1.Move,Prev,Next对于这三个操作修改p即可。
2.Delete设文本为S。把树分成三个部分一个为x树对应[1,p]的文本一个为y树对应要删除的(p,p+n]的文本还有一个为z树对应(p+n,∣S∣]的文本。于是乎y树就是要删除的部分。我们直接将x树和z树合成新树即可。
3.Rotate同上把需要修改的部分提出来打标记。然后在拆分、修改的操作的时候下传标记即可。
4.Get相当于求文本中第p+1小的值。套板子。
5.Insert先把书分成两个部分一个为x树对应[1,p]另一个为z树对应(p,∣S∣]。下面有两种处理方法。一种是把要插入的串暴力一个一个字符地插入到x树然后合并x和z时间是可以过的但是显然效率很低另一种是对于要插入的串建立一颗y树再把x,y,z合并起来。因为我很懒我用的第一种方法。
由于出题人很恶心插入的时候有可能出现换行符也需要插入所以需要严格地按照输入的n来插入而不是用scanf之类的。同时如果Get需要输出换行符就只需要输出一个。
然后你就发现这道黑题就被这样愉快地水过去解决了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define random myRandom
const int MAXSIZ = 1024 * 1024 * 2 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
void swapp( _T &x, _T &y ) { _T t = x; x = y, y = t; }
int ch[MAXSIZ][2], aux[MAXSIZ], siz[MAXSIZ];
char val[MAXSIZ], S[MAXSIZ];
bool rot[MAXSIZ];
int nsiz, mpos = 0, rt;
void srd() { int a, *aa = &a; srand( ( unsigned long long ) aa ); }
int random() { return rand() * rand(); }
int newNode( const char c ) { aux[++ nsiz] = random(), siz[nsiz] = 1, val[nsiz] = c, rot[nsiz] = false; return nsiz; }
void upt( const int u ) { siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1; }
void swp( const int u ) { swapp( ch[u][0], ch[u][1] ), rot[u] ^= 1; }
void normalize( const int u )
{
if( ! rot[u] ) return ;
swp( ch[u][0] ), swp( ch[u][1] );
rot[u] = false;
}
void splitRnk( const int u, const int k, int &x, int &y )
{
if( ! u ) { x = y = 0; return ; }
normalize( u );
if( k <= siz[ch[u][0]] ) y = u, splitRnk( ch[u][0], k, x, ch[u][0] );
else x = u, splitRnk( ch[u][1], k - siz[ch[u][0]] - 1, ch[u][1], y );
upt( u );
}
int merg( const int u, const int v )
{
if( ! u || ! v ) return u + v;
if( aux[u] < aux[v] ) { normalize( u ), ch[u][1] = merg( ch[u][1], v ), upt( u ); return u; }
else { normalize( v ), ch[v][0] = merg( u, ch[v][0] ), upt( v ); return v; }
}
void insert( const char *buf )
{
int l = strlen( buf ), y;
splitRnk( rt, mpos, rt, y );
for( int i = 0 ; i < l ; i ++ ) rt = merg( rt, newNode( buf[i] ) );
rt = merg( rt, y );
}
void del( const int length )
{
int x, y;
splitRnk( rt, mpos, rt, x ),
splitRnk( x, length, x, y );
rt = merg( rt, y );
}
void rotate( const int length )
{
int x, y;
splitRnk( rt, mpos, rt, x ), splitRnk( x, length, x, y );
swp( x ), rt = merg( merg( rt, x ), y );
}
char Get()
{
int u = rt, k = mpos + 1;
while( true )
{
normalize( u );
if( k <= siz[ch[u][0]] ) u = ch[u][0];
else if( k <= siz[ch[u][0]] + 1 ) return val[u];
else k -= siz[ch[u][0]] + 1, u = ch[u][1];
}
}
int main()
{
srd();
char op[10];
int N, k;
read( N );
while( N -- )
{
scanf( "%s", op );
if( op[0] == 'M' ) { read( mpos ); }
if( op[0] == 'I' )
{
read( k );
for( int i = 0 ; i < k ; i ++ ) S[i] = getchar();
insert( S );
for( int i = 0 ; i < k ; i ++ ) S[i] = '\0';
}
if( op[0] == 'D' ) read( k ),
del( k );
if( op[0] == 'R' ) read( k ), rotate( k );
if( op[0] == 'G' )
{
char tmp; putchar( tmp = Get() );
if( tmp ^ '\n' ) putchar( '\n' );
}
if( op[0] == 'P' ) mpos --;
if( op[0] == 'N' ) mpos ++;
}
return 0;
}