[BZOJ 1058] 报表统计

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Link:

BZOJ 1058 传送门

Solution:

为了这道题今天下午一直都在和常数大战……

1、对于询问1，我们记录每个数末位置的数$T[i]$和初始位置$S[i]$

用平衡树维护所有差值，对于操作$i,k$：删除$S[i+1]-T[i]$，增加$x-T[i]$和$x-S[i+1]$

2、对于询问2，用平衡树记录所有值，每次找到$k$的前驱和后继更新$mn$就好了

当然以上都可以不用手写平衡树，用$multiset$和$priority\_ queue$可水过

但我如此耿直的人还是用结构体写了两个$Splay$分别维护两个询问

下面总结下出的各种锅和常数优化细节吧：

1、补锅匠系列：

（1）范围要开到$2*n$，毕竟每次会新加进一个数

这时显示的居然是$TLE$不是$RE$？以后要注意……

（2）对于询问2在查找前驱后继时要包含与查找数相同的数

此时不是严格小于/大于啊……

2、卡常系列：

（1）基础的IO，$register$，$inline$

（2）进行任何操作后最好都$Splay$一遍来保证复杂度！

（3）如果$mn=0$时直接将后面的更新剪枝，好像对$Luogu$上的数据很有效……

（4）尽量少外界调用结构体内函数

卡常卡到最后还是只过了$Luogu$，$BZOJ$过不去啊……

但好像$BZOJ$数据加强了，黄学长的标程也T了……

最后发现别人用$Treap$写比我的快10倍？以后还是少写$Splay$吧

Code:

#include <bits/stdc++.h>using namespace std;//注意MAXN要开到1e6
const int MAXN=1e6+,INF=0x3f3f3f3f;
char s[];int n,m,dat[MAXN],S[MAXN],T[MAXN],mn=INF;inline int read()
{
char ch;int num,f=;
while(!isdigit(ch=getchar())) f|=(ch=='-');
num=ch-'';
while(isdigit(ch=getchar())) num=num*+ch-'';
return f?-num:num;
}
inline void write(int x)
{
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}struct splay
{
int rt,sz[MAXN],cnt[MAXN],val[MAXN],f[MAXN],ch[MAXN][],tot;
inline void pushup(int x)
{sz[x]=sz[ch[x][]]+sz[ch[x][]]+cnt[x];}
inline void Rotate(int x)
{
int y=f[x],z=f[y],k=(ch[y][]==x);
ch[z][ch[z][]==y]=x;f[x]=z;
ch[y][k]=ch[x][k^];f[ch[x][k^]]=y;
ch[x][k^]=y;f[y]=x;
pushup(x);pushup(y);
}
inline void Splay(int x,int up)
{
while(f[x]!=up)
{
int y=f[x],z=f[y];
if(z!=up) (ch[y][]==x)^(ch[z][]==y)?Rotate(x):Rotate(y);
Rotate(x);
}
if(!up) rt=x;
}
inline void Insert(int x)
{
int k=rt,anc=;
while(k&&x!=val[k])
anc=k,k=ch[k][x>val[k]]; if(k) {cnt[k]++;Splay(k,);return;}
k=++tot;
if(anc) ch[anc][x>val[anc]]=k;
ch[k][]=ch[k][]=;
sz[k]=cnt[k]=;f[k]=anc;val[k]=x;
Splay(k,);
}
inline void Find(int x)
{
int k=rt;
while(ch[k][x>val[k]]&&x!=val[k])
k=ch[k][x>val[k]];
Splay(k,);
}
inline int Kth(int x)
{
int k=rt;
while(true)
{
if(sz[ch[k][]]+cnt[k]<x)
x-=sz[ch[k][]]+cnt[k],k=ch[k][];
else if(sz[ch[k][]]>=x) k=ch[k][];
else return k;
}
}
inline int Next(int x,int flag)
{
Find(x);int k=rt;
if((val[k]<x&&!flag)||(val[k]>x&&flag)) return k;
k=ch[k][flag];
while(ch[k][flag^]) k=ch[k][flag^];
Splay(k,);return k;
}
inline int Next2(int x,int flag)
{
Find(x);int k=rt;
if((val[k]<=x&&!flag)||(val[k]>=x&&flag)) return k;
k=ch[k][flag];
while(ch[k][flag^]) k=ch[k][flag^];
Splay(k,);return k;
}
inline void Delete(int x)
{
int nxt=Next(x,),lst=Next(x,);
Splay(lst,);Splay(nxt,lst);
if(cnt[ch[nxt][]]>)
cnt[ch[nxt][]]--,Splay(ch[nxt][],);
else ch[nxt][]=;
}
inline void push(int x)
{//调用结构体函数的次数越少越好，因此push放里面快
if(!mn) return;
int nxt=Next2(x,),lst=Next2(x,);
mn=min(mn,min(abs(val[nxt]-x),abs(val[lst]-x)));
Insert(x);
}
}all,adj;int main()
{
n=read();m=read();
all.Insert(INF);all.Insert(-INF);
adj.Insert(INF);adj.Insert(-INF);
for(register int i=;i<=n;i++)
dat[i]=read(),all.push(dat[i]),S[i]=T[i]=dat[i];
for(register int i=;i<=n;i++) adj.Insert(abs(dat[i]-dat[i-])); while(m--)
{
int x,y;scanf("%s",s);
if(s[]=='I')
{
x=read();y=read();
if(x!=n) adj.Delete(abs(S[x+]-T[x]));
adj.Insert(abs(y-T[x]));
adj.Insert(abs(y-S[x+]));
all.push(y);T[x]=y;
}
else if(s[]=='G') write(adj.val[adj.Kth()]),putchar('\n');
else write(mn),putchar('\n');
}
return ;
}