传送门
真tm好题。
区间加减，区间乘，区间假加，区间覆盖。
每个线段树结点对应我们需要求的一个初始代入值下标。
为了简单我们把询问的东西sort。
维护一个函数：（k1,k2,k3）=k1*c1+k2*a+k3;这样就可以应对四个操作。
如此，直接怼。可以说是下传标记好题。
#include<bits/stdc++.h>usingnamespacestd;#defineinread()#defineintlonglongintin{intcnt=0,f=1;charch=0;while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}while(isdigit(ch)){cnt=cnt*10+ch-48;ch=getchar();}returncnt*f;}structnode{intmaxx,minn,l,r,k1,k2,k3;}t[400003];intn,L,R;intans[100003];structbili{intop;intkey;}que[100003];structgu{intid;intkey;}a[100003];boolcm(gua,gub){returna.key<b.key;}voidpushup(intu){t[u].maxx=t[u*2+1].maxx;t[u].minn=t[u*2].minn;}voidbuild(intu,intl,intr){t[u].l=l;t[u].r=r;t[u].maxx=a[r].key;t[u].minn=a[l].key;t[u].k1=1;if(l==r)return;intmid=(l+r)>>1;build(u*2,l,mid);build(u*2+1,mid+1,r);pushup(u);}voidmodify(intu,intk1,intk2,intk3){t[u].k1*=k1;t[u].k2=t[u].k2*k1+k2;t[u].k3=t[u].k3*k1+k3;t[u].maxx=t[u].maxx*k1+a[t[u].r].key*k2+k3;t[u].minn=t[u].minn*k1+a[t[u].l].key*k2+k3;}voidpushdown(intu){modify(u*2,t[u].k1,t[u].k2,t[u].k3);modify(u*2+1,t[u].k1,t[u].k2,t[u].k3);t[u].k1=1;t[u].k2=t[u].k3=0;}voidquery(intu){if(t[u].l==t[u].r){ans[a[t[u].l].id]=t[u].minn;return;}pushdown(u);query(u*2);query(u*2+1);}voidmo1(intu){if(t[u].l==t[u].r){modify(u,0,0,L);return;}pushdown(u);if(t[u*2+1].minn<L)modify(u*2,0,0,L),mo1(u*2+1);elsemo1(u*2);pushup(u);}voidmo2(intu){if(t[u].l==t[u].r){modify(u,0,0,R);return;}pushdown(u);if(t[u*2].maxx>R)modify(u*2+1,0,0,R),mo2(u*2);elsemo2(u*2+1);pushup(u);}signedmain(){n=in;L=in;R=in;charch[3];for(inti=1;i<=n;i++){scanf("%s",ch+1);switch(ch[1]){case'+':{que[i].op=1;break;}case'-':{que[i].op=2;break;}case'*':{que[i].op=3;break;}case'@':{que[i].op=4;break;}}que[i].key=in;}intq=in;for(inti=1;i<=q;i++)a[i].id=i,a[i].key=in;sort(a+1,a+q+1,cm);build(1,1,q);for(inti=1;i<=n;i++){switch(que[i].op){case1:{modify(1,1,0,que[i].key);break;}case2:{modify(1,1,0,-que[i].key);break;}case3:{modify(1,que[i].key,0,0);break;}case4:{modify(1,1,que[i].key,0);break;}}if(t[1].minn<L)mo1(1);if(t[1].maxx>R)mo2(1);}query(1);for(inti=1;i<=q;i++){cout<<ans[i]<<'\n';}return0;}
