bzoj 1058: [ZJOI2007]报表统计【set】

我想写FHQtreap的！是set自己跑进代码的！因为太好写了

是有点慢……洛谷上不吸氧会T一个点

就是，用一个set p维护所有点值，ans维护MIN_SORT_GAP的答案，每次insert一个点的时候都查一下它在p里的前驱后继，更新一下ans即可；用一个multiset c维护差分后的序列，a[i]表示第i个位置的开头数字，b[i]表示结尾数字，每次在x位置新插入值v的时候都要c.erase(c.find(abs(a[x+1]-b[x]))),c.insert(abs(a[x+1]-v))，c.insert(abs(v-b[x]))（这个应该很好理解）然后查询的时候直接找begin即可

差分的时候注意一下边界

想要快的话大概是线段树+树上二分代替p，平衡树代替set？

#include<iostream>

#include<cstdio>

#include<set>

#include<algorithm>

using namespace std;

const int N=500005;

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

char o[20];

set<int>p;

multiset<int>c;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

	{

		a[i]=b[i]=read();

		if(i>1)

		{

			c.insert(abs(a[i]-a[i-1]));

			set<int>::iterator it=p.lower_bound(a[i]);

			if(it!=p.end())

				ans=min(ans,(*it)-a[i]);//,cerr<<a[i]<<" "<<*it<<endl;

			if(it!=p.begin())

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

		}

		p.insert(a[i]);

	}

	while(m--)

	{

		scanf("%s",o+1);

		if(o[1]=='I')

		{

			int x=read(),v=read();

			set<int>::iterator it=p.lower_bound(v);

			if(it!=p.end())

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

			if(it!=p.begin())

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

			p.insert(v);

			if(x<n)

				c.erase(c.find(abs(a[x+1]-b[x]))),c.insert(abs(a[x+1]-v));

			c.insert(abs(v-b[x]));

			b[x]=v;

		}

		else if(o[5]=='G')

			printf("%d\n",*c.begin());

		else

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

	}

	return 0;

}

巴特西

bzoj 1058: [ZJOI2007]报表统计【set】

最新文章

热门文章