社区讨论

代码挺短,帮忙看下呗

P1110[ZJOI2007] 报表统计参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo7o7p1n
此快照首次捕获于
2023/10/27 05:02
2 年前
此快照最后确认于
2023/10/27 05:02
2 年前
查看原帖
在#6输出了负数,应该输出0
然后我把负数特判成0:
CPP
		if(hes.top()<0) cout<<"0\n";
		else cout<<hes.top()<<endl;
就过了,,,,,,为啥啊
code:
全是STL,两堆一set
set 存了所有元素
堆:he装的是不排序的序列的差分,del 是它的删除堆
hes 装的是排序后的序列的差分, dels是它的删除堆
CPP
#include <bits/stdc++.h>
#define rep(a,b,c) for(register int a=b;a<=c;++a)
using namespace std;
const int N=5e5+500;
int n,cnt,m,a[N];
multiset<int> ful;
priority_queue<int,vector<int>,greater<int> > he,del,hes,dels; 
int ed[N],beg[N];
void init()
{
	cin>>n>>m;
	rep(i,1,n) 
	{
		cin>>a[i];
		ed[i]=beg[i]=a[i];
		ful.insert(a[i]);
		if(i>1) he.push(abs(a[i]-a[i-1]));
	}
	multiset<int>::iterator it=ful.begin(),pre;pre=it;it++;
	for(;it!=ful.end();++it)
	{
		hes.push(*it-*pre);
		pre=it;
	}
}
int main()
{
	//freopen("in.in","r",stdin);
	ios::sync_with_stdio(false);
	init();
	string s;
	rep(i,1,m)
	{
		cin>>s;
		if(s[4]=='R')
		{
			int t,x;cin>>t>>x;
			if(t!=n)
			del.push(abs(beg[t+1]-ed[t])),he.push(abs(beg[t+1]-x));
			he.push(abs(ed[t]-x));
			ed[t]=x;
			ful.insert(x);
			multiset<int>::iterator it=ful.find(x),nxt,pre;
			it++;nxt=it;
			it--;it--;pre=it;
			it++;
		//	cout<<*pre<<" "<<*nxt<<" "<<(nxt==ful.end())<<endl;
			if(nxt!=ful.end()&&it!=ful.begin()) dels.push(*(nxt)-*(pre));
			if(it!=ful.begin()) hes.push(*it-*(pre));
			if(nxt!=ful.end()) hes.push(*(nxt)-*it);
		}
		if(s[4]=='S')
		{
			while(dels.size()&&dels.top()==hes.top()) dels.pop(),hes.pop();
			if(hes.top()<0) cout<<"0\n";
			else cout<<hes.top()<<endl;
		}
		if(s[4]=='G')
		{
			while(del.size()&&del.top()==he.top()) he.pop(),del.pop();
			if(he.top()<0) cout<<"0\n";
			else cout<<he.top()<<endl;
		}
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...