题目描述
题解：
考虑到经过一系列变化后小数不可能比大数大，我们可以用线段树维护区间修改。
重点是，每个节点都可以通过$a[i]=a[i]*t1+a0[i]*t2+t3$这个函数来表示，我们就可以把三个标记一起维护。
代码：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int N = 100050;template<typename T>inline void read(T&x){ ???T f = 1,c = 0;char ch=getchar(); ???while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} ???while(ch>=‘0‘&&ch<=‘9‘){c=c*10+ch-‘0‘;ch=getchar();} ???x = f*c;}int n,m;ll L,R;char ch[2];struct Pair{ ???ll x,y;}p[N],q[N];bool cmp(Pair a,Pair b){return a.x<b.x;}ll ans[N];struct segtree{ ???ll t1[N<<2],t2[N<<2],t3[N<<2]; ???ll lp[N<<2],rp[N<<2],mx[N<<2],mn[N<<2]; ???void pushup(int x) ???{ ???????mx[x]=mx[x<<1|1]; ???????mn[x]=mn[x<<1]; ???} ???void add(int x,ll k1,ll k2,ll k3) ???{ ???????t1[x]*=k1; ???????t2[x]=t2[x]*k1+k2; ???????t3[x]=t3[x]*k1+k3; ???????mx[x]=mx[x]*k1+rp[x]*k2+k3; ???????mn[x]=mn[x]*k1+lp[x]*k2+k3; ???} ???void pushdown(int x) ???{ ???????if(t1[x]!=1||t2[x]||t3[x]) ???????{ ???????????add(x<<1,t1[x],t2[x],t3[x]); ???????????add(x<<1|1,t1[x],t2[x],t3[x]); ???????????t1[x]=1,t2[x]=t3[x]=0; ???????} ???} ???void build(int l,int r,int x) ???{ ???????t1[x]=1,t2[x]=t3[x]=0; ???????lp[x]=mn[x]=q[l].x,rp[x]=mx[x]=q[r].x; ???????if(l==r)return ; ???????int mid = (l+r)>>1; ???????build(l,mid,x<<1);build(mid+1,r,x<<1|1); ???} ???void cl(int x) ???{ ???????if(mn[x]>=L)return ; ???????if(mx[x]<=L){add(x,0,0,L);return ;} ???????pushdown(x); ???????if(mx[x<<1]<=L)add(x<<1,0,0,L),cl(x<<1|1); ???????else cl(x<<1); ???????pushup(x); ???} ???void cr(int x) ???{ ???????if(mx[x]<=R)return ; ???????if(mn[x]>=R){add(x,0,0,R);return ;} ???????pushdown(x); ???????if(mn[x<<1|1]>=R)add(x<<1|1,0,0,R),cr(x<<1); ???????else cr(x<<1|1); ???????pushup(x); ???} ???void down(int l,int r,int x) ???{ ???????if(l==r) ???????{ ???????????ans[q[l].y] = mx[x]; ???????????return ; ???????} ???????pushdown(x); ???????int mid = (l+r)>>1; ???????down(l,mid,x<<1); ???????down(mid+1,r,x<<1|1); ???}}tr;int main(){// ?freopen("tt.in","r",stdin); ???read(n),read(L),read(R); ???for(int i=1;i<=n;i++) ???{ ???????scanf("%s",ch); ???????read(p[i].y); ???????if(ch[0]==‘+‘)p[i].x=1; ???????if(ch[0]==‘-‘)p[i].x=2; ???????if(ch[0]==‘*‘)p[i].x=3; ???????if(ch[0]==‘@‘)p[i].x=4; ???} ???read(m); ???for(int i=1;i<=m;i++) ???{ ???????read(q[i].x),q[i].y=i; ???} ???sort(q+1,q+1+m,cmp); ???tr.build(1,m,1); ???for(int i=1;i<=n;i++) ???{ ???????if(p[i].x==1)tr.add(1,1,0,p[i].y); ???????if(p[i].x==2)tr.add(1,1,0,-p[i].y); ???????if(p[i].x==3)tr.add(1,p[i].y,0,0); ???????if(p[i].x==4)tr.add(1,1,p[i].y,0); ???????if(tr.mx[1]>R)tr.cr(1); ???????if(tr.mn[1]<L)tr.cl(1); ???} ???tr.down(1,m,1); ???for(int i=1;i<=m;i++)printf("%lld\n",ans[i]); ???return 0;}AHOI2014/JSOI2014 奇怪的计算器
原文地址：https://www.cnblogs.com/LiGuanlin1124/p/10351692.html