题解 P4314 【CPU监控】

Update: 2020-1-8 修复了 ```do_val``` 函数的 bug，感谢 @z7z_Eta 提供的 hack 数据 ； 修改了部分文章内容 --- [题目传送门](https://www.luogu.org/problemnew/show/P4314) 首行求赞，反正不 FA 钱 qwq ## 0.前置 - 线段树（并能较好地理解） - 一颗能听我把废话说完的心 ## 1.题意简述 给出 $T$ 个数，$E$ 个操作（$T,E \leq 10^5$）: - Q X Y：询问从 $X$ 到 $Y$ 的**当前**最大值 - A X Y：询问从 $X$ 到 $Y$ 的**历史**最大值（出现过的最大数） - P X Y Z：将 $X$ 到 $Y$ 这段区间加 $Z$ - C X Y Z：将 $X$ 到 $Y$ 这段区间赋值为 $Z$ ## 2.线段树 看到这道题，首先不难想到的就是线段树 如果没有查询历史最大值，这道题（对于您来说）肯定没有难度 加上历史最大值，事情就复杂了。。。 这也是这道题困难的地方，即对于 ```lazy tag``` 的理解 --- $\tiny \text{（以上都是废话）}$ --- ## 3.lazy tag 的使用 其实这道题完全可以作为线段树的模板题，考察了 ```lazy tag``` 与树上节点的更新顺序的关系 ### 如何理解？ ```lazy tag``` 实际上可以看作是对于该节点表示的区间的**操作序列**，这也是线段树的精髓所在 ```push_down``` 操作就是把父节点的操作序列接在儿子节点的序列**之后** （_思考：为什么一定是 “ **之后** ” ？_） 对一个点进行 ```push_down``` 操作后，该点的操作序列即被清空，因为在递归完子树后，该点答案将被更新。以下文章中的 “ 操作序列 ”，都指的是该点上一次进行 ```push_down``` 后（即上一次清空后）的操作序列 ### 如何处理操作序列？ 首先，相邻的同种操作可被合并 于是，对于一个点，操作序列分为以下几种（ "+" 号表示操作的先后顺序，汉字叙述可能影响您的阅读体验）： 1. $\text{加操作}$ 2. $\text{加操作} + \text{赋值操作}$ 3. $\text{加操作} + \text{赋值操作} + \text{加操作}$ 4. $\text{加操作} + \text{赋值操作} + \text{加操作} + \text{赋值操作}$ 5. $\cdots$ 这个操作序列显然很难保存在每一个点上 我们发现，对于一个点，首次赋值操作之后的任何修改都可以看作赋值操作（_想一想，为什么_） 于是操作序列化简为（**重点**）： $$\text{加操作 + 赋值操作}$$ 现在，恭喜您解决了两个个很大的问题：操作序列如何保存 & 同一点上操作的先后顺序问题 于是，只用保存加和赋值两种 ```lazy tag```，便可记录该节点的操作序列 --- **如果您理解了以上内容，那么您就已经掌握了本题算法的核心。如果您还没有，也可以先看代码，再回顾以上内容** --- 其它细节详见代码 ## 4.code ```cpp #include<cstdio> const int MAXN = 1e5 + 5; const int inf = 0x7fffffff; inline int max(int a,int b){ return a>b? a: b;} inline void chk_max(int &a,int b){ if(a<b) a=b;} int ans[MAXN<<2],max_ans[MAXN<<2];//区间最大值 区间历史最大值 bool vis[MAXN<<2];//是否进行过区间赋值操作 int sum[MAXN<<2], val[MAXN<<2];//上次下放之后的加和 上次下放之后的赋值操作 （赋值之后的加操作一并算入赋值，下同） int max_sum[MAXN<<2], max_val[MAXN<<2];//上次下放之后达到的最大加和 上次下放之后赋的最大值 /* 注意这里实际上使用了4个lazy_tag，不过如果您理解了算法的核心，您应该知道我在干什么 */ #define ls(u) ((u)<<1) #define rs(u) ((u)<<1|1)//个人习惯，左右儿子 inline void push_up(int u)//push_up比较简单，就是用左右儿子的答案更新本节点的答案 { ans[u] = max(ans[ls(u)], ans[rs(u)]); max_ans[u] = max(max_ans[ls(u)], max_ans[rs(u)]); } //我将更新lazy_tag的操作打包成函数，不然有可能在细节上出错（其实我一开始就是在这里出的错） /* 更新加操作的tag，分为两种情况： 1.赋过值，算作赋值操作 2.没赋过值 */ inline void do_sum(int u,int k,int max_k)//max_k表示父节点在上一次push_down之后达到的最大加和 { if(vis[u]) { chk_max(max_val[u], val[u]+max_k); chk_max(max_ans[u], ans[u]+max_k); ans[u]+=k; val[u]+=k; } else { chk_max(max_sum[u], sum[u]+max_k); chk_max(max_ans[u], ans[u]+max_k); ans[u]+=k; sum[u]+=k; } } inline void do_val(int u,int k,int max_k)//max_k表示父节点在上一次push_down之后达到的最大赋值 { if(vis[u]) { chk_max(max_val[u], max_k); chk_max(max_ans[u], max_k); } else { vis[u]=1;//该点标记为赋过值 max_val[u] = max_k; chk_max(max_ans[u], max_k); } ans[u] = val[u] = k; } inline void push_down(int u) { do_sum(ls(u),sum[u],max_sum[u]); do_sum(rs(u),sum[u],max_sum[u]);//先传递和 sum[u] = max_sum[u] = 0;//下传之后清零 if(vis[u]) { do_val(ls(u),val[u],max_val[u]); do_val(rs(u),val[u],max_val[u]); vis[u] = 0; val[u] = max_val[u] = 0;//下传之后清零 } } void build(int u,int l,int r)//建树 { if(l==r) { scanf("%d",&ans[u]); max_ans[u]=ans[u]; return; } int mid=(l+r)>>1; build(ls(u),l,mid); build(rs(u),mid+1,r); push_up(u); } int query(int u,int l,int r, int ql,int qr)//Q操作 { if(ql<=l && r<=qr) return ans[u]; push_down(u); int mid=(l+r)>>1, ret=-inf; if(ql<=mid) ret = query(ls(u),l,mid, ql,qr); if(mid<qr) chk_max(ret, query(rs(u),mid+1,r, ql,qr)); return ret; } int query_max(int u,int l,int r, int ql,int qr)//A操作，与Q类似 { if(ql<=l && r<=qr) return max_ans[u]; push_down(u); int mid=(l+r)>>1, ret=-inf; if(ql<=mid) ret = query_max(ls(u),l,mid, ql,qr); if(mid<qr) chk_max(ret, query_max(rs(u),mid+1,r, ql,qr)); return ret; } void add(int u,int l,int r, int ql,int qr,int k)//P操作 { if(ql<=l && r<=qr) { do_sum(u,k,k);//这里max_k也填k就行了 return; } push_down(u); int mid = (l+r)>>1; if(ql<=mid) add(ls(u),l,mid, ql,qr,k); if(mid<qr) add(rs(u),mid+1,r, ql,qr,k); push_up(u); } void assign(int u,int l,int r, int ql,int qr,int k)//C操作 { if(ql<=l && r<=qr) { do_val(u,k,k); return; } push_down(u); int mid = (l+r)>>1; if(ql<=mid) assign(ls(u),l,mid, ql,qr,k); if(mid<qr) assign(rs(u),mid+1,r, ql,qr,k); push_up(u); } //这两个函数是调试用的，用于打印序列 void print(int u,int l,int r) { if(l==r) { printf("%d ",ans[u]); return; } push_down(u); int mid=(l+r)>>1; print(ls(u),l,mid); print(rs(u),mid+1,r); } inline void test(int t) { printf("=========================================\n"); print(1,1,t); printf("\n=========================================\n"); } int main(void) { int t; scanf("%d",&t); build(1,1,t); int e; scanf("%d",&e); while(e--) { char c=getchar(); while(c!='Q' && c!='A' && c!='P' && c!='C') c=getchar();//个人习惯，感觉这么写比较保险 int x,y; scanf("%d%d",&x,&y); if(c=='Q') printf("%d\n",query(1,1,t, x,y)); if(c=='A') printf("%d\n",query_max(1,1,t, x,y)); if(c=='P') { int z; scanf("%d",&z); add(1,1,t, x,y,z); //test(t); } if(c=='C') { int z; scanf("%d",&z); assign(1,1,t, x,y,z); //test(t); } } return 0; } ``` 本题解主要用于理清自己思路，如果有与他人方法重复也不要喷qaq 实际还写了蛮长时间的。。。码字手酸，见谅qwq 如果您觉得题解有错误，可以私信或者评论 当然别忘了点赞qwq