神秘物质 bzoj-4864 BeiJing-2017-Wc
题目大意：给定一个长度为n的序列，支持插入，将相邻两个元素合并并在该位置生成一个指定权值的元素；查询：区间内的任意一段子区间的最大值减最小值的最大值或最小值。
注释：$1\le n,m \le 10^5$，m为操作个数。
想法：如果用非旋转Treap的话，前两个操作就是傻逼操作。后两个操作也都比较简单：
1.如果是最大极差，我们就是将这个区间的最大值-最小值即可。
2.最小极差的话，显然只能是相邻两个数的差的绝对值的最小值，这东西也可以合并，那非旋转Treap维护一下即可。
最后，附上丑陋的代码... ...
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 102333
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int inf=0x3fbbbbbb;
inline void read(int &x)
{
x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
}
int n,m;
struct Node
{
int ls,rs,size,key,e,maxx,minn,minr,le,re;
}a[N<<1];
struct par{int x,y;};
inline void update(int x)
{
int ls=a[x].ls,rs=a[x].rs;
a[x].size=1,a[x].maxx=a[x].minn=a[x].le=a[x].re=a[x].e,a[x].minr=inf;
if(ls)
{
a[x].size+=a[ls].size;
a[x].maxx=max(a[x].maxx,a[ls].maxx);
a[x].minn=min(a[x].minn,a[ls].minn);
a[x].le=a[ls].le;
a[x].minr=min(a[x].minr,min(a[ls].minr,abs(a[ls].re-a[x].e)));
}
if(rs)
{
a[x].size+=a[rs].size;
a[x].maxx=max(a[x].maxx,a[rs].maxx);
a[x].minn=min(a[x].minn,a[rs].minn);
a[x].re=a[rs].re;
a[x].minr=min(a[x].minr,min(a[rs].minr,abs(a[rs].le-a[x].e)));
}
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(a[x].key>a[y].key)
{
a[x].rs=merge(a[x].rs,y);update(x);
return x;
}
a[y].ls=merge(x,a[y].ls);update(y);
return y;
}
par split(int x,int k)
{
if(!k)return (par){0,x};
int ls=a[x].ls,rs=a[x].rs;
if(k==a[ls].size)
{
a[x].ls=0;update(x);
return (par){ls,x};
}
if(k==a[ls].size+1)
{
a[x].rs=0;update(x);
return (par){x,rs};
}
if(k<a[ls].size)
{
par t=split(ls,k);
a[x].ls=t.y;update(x);
return (par){t.x,x};
}
par t=split(rs,k-a[ls].size-1);
a[x].rs=t.x;update(x);
return (par){x,t.y};
}
int e[N],cnt,root;
inline int makenew(int val)
{
a[++cnt].size=1;
a[cnt].e=a[cnt].maxx=a[cnt].minn=a[cnt].le=a[cnt].re=val;
a[cnt].key=rand(),a[cnt].minr=inf;
return cnt;
}
int build(int l,int r)
{
if(l==r)return makenew(e[l]);
int mid=(l+r)>>1;
return merge(build(l,mid),build(mid+1,r));
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)read(e[i]);
root=build(1,n);
char s[10];
for(int x,y,i=1;i<=m;i++)
{
scanf("%s",s);
read(x);read(y);
if(s[1]=='e')
{
par t1=split(root,x+1),t2=split(t1.x,x-1);
root=merge(merge(t2.x,makenew(y)),t1.y);
}
else if(s[1]=='n')
{
par t=split(root,x);
root=merge(merge(t.x,makenew(y)),t.y);
}
else if(s[1]=='a')
{
par t1=split(root,y),t2=split(t1.x,x-1);
printf("%d\n",a[t2.y].maxx-a[t2.y].minn);
root=merge(merge(t2.x,t2.y),t1.y);
}
else if(s[1]=='i')
{
par t1=split(root,y),t2=split(t1.x,x-1);
printf("%d\n",a[t2.y].minr);
root=merge(merge(t2.x,t2.y),t1.y);
}
}
return 0;
}
小结：非旋转Treap真的是神一样的数据结构...