BZOJ 1058 [ZJOI2007]报表统计

题目描述

传送门

题目分析

操作看上去都不是很困难的样子。

插入操作好像不落俗套，考虑使用一个\(vector\)，每次搞一下当前块的最后值和下一个的开头，记录一下即可。

第二个操作看上去，可以写个堆，或者写个平衡树，应该都可以维护。

第三个操作就是平衡树。。。

考虑偷懒，使用俩可重集，第一个维护相邻的差，第二个维护数列。

不开\(O2\)很慢，开了\(O2\)也不快。

洛谷过了，被BZOJ教做人了。

考虑插入时可不可以优化，发现可以。

新插入的数与它前面的的差值不会发生变化，考虑用一个变量直接维护。

发现收敛的比较快，当收敛到0时，就不用搞平衡树操作了。

瞬间就卡过去了。

是代码呢

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+7;
const int inf=1e9+7;
multiset<int> st,nul;
vector<int> a[MAXN];
int n,m,min1=inf,min2=inf;
char s[100];
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    while(ch=='-')c*=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
inline void change(int x)
{
    multiset<int>::iterator it=st.lower_bound(x);
    int nw=*it-x;
    it--;
    nw=min(nw,x-*it);
    min2=min(min2,nw);
    st.insert(x);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++){
        int x=read();
        a[i].push_back(x);
    }
    st.insert(inf);
    st.insert(-inf);
    for(int i=1;i<n;i++) nul.insert(abs(a[i+1][0]-a[i][0]));
    for(int i=1;i<=n;i++){
        change(a[i][0]);
    }
    while(m--){
        scanf("%s",s);
        if(s[0]=='I'){
            int id=read(),v=read();
            if(min2!=0) change(v);
            if(min1==0) continue;
            int pre=a[id].back();
            min1=min(abs(v-pre),min1);
            if(id!=n){
                int nxt=a[id+1][0];
                nul.erase(nul.find(abs(nxt-pre)));
                nul.insert(abs(nxt-v));
            }
            a[id].push_back(v);
        } else if(s[4]=='G') printf("%d\n", min(*nul.begin(),min1));
        else printf("%d\n",min2);
    }
}

BZOJ 1058 [ZJOI2007]报表统计

原文：https://www.cnblogs.com/victorique/p/10282517.html