链接:https://www.luogu.com.cn/problem/P4041
题目描述：给定一个数列\(a\)，与常数\(L\),\(R\),实现下列四个操作：
1.将所有数加\(d\)。
2.将所有数减\(d\)。
3.将所有数乘\(d\)。
4.将所有数加上初始值的\(d\)倍。
规定每一次操作完后，要将小于\(L\)的数置为\(L\),大于\(L\)的数置为\(R\)，求\(q\)此操作后的序列。
题解：若将\(a\)排序，我们可以发现，在操作的过程中序列始终单调不降，此时我们可以通过二分来确定要变为\(L\)的与要变为\(R\)的数的范围。这样，我们要实现的其实还有第五个操作：将\([l,r]\)置为\(x\)。
这个可以直接用线段树维护，但这样直接维护的代码量却不小。我就写了\(250\)多行代码，\(30\)分一直调不出。
此时，你要用到一个神奇的方法，将所有的修改操作看作将\(a_{i}\)置为\(A\times a_{i}+b\times x_{i}+c\)，这样就把所有的操作合并了，就只用维护一个操作了，你会发现代码量会减少很多。
但这样任然过不了\(BZOJ\)的数据，我们可以将二分的过程改为线段树二分，复杂度就优化到\(O(n log n)\)了。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node
{
long long num,data;
bool operator < (const node &a)const
{
return data<a.data;
}
};
node delta[2000001];
struct seg
{
long long l,r;
long long mindata,maxdata,lazyA,lazyB,lazyC;
};
long long L,R,n,Ans[2000001];
seg tree[2000001];
inline void spread(register int k)
{
tree[k*2].lazyA*=tree[k].lazyA;
tree[k*2].lazyB=tree[k*2].lazyB*tree[k].lazyA+tree[k].lazyB;
tree[k*2].lazyC=tree[k*2].lazyC*tree[k].lazyA+tree[k].lazyC;
tree[k*2].mindata=tree[k*2].mindata*tree[k].lazyA+delta[tree[k*2].l].data*tree[k].lazyB+tree[k].lazyC;
tree[k*2].maxdata=tree[k*2].maxdata*tree[k].lazyA+delta[tree[k*2].r].data*tree[k].lazyB+tree[k].lazyC;
tree[k*2+1].lazyA*=tree[k].lazyA;
tree[k*2+1].lazyB=tree[k*2+1].lazyB*tree[k].lazyA+tree[k].lazyB;
tree[k*2+1].lazyC=tree[k*2+1].lazyC*tree[k].lazyA+tree[k].lazyC;
tree[k*2+1].mindata=tree[k*2+1].mindata*tree[k].lazyA+delta[tree[k*2+1].l].data*tree[k].lazyB+tree[k].lazyC;
tree[k*2+1].maxdata=tree[k*2+1].maxdata*tree[k].lazyA+delta[tree[k*2+1].r].data*tree[k].lazyB+tree[k].lazyC;
tree[k].lazyA=1;
tree[k].lazyB=tree[k].lazyC=0;
return;
}
inline void build(register int k,register int l,register int r)
{
tree[k].l=l;
tree[k].r=r;
tree[k].lazyA=1;
int mid=(l+r)/2;
if (l==r)
{
tree[k].mindata=tree[k].maxdata=delta[l].data;
return;
}
build(k*2,l,mid);
build(k*2+1,mid+1,r);
tree[k].mindata=tree[k*2].mindata;
tree[k].maxdata=tree[k*2+1].maxdata;
return;
}
inline void add(register int k,register int l,register int r,register long long a,register long long b,register long long c)
{
if (tree[k].l==l&&tree[k].r==r)
{
tree[k].lazyA*=a;
tree[k].lazyB=tree[k].lazyB*a+b;
tree[k].lazyC=tree[k].lazyC*a+c;
tree[k].mindata=tree[k].mindata*a+delta[tree[k].l].data*b+c;
tree[k].maxdata=tree[k].maxdata*a+delta[tree[k].r].data*b+c;
return;
}
spread(k);
int mid=(tree[k].l+tree[k].r)/2;
if (l<=mid&&r<=mid)
{
add(k*2,l,r,a,b,c);
tree[k].mindata=tree[k*2].mindata;
tree[k].maxdata=tree[k*2+1].maxdata;
return;
}
if (l>=mid+1&&r>=mid+1)
{
add(k*2+1,l,r,a,b,c);
tree[k].mindata=tree[k*2].mindata;
tree[k].maxdata=tree[k*2+1].maxdata;
return;
}
add(k*2,l,mid,a,b,c);
add(k*2+1,mid+1,r,a,b,c);
tree[k].mindata=tree[k*2].mindata;
tree[k].maxdata=tree[k*2+1].maxdata;
return;
}
inline long long query(register int k,register int x)
{
if (tree[k].l==tree[k].r)
return tree[k].mindata;
spread(k);
int mid=(tree[k].l+tree[k].r)/2;
if (x<=mid)
return query(k*2,x);
else
return query(k*2+1,x);
}
char ot1[1000001];
long long ot2[1000001];
inline int read()
{
register char c=0;
register int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
inline void write(register int x)
{
if (x==0)
return;
write(x/10);
putchar(x%10+'0');
return;
}
inline int min_segment_search(register int k,register int l,register int r,register int d)
{
if (tree[k].l==tree[k].r)
{
if (tree[k].mindata<=d)
return n+1;
return tree[k].l;
}
spread(k);
int mid=(tree[k].l+tree[k].r)/2;
if (tree[k*2+1].mindata>d&&l<=mid)
return min(min_segment_search(k*2,l,mid,d),mid+1);
else
return min_segment_search(k*2+1,mid+1,r,d);
}
inline int max_segment_search(register int k,register int l,register int r,register int d)
{
if (tree[k].l==tree[k].r)
{
if (tree[k].maxdata>=d)
return 0;
return tree[k].l;
}
spread(k);
int mid=(tree[k].l+tree[k].r)/2;
if (tree[k*2].maxdata<d&&mid+1<=r)
return max(max_segment_search(k*2+1,mid+1,r,d),mid);
else
return max_segment_search(k*2,l,mid,d);
}
signed main()
{
register int q,first,last,mid,ans;
q=read();
L=read();
R=read();
for (register int i=1;i<=q;++i)
{
while (ot1[i]!='+'&&ot1[i]!='-'&&ot1[i]!='*'&&ot1[i]!='@')
ot1[i]=getchar();
ot2[i]=read();
}
n=read();
for (register int i=1;i<=n;++i)
{
delta[i].data=read();
delta[i].num=i;
}
sort(delta+1,delta+n+1);
build(1,1,n);
for (register int i=1;i<=q;++i)
{
if (ot1[i]=='+')
add(1,1,n,1,0,ot2[i]);
if (ot1[i]=='-')
add(1,1,n,1,0,-ot2[i]);
if (ot1[i]=='*')
add(1,1,n,ot2[i],0,0);
if (ot1[i]=='@')
add(1,1,n,1,ot2[i],0);
ans=min_segment_search(1,1,n,R);
if (ans!=n+1)
add(1,ans,n,0,0,R);
ans=max_segment_search(1,1,n,L);
if (ans!=0)
add(1,1,ans,0,0,L);
}
for (register int i=1;i<=n;++i)
Ans[delta[i].num]=query(1,i);
for (register int i=1;i<=n;++i)
{
write(Ans[i]);
puts("");
}
return 0;
}