[AHOI2014/JSOI2014]奇怪的计算器

链接: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 #include #include 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="" l,r;="" mindata,maxdata,lazya,lazyb,lazyc;="" l,r,n,ans[2000001];="" 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;="" build(register="" k,register="" l,register="" r)="" tree[k].l="l;" tree[k].r="r;" mid="(l+r)/2;" if="" (l="=r)" tree[k].mindata="tree[k].maxdata=delta[l].data;" build(k*2,l,mid);="" build(k*2+1,mid+1,r);="" tree[k].maxdata="tree[k*2+1].maxdata;" add(register="" r,register="" a,register="" b,register="" c)="" (tree[k].l="=l&&tree[k].r==r)" tree[k].lazya*="a;" tree[k].lazyc="tree[k].lazyC*a+c;" spread(k);="" (l<="mid&&r<=mid)" add(k*2,l,r,a,b,c);="">=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