首页 > 代码库 > BZOJ 3878 【AHOI2014】 奇怪的计算器
BZOJ 3878 【AHOI2014】 奇怪的计算器
题目链接:奇怪的计算器
如果没有溢出的话,所有的标记都可以在线段树上直接维护,所以一棵线段树就解决问题了。
现在有了溢出,怎么办呢?
发现就算溢出了,各个元素的相对大小关系也是不变的。所以,如果一开始就把元素排好序,溢出的数一定是两端区间。在线段树上把这两段区间找出来,区间赋值就好了。当然也需要多记录区间\(\max\)和区间\(\min\)。
PS:注意各个标记的先后关系
下面贴代码(代码较丑):
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 100010 #define MAXN maxn<<2 using namespace std; typedef long long llg; struct data{ int x,b; bool operator < (const data &h)const{return x<h.x;} }b[maxn],s[maxn]; int n,m,ZL,ZR,a[maxn],ans[maxn]; llg maxv[MAXN],minv[MAXN],che[MAXN]; llg add1[MAXN],add2[MAXN],set[MAXN]; int getint(){ int w=0;bool q=0; char c=getchar(); while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar(); if(c==‘-‘) c=getchar(),q=1; while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } void gch(int u,int x){minv[u]*=x,maxv[u]*=x,che[u]*=x;} void ga1(int u,int x){minv[u]+=x,maxv[u]+=x,add1[u]+=x;} void gset(int u,int x){ set[u]=maxv[u]=minv[u]=x; add1[u]=add2[u]=0; che[u]=1; } void pushdown(int u,int l,int r){ int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1; if(set[u]) gset(lc,set[u]),gset(lv,set[u]); if(che[u]>1) gch(lc,che[u]),gch(lv,che[u]); if(add1[u]) ga1(lc,add1[u]),ga1(lv,add1[u]); if(add2[u]){ minv[lc]+=add2[u]*a[l]; maxv[lc]+=add2[u]*a[mid]; minv[lv]+=add2[u]*a[mid+1],maxv[lv]+=add2[u]*a[r]; add2[lc]+=add2[u],add2[lv]+=add2[u]; } set[u]=add1[u]=add2[u]=0; che[u]=1; } void update(int u){minv[u]=minv[u<<1],maxv[u]=maxv[u<<1|1];} void build(int u,int l,int r){ int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1; che[u]=1; if(l==r){maxv[u]=minv[u]=a[l];return;} build(lc,l,mid),build(lv,mid+1,r); update(u); } void queryl(){ if(maxv[1]<=ZL){gset(1,ZL);return;} int u=1,l=1,r=m,mid; while(l!=r){ pushdown(u,l,r); mid=(l+r)>>1; u<<=1; if(maxv[u]>=ZL) r=mid; else gset(u,ZL),l=mid+1,u^=1; } while(u>1) u>>=1,update(u); } void queryr(){ if(minv[1]>=ZR){gset(1,ZR);return;} int u=1,l=1,r=m,mid; while(l!=r){ pushdown(u,l,r); mid=(l+r)>>1; u<<=1; u|=1; if(minv[u]<=ZR) l=mid+1; else gset(u,ZR),r=mid,u^=1; } while(u>1) u>>=1,update(u); } void dfs(int u,int l,int r){ int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1; if(l==r) ans[s[l].b]=maxv[u]; else{ pushdown(u,l,r); dfs(lc,l,mid),dfs(lv,mid+1,r); } } int main(){ File("a"); n=getint(),ZL=getint(),ZR=getint(); for(int i=1;i<=n;i++){ char c=getchar(); while(c!=‘+‘ && c!=‘-‘ && c!=‘*‘ && c!=‘@‘) c=getchar(); b[i].x=getint(); if(c==‘+‘) b[i].b=1; if(c==‘-‘) b[i].b=2; if(c==‘*‘) b[i].b=3; if(c==‘@‘) b[i].b=4; } m=getint(); for(int i=1;i<=m;i++) s[i].x=getint(),s[i].b=i; sort(s+1,s+m+1); for(int i=1;i<=m;i++) a[i]=s[i].x; build(1,1,m); dfs(1,1,m); for(int i=1,x,tp;i<=n;i++){ tp=b[i].b,x=b[i].x; if(tp==1) ga1(1,x); if(tp==2) ga1(1,-x); if(tp==3) gch(1,x); if(tp==4) add2[1]+=x,minv[1]+=1ll*a[1]*x,maxv[1]+=1ll*a[m]*x; queryl(); queryr(); //dfs(1,1,m); } dfs(1,1,m); for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }
BZOJ 3878 【AHOI2014】 奇怪的计算器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。