zcmimi's blog

查看原题

点击跳转

考虑离线

把所有数排序后,可以发现经过4种操作后所有数还是有序的

这样我们维护区间加,区间乘,区间加变形,区间覆盖

#include<bits/stdc++.h>
typedef long long ll;
const int N=100011,P=1000000007;
int n,m,L,R,ans[N];
struct que{int op,v;}q[N];
struct qwq{
    int v,id;
    bool operator<(const qwq&t){return v<t.v;}
}a[N];
#define ls rt<<1
#define rs rt<<1|1
struct node{
    int l,r;ll mi,mx,lu,lv,lw;
    void upd(int u,int v,int w){// val=val*u+a[i]*v+w
        lu*=u,lv=lv*u+v,lw=lw*u+w;
        mi=mi*u+1ll*a[l].v*v+w;
        mx=mx*u+1ll*a[r].v*v+w;
    }
}s[N<<2];
void build(int l,int r,int rt){
    s[rt]=(node){l,r,a[l].v,a[r].v,1,0,0};
    if(l==r)return;
    int m=l+r>>1;
    build(l,m,ls),build(m+1,r,rs);
}
void pd(int rt){
    s[ls].upd(s[rt].lu,s[rt].lv,s[rt].lw);
    s[rs].upd(s[rt].lu,s[rt].lv,s[rt].lw);
    s[rt].lu=1,s[rt].lv=s[rt].lw=0;
}
void pu(int rt){s[rt].mi=s[ls].mi,s[rt].mx=s[rs].mx;}
void setL(int rt){
    if(s[rt].l==s[rt].r)return s[rt].upd(0,0,L);
    pd(rt);
    if(s[rs].mi<L)s[ls].upd(0,0,L),setL(rs);
    else setL(ls);
    pu(rt);
}
void setR(int rt){
    if(s[rt].l==s[rt].r)return s[rt].upd(0,0,R);
    pd(rt);
    if(s[ls].mx>R)s[rs].upd(0,0,R),setR(ls);
    else setR(rs);
    pu(rt);
}
void travel(int rt){
    if(s[rt].l==s[rt].r){ans[a[s[rt].l].id]=s[rt].mi;return;}
    pd(rt),travel(ls),travel(rs);
}
int main(){
    scanf("%d%d%d",&m,&L,&R);
    char c[5];
    for(int i=1;i<=m;++i){
        scanf("%s%d",c,&q[i].v);
        if(c[0]=='+')q[i].op=1;
        else if(c[0]=='-')q[i].op=2;
        else if(c[0]=='*')q[i].op=3;
        else q[i].op=4;
    }
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i].v),a[i].id=i;
    std::sort(a+1,a+n+1),build(1,n,1);
    for(int i=1;i<=m;++i){
        if(q[i].op==1)s[1].upd(1,0,q[i].v);
        else if(q[i].op==2)s[1].upd(1,0,-q[i].v);
        else if(q[i].op==3)s[1].upd(q[i].v,0,0);
        else s[1].upd(1,q[i].v,0);

        if(s[1].mi<L)setL(1);
        if(s[1].mx>R)setR(1);
    }
    travel(1);
    for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
}
LG 4041 [AHOI2014 or JSOI2014]奇怪的计算器
comment评论
Search
search