AHOI2014/JSOI2014 奇怪的计算器
2024-09-30 09:59:40
题解:
考虑到经过一系列变化后小数不可能比大数大,我们可以用线段树维护区间修改。
重点是,每个节点都可以通过$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 ;
}
最新文章
- ViewPager及PagerTabStrip 的使用详解
- POJ1523 SPF[无向图割点]
- Jquery中的filter()详细说明和transition的用法
- 随笔 planetest
- SoapUI入门
- Eclipse下安装及配置maven项目管理工具
- Java RTTI和反射
- shell脚本练习
- [Jenkins]怎么删除jenkins里项目配置的svn记录
- 注册表检测office版本
- 高德地图测两点距离android比较精确的
- [BZOJ2879] [Noi2012] 美食节 (费用流 &; 动态加边)
- Docke--利用 commit 理解构建镜像
- JNDI是什么
- github 学习心得
- 关于MySQL大量数据分页查询优化
- cloudflare 加https、加SSL(加CF处理)实操流程
- opencv(4)实现数据增加小工具
- Java AES 加密工具类
- mysql5.6.23安装 步骤