网站基本信息设置/站内推广和站外推广的区别

传送门:bzoj3878

题解

$ds$功力还是太差了…膜了一下网上的题解才把代码写得比较简洁QWQ。

4种操作均可以操作$f(a,b,c)$表示，$f(x,a,b,c)=\min (\max (L,(a+b)x+c),R)$
定义：$f(a_1,b_1,c_1)+f(a_2,b_2,c_2)=f(a_1{a}_2,b_1{a}_2+b_2,c_1{a}_2+c_2)$。

发现函数是单调不降的，所以把数排序后相对大小不变，每次整体修改操作后二分下去前后缀超界的部分，强制改为$L/R$(即$+=f(0,0,L/R)$)即可。

代码

#include<bits/stdc++.h>
#define mid (l+r>>1)
#define lc k<<1
#define rc k<<1|1
#define lcc lc,l,mid
#define rcc rc,mid+1,r
typedef long long ll;
using namespace std;
const int N=1e5+10;ll dnn,upp;
int n,m,typ[N],val[N],ans[N];
struct Q{int v,id;bool operator <(const Q&ky)const{return v<ky.v;}}a[N];struct chg{ll a,b,c;chg(ll a_=1,ll b_=0,ll c_=0):a(a_),b(b_),c(c_){};void operator +=(chg ky){a*=ky.a,b=b*ky.a+ky.b,c=c*ky.a+ky.c;}inline ll cal(int x){return min(max(dnn,(a+b)*x+c),upp);}bool operator ==(const chg&ky)const{return (a==ky.a && b==ky.b && c==ky.c);}
}zz,ori;
struct node{chg l,r,lzy;}t[N<<2];char cp;
inline int init()
{for(;;){cp=getchar();if(cp=='+') return 1;if(cp=='-') return 2;if(cp=='*') return 3;if(cp=='@') return 4;}
}inline void col(node &k,chg p){k.lzy+=p;k.l+=p;k.r+=p;}chg dnp;
inline void pd(int k)
{if(t[k].lzy==ori) return;dnp=t[k].lzy;t[k].lzy=ori;col(t[lc],dnp);col(t[rc],dnp);
}inline void reb(int k,int l,int r)
{if(l^r){pd(k);reb(lcc);reb(rcc);}else ans[a[l].id]=t[k].l.cal(a[l].v);
}void sol(int k,int l,int r)
{if(l^r) pd(k);if((t[k].l.cal(a[l].v)>dnn)&&(t[k].r.cal(a[r].v)<upp)) return;if(t[k].l.cal(a[l].v)==upp){col(t[k],chg(0,0,upp));return;}if(t[k].r.cal(a[r].v)==dnn){col(t[k],chg(0,0,dnn));return;}sol(lcc);sol(rcc);t[k].l=t[lc].l;t[k].r=t[rc].r;
}int main(){int i;scanf("%d%lld%lld",&m,&dnn,&upp);for(i=1;i<=m;++i) {typ[i]=init();scanf("%d",&val[i]);}for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i].v),a[i].id=i;sort(a+1,a+n+1);for(i=1;i<=m;++i){switch(typ[i]){case 1:zz=chg(1,0,val[i]);break;case 2:zz=chg(1,0,-val[i]);break;case 3:zz=chg(val[i],0,0);break;case 4:zz=chg(1,val[i],0);break;}col(t[1],zz);sol(1,1,n);}reb(1,1,n);for(i=1;i<=n;++i) printf("%d\n",ans[i]);return 0;
}