BZOJ 3878 [AHOI&JSOI2014]奇怪的计算器 (线段树)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题面：BZOJ传送门洛谷传送门

线段树好题

题目保证$a$一定是正整数，容易发现计算结果是单调的

我们把询问离线，并按照从小到大排序

某次操作可能导致某些位置达到边界$L/R$

根据单调性的结论

这些位置一定是从$1$向右扩展或者$Q$向左扩展

可以二分找到这个区间，然后区间覆盖

那么修改操作，归根结底是这$4$种操作：

1.区间加减 2.区间乘法 3.区间覆盖 4.区间每个位置加某个数*对应位置的固定权值

比较复杂，考虑抽象化这个问题，把它写成一个函数

$f(a,b,c)=a*f(a,b,c)+b*X_{i}+c$

上述四种操作变成

$1.f(1,0,x) 2.(x,0,0) 3.(0,0,x) 4.(1,x,0)$

我们只需要每次把值往里面带，然后用线段树维护这个函数就行了

注意下推标记的顺序

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 100010

 #define ll long long

 using namespace std;

 int gint()

 {

     int ret=,fh=; char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n;

 ll ml,mr;

 struct node{int id,x;ll ans;}q[N1];

 int cmp1(node s1,node s2){return s1.x<s2.x;}

 int cmp2(node s1,node s2){return s1.id<s2.id;}

 int v[N1],p[N1],f[N1],m;

 struct SEG{

 #define M1 (N1<<2)

 ll mi[M1],ma[M1],a[M1],b[M1],c[M1];

 void pushup(int rt)

 {

     mi[rt]=mi[rt<<];

     ma[rt]=ma[rt<<|];

 }

 void pushdown(int l,int r,int rt)

 {

     int mid=(l+r)>>;

     if(a[rt]==&&!b[rt]&&!c[rt]) return;

     a[rt<<]=a[rt]*a[rt<<];

     a[rt<<|]=a[rt]*a[rt<<|];

     b[rt<<]=a[rt]*b[rt<<]+b[rt];

     b[rt<<|]=a[rt]*b[rt<<|]+b[rt];

     c[rt<<]=a[rt]*c[rt<<]+c[rt];

     c[rt<<|]=a[rt]*c[rt<<|]+c[rt];

     mi[rt<<]=a[rt]*mi[rt<<]+b[rt]*v[l]+c[rt];

     mi[rt<<|]=a[rt]*mi[rt<<|]+b[rt]*v[mid+]+c[rt];

     ma[rt<<]=a[rt]*ma[rt<<]+b[rt]*v[mid]+c[rt];

     ma[rt<<|]=a[rt]*ma[rt<<|]+b[rt]*v[r]+c[rt];

     a[rt]=; b[rt]=c[rt]=;

 }

 void update(int L,int R,int l,int r,int rt,ll A,ll B,ll C)

 {

     if(L<=l&&r<=R)

     {

         a[rt]=A*a[rt];

         b[rt]=A*b[rt]+B;

         c[rt]=A*c[rt]+C;

         mi[rt]=A*mi[rt]+B*v[l]+C;

         ma[rt]=A*ma[rt]+B*v[r]+C;

         return;

     }

     int mid=(l+r)>>;

     if(L<=mid) update(L,R,l,mid,rt<<,A,B,C);

     if(R>mid) update(L,R,mid+,r,rt<<|,A,B,C);

     pushup(rt);

 }

 ll calc1(int x,ll rt,ll A,ll B,ll C){return A*mi[rt]+B*v[x]+C;}

 ll calc2(int x,ll rt,ll A,ll B,ll C){return A*ma[rt]+B*v[x]+C;}

 ll de;

 int qleft(int l,int r,int rt,int A,int B,int C)

 {

     if(l==r){ if(calc2(r,rt,A,B,C)>ml) return l-; return l; }

     int mid=(l+r)>>; pushdown(l,r,rt); de=calc2(mid,rt<<,A,B,C);

     if(calc2(mid,rt<<,A,B,C)<=ml) return qleft(mid+,r,rt<<|,A,B,C);

     else return qleft(l,mid,rt<<,A,B,C);

 }

 int qright(int l,int r,int rt,int A,int B,int C)

 {

     if(l==r){ if(calc1(l,rt,A,B,C)<mr) return l+; return l; }

     int mid=(l+r)>>; pushdown(l,r,rt); de=calc1(mid+,rt<<|,A,B,C);

     if(calc1(mid+,rt<<|,A,B,C)>=mr) return qright(l,mid,rt<<,A,B,C);

     else return qright(mid+,r,rt<<|,A,B,C);

 }

 void build(int l,int r,int rt)

 {

     a[rt]=; b[rt]=c[rt]=;

     if(l==r){ mi[rt]=ma[rt]=v[l]; return; }

     int mid=(l+r)>>;

     build(l,mid,rt<<);

     build(mid+,r,rt<<|);

     pushup(rt);

 }

 void print(int l,int r,int rt,node *s)

 {

     if(l==r){ s[l].ans=mi[rt]; return; }

     int mid=(l+r)>>; pushdown(l,r,rt);

     print(l,mid,rt<<,s);

     print(mid+,r,rt<<|,s);

 }

 ll query(int x,int l,int r,int rt)

 {

     if(l==r) return mi[rt];

     int mid=(l+r)>>; pushdown(l,r,rt);

     if(x<=mid) return query(x,l,mid,rt<<);

     else return query(x,mid+,r,rt<<|);

 }

 }s;

 int main()

 {

     scanf("%d%lld%lld",&n,&ml,&mr);

     char str[]; int i,j,l,r;

     for(i=;i<=n;i++)

     {

         scanf("%s",str);

         switch(str[])

         {

             case '+': p[i]=; break;

             case '-': p[i]=; break;

             case '*': p[i]=; break;

             case '@': p[i]=; break;

         }

         f[i]=gint();

     }

     scanf("%d",&m);

     for(i=;i<=m;i++) q[i].x=gint(),q[i].id=i;

     sort(q+,q+m+,cmp1);

     for(i=;i<=m;i++) v[i]=q[i].x;

     s.build(,m,);

     s.query(,,m,);

     for(i=;i<=n;i++)

     {

         switch(p[i])

         {

         case :

         {

             l=s.qright(,m,,,,f[i]),r=m;

             if(l>) s.update(,l-,,m,,,,f[i]);

             if(l<=r) s.update(l,r,,m,,,,mr);

             break;

         }

         case :

         {

             l=s.qleft(,m,,,,-f[i]),r=m;

             if(l>) s.update(,l,,m,,,,ml);

             if(l<r) s.update(l+,r,,m,,,,-f[i]);

             break;

         }

         case :

         {

             l=s.qright(,m,,f[i],,),r=m;

             if(l>) s.update(,l-,,m,,f[i],,);

             if(l<=r) s.update(l,r,,m,,,,mr);

             break;

         }

         case :

         {

             l=s.qright(,m,,,f[i],),r=m;

             if(l>) s.update(,l-,,m,,,f[i],);

             if(l<=r) s.update(l,r,,m,,,,mr);

             break;

         }

         }

     }

     s.print(,m,,q);

     sort(q+,q+m+,cmp2);

     for(i=;i<=m;i++) printf("%lld\n",q[i].ans);

     return ;

 }