题目描述

题解:

考虑到经过一系列变化后小数不可能比大数大,我们可以用线段树维护区间修改。

重点是,每个节点都可以通过$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 = ;
template<typename T>
inline void read(T&x)
{
T f = ,c = ;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}
x = f*c;
}
int n,m;
ll L,R;
char ch[];
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<<],t2[N<<],t3[N<<];
ll lp[N<<],rp[N<<],mx[N<<],mn[N<<];
void pushup(int x)
{
mx[x]=mx[x<<|];
mn[x]=mn[x<<];
}
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]!=||t2[x]||t3[x])
{
add(x<<,t1[x],t2[x],t3[x]);
add(x<<|,t1[x],t2[x],t3[x]);
t1[x]=,t2[x]=t3[x]=;
}
}
void build(int l,int r,int x)
{
t1[x]=,t2[x]=t3[x]=;
lp[x]=mn[x]=q[l].x,rp[x]=mx[x]=q[r].x;
if(l==r)return ;
int mid = (l+r)>>;
build(l,mid,x<<);build(mid+,r,x<<|);
}
void cl(int x)
{
if(mn[x]>=L)return ;
if(mx[x]<=L){add(x,,,L);return ;}
pushdown(x);
if(mx[x<<]<=L)add(x<<,,,L),cl(x<<|);
else cl(x<<);
pushup(x);
}
void cr(int x)
{
if(mx[x]<=R)return ;
if(mn[x]>=R){add(x,,,R);return ;}
pushdown(x);
if(mn[x<<|]>=R)add(x<<|,,,R),cr(x<<);
else cr(x<<|);
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)>>;
down(l,mid,x<<);
down(mid+,r,x<<|);
}
}tr;
int main()
{
// freopen("tt.in","r",stdin);
read(n),read(L),read(R);
for(int i=;i<=n;i++)
{
scanf("%s",ch);
read(p[i].y);
if(ch[]=='+')p[i].x=;
if(ch[]=='-')p[i].x=;
if(ch[]=='*')p[i].x=;
if(ch[]=='@')p[i].x=;
}
read(m);
for(int i=;i<=m;i++)
{
read(q[i].x),q[i].y=i;
}
sort(q+,q++m,cmp);
tr.build(,m,);
for(int i=;i<=n;i++)
{
if(p[i].x==)tr.add(,,,p[i].y);
if(p[i].x==)tr.add(,,,-p[i].y);
if(p[i].x==)tr.add(,p[i].y,,);
if(p[i].x==)tr.add(,,p[i].y,);
if(tr.mx[]>R)tr.cr();
if(tr.mn[]<L)tr.cl();
}
tr.down(,m,);
for(int i=;i<=m;i++)printf("%lld\n",ans[i]);
return ;
}

最新文章

  1. ViewPager及PagerTabStrip 的使用详解
  2. POJ1523 SPF[无向图割点]
  3. Jquery中的filter()详细说明和transition的用法
  4. 随笔 planetest
  5. SoapUI入门
  6. Eclipse下安装及配置maven项目管理工具
  7. Java RTTI和反射
  8. shell脚本练习
  9. [Jenkins]怎么删除jenkins里项目配置的svn记录
  10. 注册表检测office版本
  11. 高德地图测两点距离android比较精确的
  12. [BZOJ2879] [Noi2012] 美食节 (费用流 &amp; 动态加边)
  13. Docke--利用 commit 理解构建镜像
  14. JNDI是什么
  15. github 学习心得
  16. 关于MySQL大量数据分页查询优化
  17. cloudflare 加https、加SSL(加CF处理)实操流程
  18. opencv(4)实现数据增加小工具
  19. Java AES 加密工具类
  20. mysql5.6.23安装 步骤

热门文章

  1. E20180331-hm
  2. 分层图初探 By cellur925
  3. hdu3926 Hand in Hand 同构图
  4. hdu1863 畅通工程 基础最小生成树
  5. docker监控之cadvisor
  6. Codeforces Round #302 (Div. 1) 训练
  7. 牛客国庆集训派对Day_1~3
  8. android开发学习 ------- git - 将代码回滚到任意版本
  9. 访问TomCat出现的一些异常
  10. springmvc、springboot静态资源访问配置