社区讨论
代码挺短,帮忙看下呗
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 条回复,欢迎继续交流。
正在加载回复...