![AC日记——[ZJOI2007]报表统计 bzoj 1058](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "AC日记——[ZJOI2007]报表统计 bzoj 1058")
思路：
平衡树的题；
然而我的平衡树写一次炸一次QwQ；
而且各种tle；
所以stl水过；
代码：
#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 1000005 class HeadType {
private:
int head[maxn*],cnt; public:
bool size()
{
return cnt;
} int top()
{
if(!cnt) return 0x7fffffff;
return head[];
} inline void push(int x)
{
head[++cnt]=x;
int now=cnt,tmp;
while(now>)
{
if(head[now>>]>head[now]) tmp=head[now],head[now]=head[now>>],now>>=,head[now]=tmp;
else break;
}
} inline void pop()
{
head[]=head[cnt--];
if(cnt==) return ;
int pos,pos_,now=;
while()
{
pos=now,pos_=head[now];
if((now<<)<=cnt&&head[now<<]<head[pos]) pos=now<<,pos_=head[now<<];
if((now<<|)<=cnt&&head[now<<|]<head[pos]) pos=now<<|,pos_=head[now<<|];
if(pos==now) return ;
head[pos]=head[now],head[now]=pos_,now=pos;
}
}
};
class HeadType ai,bi,ci; struct ListType {
int pre,dis;
};
struct ListType bili[maxn]; int n,m,vi[maxn],tot; set<int>so; inline void in(int &now)
{
int if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} int main()
{
in(n),in(m);bili[].dis=1e9,bili[n+].dis=1e9,tot=n+;
for(int i=;i<=n;i++)
{
bili[i].pre=i-,in(bili[i].dis);
ai.push(abs(bili[i].dis-bili[i-].dis));
so.insert(bili[i].dis),vi[i]=bili[i].dis;
}
sort(vi+,vi+n+),bili[n+].pre=n,ai.push(abs(bili[n+].dis-bili[bili[n+].pre].dis));
for(int i=;i<=n;i++) ci.push(abs(vi[i]-vi[i-]));
char op[];int p,x;
for(;m--;)
{
scanf("%s",op);
if(op[]=='I')
{
in(p),in(x);p++;
bi.push(abs(bili[p].dis-bili[bili[p].pre].dis));
ai.push(abs(x-bili[bili[p].pre].dis)),ai.push(abs(bili[p].dis-x));
bili[++tot].pre=bili[p].pre,bili[tot].dis=x,bili[p].pre=tot;
set<int>::iterator it=so.lower_bound(x);
if(it!=so.end()) ci.push(abs(*it-x));
if(it!=so.begin()) it--,ci.push(abs(*it-x));
so.insert(x);
}
else if(op[]=='S') printf("%d\n",ci.top());
else
{
while(ai.top()==bi.top()) ai.pop(),bi.pop();
printf("%d\n",ai.top());
}
}
return ;
}
平衡树代码：
#pragma GCC optimize("O2")
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1000005
#define INF 0x7fffffff
class SplayTreeType {
private:
int ch[maxn][],key[maxn],minkey[maxn],size[maxn];
int pre[maxn],f[maxn];
public:
int ai[maxn],tot,root,n;
inline void updata(int now)
{
size[now]=,minkey[now]=abs(key[now]-pre[now]);
if(ch[now][]) size[now]+=size[ch[now][]],minkey[now]=min(minkey[now],minkey[ch[now][]]);
if(ch[now][]) size[now]+=size[ch[now][]],minkey[now]=min(minkey[now],minkey[ch[now][]]);
}
inline int tree_build(int l,int r,int fa)
{
int now=l+r>>;
key[now]=ai[now],pre[now]=ai[now-],f[now]=fa;
minkey[now]=abs(key[now]-pre[now]);
if(now>l) ch[now][]=tree_build(l,now-,now);
if(now<r) ch[now][]=tree_build(now+,r,now);
updata(now);return now;
}
inline void rotate(int now,int &to)
{
int fa=f[now],ffa=f[fa];bool pos=(ch[f[now]][]==now);
if(fa==to) to=now;
else if(ffa) ch[ffa][ch[f[fa]][]==fa]=now;
ch[fa][pos]=ch[now][pos^];
if(ch[fa][pos]) f[ch[fa][pos]]=fa;
ch[now][pos^]=fa,f[fa]=now,f[now]=ffa;
updata(fa);
}
inline void splay(int now,int &to)
{
while(now!=to)
{
int fa=f[now],ffa=f[fa];
if(fa!=to) rotate((ch[f[now]][]==now)==(ch[f[fa]][]==fa)?fa:now,to);
rotate(now,to);
}
updata(now);
}
inline void insert(int p,int ci)
{
splay(p+,root),pree();
ch[ch[root][]][]=++tot;
f[tot]=ch[root][],key[tot]=ci,pre[tot]=key[ch[root][]];
pre[root]=key[tot],updata(tot),updata(ch[root][]),updata(root);
}
inline void pree()
{
int now=ch[root][];
while(ch[now][]) now=ch[now][];
splay(now,ch[root][]);
}
inline void suff()
{
int now=ch[root][];
while(ch[now][]) now=ch[now][];
splay(now,ch[root][]);
}
inline void insert_(int ci)
{
int now=root,fa=;
while()
{
fa=now;
if(key[now]<=ci) now=ch[now][];
else now=ch[now][];
if(now==)
{
now=++tot;
ch[fa][ci>key[fa]]=now;
f[now]=fa,key[now]=ci,size[now]=;
splay(now,root),pree(),suff();
pre[root]=key[ch[root][]],pre[ch[root][]]=key[root];
updata(ch[root][]),updata(ch[root][]),updata(root);return ;
}
}
}
inline int query()
{
splay(,root),splay(n+,ch[root][]);
return minkey[ch[ch[root][]][]];
}
};
struct SplayTreeType ai,bi;
int n,m;
inline void in(int &now)
{
int if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
}
int main()
{
in(n),in(m);ai.tot=n+,bi.tot=n+,ai.n=n,bi.n=n;
for(int i=;i<=n+;i++) in(ai.ai[i]),bi.ai[i]=ai.ai[i];char op[];int u,v,x;
sort(bi.ai+,bi.ai+n+);bi.ai[]=-(INF-),bi.ai[bi.tot]=INF;
ai.root=ai.tree_build(,n+,),bi.root=bi.tree_build(,n+,);
for(;m--;)
{
scanf("%s",op);
if(op[]=='I') in(u),in(v),ai.insert(u,v),bi.insert_(v);
else if(op[]=='M')
{
if(op[]=='S') printf("%d\n",bi.query());
else printf("%d\n",ai.query());
}
}
return ;
}