做名片的网站叫什么来着,小项目加盟,四川省建设厅,视频网站不赚钱为什么还做这个是去年遗留历史问题#xff0c;之前思路混乱#xff0c;搞了好多发都是WA#xff0c;就没做了 自从上次做了大白书上那个双重懒惰标记的题目#xff0c;做这个就思路很清晰了 跟上次大白上那个差不多#xff0c;这个也是有一个sets标记#xff0c;代表这个区间全部置… 这个是去年遗留历史问题之前思路混乱搞了好多发都是WA就没做了 自从上次做了大白书上那个双重懒惰标记的题目做这个就思路很清晰了 跟上次大白上那个差不多这个也是有一个sets标记代表这个区间全部置为0或者1没有置位的时候为-1 还有个rev标记代表翻转操作0代表当前不翻1代表当前翻 要注意一下优先级发现有不同的弄法我是这个弄得有set操作的时候set标记设值并把当前节点的rev标记设为0因为不管要不要rev当前set操作肯定直接覆盖了 rev操作不改变set操作在pushdown的时候先考虑set标记再弄rev标记这也是很好理解的因为一旦rev和set共存肯定是rev在set后面。 有几个细节要注意一下一开始行云流水一气呵成发现还是WA了就是这几个地方 1.除了set的时候强制给rev弄成0其他任何时候对rev标记操作都是^1,取反这个也很好理解之前在pushdown里面我就是直接传值肯定不对嘛 2.在pushdown里面的set下传操作也要记得把子树的rev标记抹除一开始只在主修改函数里写了这里没写WA的不明不白理由跟上面的一样 然后就基本上没问题了 #include iostream
#include cstdio
#include cstring
#define lson rt1,l,mid
#define rson rt1|1,mid1,r
using namespace std;
const int N10000010;
int d[N*3],maxc[N*3],lc[N*3],rc[N*3],maxc0[N*3],lc0[N*3],rc0[N*3];
int sets[N*3],rev[N*3];
int n,Q;
int A[N];
void up(int rt,int l,int r)
{int mid(lr)1;d[rt]d[rt1]d[rt1|1];maxc[rt]max(maxc[rt1],maxc[rt1|1]);maxc[rt]max(maxc[rt],lc[rt1|1]rc[rt1]);lc[rt]lc[rt1];rc[rt]rc[rt1|1];if (lc[rt1]mid-l1) lc[rt]lc[rt1|1];if (rc[rt1|1]r-mid) rc[rt]rc[rt1];maxc0[rt]max(maxc0[rt1],maxc0[rt1|1]);maxc0[rt]max(maxc0[rt],lc0[rt1|1]rc0[rt1]);lc0[rt]lc0[rt1];rc0[rt]rc0[rt1|1];if (lc0[rt1]mid-l1) lc0[rt]lc0[rt1|1];if (rc0[rt1|1]r-mid) rc0[rt]rc0[rt1];
}
void build(int rt,int l,int r)
{sets[rt]-1;rev[rt]0;if (lr){d[rt]maxc[rt]A[l];lc[rt]rc[rt]A[l];lc0[rt]rc0[rt]maxc0[rt]1-A[l];return;}int mid(lr)1;build(lson);build(rson);up(rt,l,r);
}
void pushdown(int rt,int l,int r)
{if (lr) return;int mid(lr)1;if (sets[rt]0){maxc[rt1]lc[rt1]rc[rt1]d[rt1](mid-l1)*sets[rt];maxc[rt1|1]lc[rt1|1]rc[rt1|1]d[rt1|1](r-mid)*sets[rt];maxc0[rt1]lc0[rt1]rc0[rt1](mid-l1)*(1-sets[rt]);maxc0[rt1|1]lc0[rt1|1]rc0[rt1|1](r-mid)*(1-sets[rt]);sets[rt1]sets[rt1|1]sets[rt];rev[rt1]rev[rt1|1]0;sets[rt]-1;}if (rev[rt]0){d[rt1](mid-l1)-d[rt1];d[rt1|1](r-mid)-d[rt1|1];int t1,t2,t3;t1maxc[rt1];t2lc[rt1];t3rc[rt1];maxc[rt1]maxc0[rt1];lc[rt1]lc0[rt1];rc[rt1]rc0[rt1];maxc0[rt1]t1;lc0[rt1]t2;rc0[rt1]t3;t1maxc[rt1|1];t2lc[rt1|1];t3rc[rt1|1];maxc[rt1|1]maxc0[rt1|1];lc[rt1|1]lc0[rt1|1];rc[rt1|1]rc0[rt1|1];maxc0[rt1|1]t1;lc0[rt1|1]t2;rc0[rt1|1]t3;rev[rt1]^1;rev[rt1|1]^1;rev[rt]0;}
}
void change(int val,int L,int R,int rt,int l,int r)
{if (Ll rR){d[rt](r-l1)*val;lc[rt]rc[rt](r-l1)*val;maxc[rt](r-l1)*val;lc0[rt]rc0[rt]maxc0[rt](r-l1)*(1-val);sets[rt]val;rev[rt]0;return;}pushdown(rt,l,r);int mid(lr)1;if (Lmid) change(val,L,R,rson);elseif (Rmid) change(val,L,R,lson);else{change(val,L,R,rson);change(val,L,R,lson);}up(rt,l,r);
}
void revers(int L,int R,int rt,int l,int r)
{if (Ll rR){d[rt](r-l1)-d[rt];int t1,t2,t3;t1maxc[rt];t2lc[rt];t3rc[rt];maxc[rt]maxc0[rt];lc[rt]lc0[rt];rc[rt]rc0[rt];maxc0[rt]t1;lc0[rt]t2;rc0[rt]t3;rev[rt]^1;return;}pushdown(rt,l,r);int mid(lr)1;if (Rmid) revers(L,R,lson);elseif (Lmid) revers(L,R,rson);else{revers(L,R,lson);revers(L,R,rson);}up(rt,l,r);
}
int output(int op,int L,int R,int rt,int l,int r)
{if (Ll rR){if (op3) return d[rt];else return maxc[rt];}pushdown(rt,l,r);int mid(lr)1;if (Lmid) return output(op,L,R,rson);elseif (Rmid) return output(op,L,R,lson);else{int ret1output(op,L,mid,lson);int ret2output(op,mid1,R,rson);if (op3) return ret1ret2;else{int retmax(ret1,ret2);int t1min(rc[rt1],mid-L1);int t2min(lc[rt1|1],R-mid);retmax(ret,t1t2);return ret;}}
}
int main()
{int t,op,a,b;scanf(%d,t);while (t--){scanf(%d%d,n,Q);for (int i1;in;i) scanf(%d,A[i]);build(1,1,n);while (Q--){scanf(%d%d%d,op,a,b);a;b;if (op1){change(op,a,b,1,1,n);}elseif (op2){revers(a,b,1,1,n);}else{int ansoutput(op,a,b,1,1,n);printf(%d\n,ans);}}}return 0;
}转载于:https://www.cnblogs.com/kkrisen/p/3864311.html
