首页 > 代码库 > HDU 4960 Handling the past 2014 多校9 线段树
HDU 4960 Handling the past 2014 多校9 线段树
首先确定的基本思想是按时间离散化后来建线段树，对于每个操作插入到相应的时间点上
但是难就难在那个pop操作，我之前对pop操作的处理是找到离他最近的那个点删掉，但是这样对于后面的peak操作，如果时间戳还在pop前面，那就需要还原之前的pop操作，这弄得很不方便
于是就有了一种类似扫描线的做法，对于push操作+1,pop操作-1，对于每次peak操作，从他这点往左走，找到第一个>0的点即可
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL __int64#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,rusing namespace std;const int N = 50010;int sum[N<<2],rsum[N<<2];int d[N<<2];int q[N],A[N],tmp[N],t[N];int n;void build(int rt,int l,int r){ sum[rt]=rsum[rt]=0; if (l>=r){ return; } int mid=(l+r)>>1; build(lson); build(rson);}void up(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; rsum[rt]=max(rsum[rt<<1|1],sum[rt<<1|1]+rsum[rt<<1]);}void update(int val,int pos,int loc,int rt,int l,int r){ if (l>=r){ sum[rt]=val; rsum[rt]=val; if (val>0) d[rt]=A[loc]; //if (val<0) rsum[rt]=0; return; } int mid=(l+r)>>1; if (pos<=mid) update(val,pos,loc,lson); else update(val,pos,loc,rson); up(rt);}int s;int query(int pos,int rt,int l,int r){ if (r<=pos){ if (s+rsum[rt]<=0){ s+=sum[rt]; return -1; } } if (l>=r){ return d[rt]; } int mid=(l+r)>>1; if (pos<=mid) return query(pos,lson); int res=-1; res=query(pos,rson); if (res!=-1) return res; return query(pos,lson);}int main(){ char str[10]; int kase=0; while (scanf("%d",&n)!=EOF) { if (n==0) break; for (int i=1;i<=n;i++){ scanf("%s",str); if (str[1]==‘u‘){ q[i]=1; scanf("%d%d",&A[i],&tmp[i]); } else if (str[1]==‘o‘){ q[i]=2; scanf("%d",&tmp[i]); } else{ q[i]=3; scanf("%d",&tmp[i]); } t[i]=tmp[i]; } printf("Case #%d:\n",++kase); sort(t+1,t+1+n); for (int i=1;i<=n;i++){ int pos=lower_bound(t+1,t+1+n,tmp[i])-t; tmp[i]=pos; //cout<<tmp[i]<<endl; } build(1,1,n); for (int i=1;i<=n;i++){ if (q[i]==1){ update(1,tmp[i],i,1,1,n); } else if (q[i]==2){ update(-1,tmp[i],i,1,1,n); } else{ if (tmp[i]<=1){ printf("-1\n"); continue; } s=0; int ans=query(tmp[i]-1,1,1,n); printf("%d\n",ans); } } } return 0;}
HDU 4960 Handling the past 2014 多校9 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。