洛谷.1110.[ZJOI2007]报表统计(Multiset Heap)

题目链接

主要思路

/*
对于询问1,用堆代替multiset/Splay
对于询问2,multiset
1.注意哨兵元素
2.注意multiset中删除时是删除某元素的一个位置,而不是这个元素!这个值会全部都删掉
*/
#include<set>
#include<cstdio>
#include<cctype>
#include<algorithm>
const int N=5e5+5,M=N*3,INF=1e9; int n,q,st[N],ed[N],Min=INF;
std::multiset<int> A;
std::multiset<int>::iterator it;
struct Heap
{
int sz,A[M];
inline int Top()
{
return A[1];
}
void Push(int x)
{
A[++sz]=x;
int now=sz,nxt=now>>1;
while(now>1 && A[nxt]>A[now])
std::swap(A[nxt],A[now]), now=nxt, nxt=now>>1;
}
void Pop()
{
A[1]=A[sz--];
int now=1,nxt;
while(now<<1<=sz)
{
nxt=now<<1;
if(A[nxt]>A[nxt+1] && nxt<sz) ++nxt;
if(A[nxt]>=A[now]) break;
std::swap(A[now],A[nxt]);
now=nxt;
}
}
}h1,h2; inline int read()
{
int now=0,f=1;register char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=getchar());
return now*f;
}
void Ins(int v)
{
it=A.lower_bound(v);
Min=std::min(Min,*it-v);
Min=std::min(Min,v-(*--it));
A.insert(v);
}
void Modify()
{
int p=read(),v=read();
if(p!=n)
h2.Push(std::abs(st[p+1]-ed[p])),
h1.Push(std::abs(st[p+1]-v));
h1.Push(std::abs(ed[p]-v));
ed[p]=v;
if(Min) Ins(v);
}
inline int Query()
{
while(h1.Top()==h2.Top()) h1.Pop(),h2.Pop();
return h1.Top();
} int main()
{
// freopen("form.in","r",stdin);
// freopen("form.out","w",stdout); n=read(),q=read();
A.insert(-INF), A.insert(INF);
st[1]=ed[1]=read(),Ins(st[1]);
for(int i=2;i<=n;++i)
st[i]=ed[i]=read(),h1.Push(std::abs(st[i]-st[i-1])),Ins(st[i]);
char s[20];int p,v;
while(q--)
{
scanf("%s",s);
if(s[0]=='I') Modify();
else if(s[4]=='G') printf("%d\n",Query());
else printf("%d\n",Min);
} return 0;
}
上一篇:字符串匹配-BF算法和KMP算法


下一篇:redis递减,过期返回值