自动搬运

查看原文

来自洛谷，原作者为

	ldxcaicai **

搬运于2025-08-24 21:55:51，当前版本为作者最后更新于2018-07-26 12:51:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门 线段树综合。 让我想起一道叫做$siano$的题，这题就是那题的强化版本。 说说做法吧： 跟$saino$一样，当我们把$a[i]$排成有序的之后，就会保证在若干次操作后整个数列仍然是单调的。 首先加减可以看成一个操作，$L,R$的限制也只相当于一个操作，因此这道题要我们维护这几个操作： 1.区间加 2.区间乘 3.区间加变形（加上原数$a[i]$的$k$倍） 4.区间覆盖 维护：区间最大最小，单点值。 因此我们可以设计一个神奇的更新函数$f(p,k_1,k_2,k_3)$，表示整个区间的值的变化方式： $c[i]=c[i]*k_1+k_2*a[i]+k_3$，然后我们又可以惊奇的发现这个函数可以用于所有的区间修改函数。 1.区间加：$f(p,1,0,add)$。 2.区间乘：$f(p,mul,0,0)$。 3.区间加变形：$f(p,1,addx,0)$。 4.区间覆盖：$f(p,0,0,set)$。 这样的话，我们连前三个操作的单独的修改函数都不用写，简洁自然。 代码如下：

#include<bits/stdc++.h>
#define ll long long
#define N 100005
#define lc (p<<1)
#define rc (p<<1|1)
#define p1 T[p].lz1
#define p2 T[p].lz2
#define p3 T[p].lz3
#define mid (T[p].l+T[p].r>>1)
using namespace std;
struct Node{int l,r;ll mn,mx,lz1,lz2,lz3;}T[N<<2];
struct Query{int op;ll v;}q[N];
struct Ans{int id;ll v;}a[N];
int n,m;
ll ans[N],L,R;
inline ll max(ll a,ll b){return a>b?a:b;}
inline ll min(ll a,ll b){return a<b?a:b;}
inline void pushup(int p){T[p].mx=T[rc].mx,T[p].mn=T[lc].mn;}
inline void pushnow(int p,ll k1,ll k2,ll k3){
	p1*=k1,p2=p2*k1+k2,p3=p3*k1+k3;
	T[p].mx=T[p].mx*k1+k2*a[T[p].r].v+k3;
	T[p].mn=T[p].mn*k1+k2*a[T[p].l].v+k3;
}
inline void pushdown(int p){pushnow(lc,p1,p2,p3),pushnow(rc,p1,p2,p3),p1=1,p2=0,p3=0;}
inline void build(int p,int l,int r){
	T[p].l=l,T[p].r=r,p1=1,p2=p3=0,T[p].mx=a[r].v,T[p].mn=a[l].v;
	if(l==r)return;
	build(lc,l,mid),build(rc,mid+1,r);
}
inline void modify1(int p){
	if(T[p].l==T[p].r)return pushnow(p,0,0,L);
	pushdown(p);
	if(T[rc].mn<L)pushnow(lc,0,0,L),modify1(rc);
	else modify1(lc);
	pushup(p);
}
inline void modify2(int p){
	if(T[p].l==T[p].r)return pushnow(p,0,0,R);
	pushdown(p);
	if(T[lc].mx>R)pushnow(rc,0,0,R),modify2(lc);
	else modify2(rc);
	pushup(p);
}
inline bool cmp(Ans a,Ans b){return a.v<b.v;}
inline void query(int p){
	if(T[p].l==T[p].r){ans[a[T[p].l].id]=T[p].mn;return;}
	pushdown(p),query(lc),query(rc);
}
int main(){
	scanf("%d%lld%lld",&m,&L,&R);
	for(int i=1;i<=m;++i){
		char s[2];
		scanf("%s%lld",s,&q[i].v);
		switch(s[0]){
			case '+':{q[i].op=1;break;}
			case '-':{q[i].op=2;break;}
			case '*':{q[i].op=3;break;}
			default:{q[i].op=4;break;}
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i].v),a[i].id=i;
	sort(a+1,a+n+1,cmp),build(1,1,n);
	for(int i=1;i<=m;++i){
		switch(q[i].op){
			case 1:{pushnow(1,1,0,q[i].v);break;}
			case 2:{pushnow(1,1,0,-q[i].v);break;}
			case 3:{pushnow(1,q[i].v,0,0);break;}
			default:{pushnow(1,1,q[i].v,0);break;}
		}
		if(T[1].mn<L)modify1(1);
		if(T[1].mx>R)modify2(1);
	}
	query(1);
	for(int i=1;i<=n;++i)cout<<ans[i]<<'\n';
	return 0;
}