luogu1110 [ZJOI2007]报表统计

上午有有人提起了这个题，翻了一下发现还没A。。。

当时写得一个set骗分，bzojAC但是luogu的模拟CCF的老爷机没A。

代码在这

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<map>
#include<queue>
#define inf 1000000000
using namespace std;
int n,m;
int st[500005],ed[500005];
multiset<int> a,b;
map<int,int> mp;
priority_queue<int,vector<int>,greater<int> > q;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void insert(int x)
{
    mp[x]++;
    if(mp[x]==1)a.insert(x);
}
void push(int x)
{
    int l=*--b.lower_bound(x),r=*b.lower_bound(x);
    q.push(min(x-l,r-x));
    b.insert(x);
}
int main()
{
    n=read();m=read();
    b.insert(inf);b.insert(-inf);
    for(int i=1;i<=n;i++)
    {
        int x=read();
        ed[i]=st[i]=x;
        push(x);
    }
    for(int i=2;i<=n;i++)insert(abs(st[i]-st[i-1]));
    char ch[12];int p,x,t;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch);
        if(ch[0]=='I')
        {
            p=read();x=read();
            if(p!=n)
            {
                t=abs(ed[p]-st[p+1]);
                mp[t]--;
                if(!mp[t])a.erase(t);
            }
            insert(abs(ed[p]-x));
            insert(abs(x-st[p+1]));
            ed[p]=x;push(x);
        }
        else if(ch[4]=='S')printf("%d\n",q.top());
        else printf("%d\n",*a.begin());
    }
    return 0;
}

竟然T了！我要卡常！

那就重新想想吧。

题目要求维护一坨数，能够随时插入，查询相邻的数的最小差值，查询任意两数间的最小差值。

第二问比较好写，由于set被卡了，于是写了个treap。。每次插入后查询一下前驱和后继更新一下答案。然后这个答案显然是递减的，所以数列中有相同的数之后就不用理了。

然而第一问就没法用treap做了。。把原数列存在map[]里面。

假设是在原数列第pos个元素后插入一个数x，那么x的右边的那个数就是map[pos+1]（如果$pos < n$的话）

x左边的那个数其实就是本来第pos个元素后面插了一坨数的最后一个，用last[i]表示当前（插入x之前）第i个元素后面插进去的一坨数的最后一个数的大小。

所以把x插进去后，原先的差值abs(last[pos]-map[pos+1])不存在了，新增了两个差值为abs(last[pos]-x)和abs(x-map[pos+1])

用优先队列（堆）维护下差值就好了。。。。。

具体姿势：

对于新增的差值abs(last[pos]-x)，它是不会被新增的数影响的。。然而abs(x-map[pos+1])可能因为之后在x后面插进去新的数而不存在。。。

判断这个差值存不存在就看x是不是所在元素的最后一次插入的数。每次查询的时候先把队头（小根堆顶）那些不存在的差值弹掉就行了。

事实证明这样写主要时间复杂度是在treap上= =。。。优先队列的速度比treap高明到不知道哪里去了。。treap的速度又比spaly高明到不知道哪里去了。。。

发现大部分的时间都是在treap建树的时候。。。所以直接把数列排序后递归建树。。。(参见文艺平衡树。)

我有特殊的卡常技巧23333

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=1000003;
const int inf=0x3f3f3f3f;
struct node
{
    int pos,len,val;
};
int num[maxn],rnd[maxn],l[maxn],r[maxn],last[maxn>>1],map[maxn>>1],len[maxn>>1];
int n,m,minsg,ming,tot,rt,x,a,b,nex,pre;
priority_queue<node>q;
bool operator <(node a,node b){return a.val>b.val;}
int ra,fh;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[11];
inline void outx(int x)
{
    while(x>0||!s[0])s[++s[0]]=x%10,x/=10;
    while(s[0])putchar(s[s[0]--]+48);putchar('\n');
}
inline void lturn(int &x,int R){r[x]=l[R],l[R]=x,x=R;}
inline void rturn(int &x,int L){l[x]=r[L],r[L]=x,x=L;}
void ins(int &x,int val)
{
    if(!x)
    {
        x=++tot,num[x]=val,rnd[x]=rand();
        return;
    }
    if(val<num[x])
    {
        ins(l[x],val);
        if(rnd[l[x]]<rnd[x])
            rturn(x,l[x]);
    }
    else if(val>num[x])
    {
        ins(r[x],val);
        if(rnd[r[x]]<rnd[x])
            lturn(x,r[x]);
    }
    else minsg=0;
}
void getpre(int now,int val)
{
    if(!now)return;
    if(num[now]>val)
        getpre(l[now],val);
    else
        pre=num[now],getpre(r[now],val);
}
void getnex(int now,int val)
{
    if(!now)return;
    if(num[now]<val)
        getnex(r[now],val);
    else
        nex=num[now],getnex(l[now],val);
}
inline void insert(int p,int x)
{
    if(minsg>0)
        pre=-inf,nex=inf,getpre(rt,x),getnex(rt,x),minsg=min(minsg,min(x-pre,nex-x));
    if(minsg>0)
        ins(rt,x);
    ming=min(ming,abs(last[p]-x));
    len[p]++;last[p]=x;
    if(p<n&&ming>0)
        q.push((node){ p,len[p],abs(map[p+1]-x) });
}
void build(int L,int R,int &now,int farnd)
{
    if(L>R)
        return;
    int mid=(L+R+1)>>1;
    now=++tot,num[now]=map[mid],rnd[now]=farnd+23333;
    build(L,mid-1,l[now],rnd[now]);
    build(mid+1,R,r[now],rnd[now]);
}
int main()
{
    n=read();m=read();
    minsg=ming=inf;
    for(int i=1;i<=n;i++)
        last[i]=map[i]=read();
    sort(map+1,map+1+n),rt=(n+1)>>1,build(1,n,rt,0);
    for(int i=1;i<n;i++)
        minsg=min(minsg,map[i+1]-map[i]);
    for(int i=1;i<n;i++)
        len[i]=1,q.push((node){ i,len[i],abs(last[i]-last[i+1]) });
    memcpy(map,last,(n+1)<<2);
    char ch1;
    while(m--)
    {
        for(ch1=getchar();ch1<'A'||ch1>'Z';ch1=getchar());
        if(ch1=='I')
            a=read(),b=read(),insert(a,b);
        else
        {
            ch1=getchar(),ch1=getchar(),ch1=getchar(),ch1=getchar();
            if(ch1=='S')outx(minsg);
            else
            {
                while(q.top().len!=len[q.top().pos])
                    q.pop();
                outx(min(ming,q.top().val));
            }
            while(ch1!='P')
                ch1=getchar();
        }
    }
}