Luogu P1110 [ZJOI2007]报表统计 multiset

沿用了学长的$multiset$

然后这道题可以看到我的程序中有两行注释，它在我看来和他们下面的代码没区别，但是我们发现，C++会先调用后面的参数，所以$--it$会被先执行

。。。

维护两个数组，$a[]$和$b[]$表示每一段开头的元素和结尾的元素。

在更新相邻差值的时候，只用考虑新插入的值和原结尾的差以及和下一段开头的差就好了。

维护两个$multiset<int>ele,del$ 表示全部元素和表示全部差值。

插入新元素的时候，我们把他在$ele$中找到前驱后继分别作差，来更新排序最小差。

然后在del中删除现在本段结尾与下一段开头的差，插入新结尾与当前本段结尾的差和新值与下一段开头的差。

#include<cstdio>

#include<iostream>

#include<set>

#include<cmath>

#include<cstring>

#define R register int

using namespace std;

const int Inf=0x3f3f3f3f,N=;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

int n,m,a[N],b[N],ans=Inf;

multiset<int> del,ele;

multiset<int>::iterator it;

signed main() {

    n=g(),m=g(); ele.insert(Inf),ele.insert(-Inf);

    for(R i=;i<=n;++i) {

        a[i]=g(); it=ele.lower_bound(a[i]);

        //ans=min(ans,min(*it-a[i],a[i]-*--it));

        ans=min(ans,*it-a[i]); ans=min(ans,a[i]-*--it);

        ele.insert(a[i]);

    } memcpy(b,a,sizeof(int)*(n+)); for(R i=;i<=n;++i) del.insert(abs(a[i]-a[i-]));

    for(R i=;i<=m;++i) { register char s[]; scanf("%s",s);

        if(s[]=='R') {

            R p=g(),vl=g();

            del.erase(del.find(abs(b[p]-a[p+])));

            del.insert(abs(vl-b[p])),del.insert(abs(vl-a[p+])); b[p]=vl;

            it=ele.lower_bound(vl);

            //ans=min(ans,min(vl-*it,vl-*--it));

            ans=min(ans,*it-vl); ans=min(ans,vl-*--it);

            ele.insert(vl);

        } else if(s[]=='G') printf("%d\n",*del.begin());

        else printf("%d\n",ans);

    }

}

2019.07.11

巴特西

Luogu P1110 [ZJOI2007]报表统计 multiset

最新文章

热门文章