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;
}
上一篇:【转】linux服务器性能查看


下一篇:Nginx使用的php-fpm的两种进程管理方式及优化(转)