洛谷题解P4314 [CPU监控]

传送门

CPU监控

题目大意

一个可修改序列，两种操作： 1.区间加 2.区间覆盖 两种查询： 1.区间最大值 2.区间历史最大值

思路

显然，我们需要在线段树上维护最大值，历史最大值，加法标记，覆盖标记。

我们可以用这些来维护最大值，但这对维护历史最大值是不足够的。

反例：如果我们在相同区间上先加一个值，在减一个值，就会导致在pushdown是子区间的历史最大值就会错误。

eg. 8 1 1 10 1 1 1 1 1 3 P 1 8 100 P 1 8 -10 A 3 3

正确答案为110，但如果只维护4个值就会输出100。

在覆盖操作时，同理也会出现上述情况。

所以，我们在线段树上还需要维护历史最大加法标记和历史最大覆盖标记。

实现

我们发现主要变化的地方在pushdown函数 在pushdown中，我们需要讨论子区间是否被覆盖过冰根据其情况计算。

我们设：

最大值 mx 历史最大值 hmx 加法标记 adtag 历史最大加法标记 hadtag 覆盖标记 cvtag 历史最大覆盖标记 hcvtag

对于加法操作

d表示父节点的加法标记的值 hd表示父节点的历史最大加法标记的值

如果cover为1：说明之前被覆盖过了，此时相当于用d+cvtag进行Cover。

如果cover为0：此时只有加法，用mx+hd和adtag+hd分别更新hmx和hadtag,把mx和adtag加上d。

对于覆盖操作

如果cover为1：用hd更新hcov，取max

如果cover为0：cover改为1，hcvtag变为hd

此外还要更新历史最大值hmx，(和hd取max)

注意：

可能出现覆盖操作比加法操作更劣的情况，所以pushdown时应先下传加法标记，在下传覆盖标记。

我的代码：

#include<cstdio> #include<cmath> #include<queue> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define MAXN 100010 #define lson (id<<1) #define rson (id<<1) + 1 #define inf 2147483647 int t,e; int a[MAXN]; struct TREE{ int l[MAXN*4],r[MAXN*4]; int mx[MAXN*4],hmx[MAXN*4]; int adtag[MAXN*4],hadtag[MAXN*4]; int cvtag[MAXN*4],hcvtag[MAXN*4]; bool cover[MAXN*4]; void pushup(int id){ mx[id] = max(mx[lson],mx[rson]); hmx[id] = max(hmx[id],max(hmx[lson],hmx[rson])); } void pushadd(int id,int d,int hd){ if(cover[id]){ hcvtag[id] = max(hcvtag[id],cvtag[id] + hd); hmx[id] = max(hmx[id],cvtag[id] + hd); cvtag[id] += d;mx[id] = cvtag[id]; adtag[id] = 0; }else{ hadtag[id] = max(hadtag[id],adtag[id] + hd); hmx[id] = max(hmx[id],mx[id] + hd); adtag[id] += d; mx[id] += d; } } void pushcov(int id,int d,int hd){ if(cover[id]){ hcvtag[id] = max(hcvtag[id],hd); }else{ cover[id] = 1; hcvtag[id] = hd; } hmx[id] = max(hmx[id],hd); cvtag[id] = d;mx[id] = d; adtag[id] = 0; } void pushdown(int id){ pushadd(lson,adtag[id],hadtag[id]); pushadd(rson,adtag[id],hadtag[id]); adtag[id] = 0;hadtag[id] = 0; if(cover[id]){ pushcov(lson,cvtag[id],hcvtag[id]); pushcov(rson,cvtag[id],hcvtag[id]); cover[id] = 0;cvtag[id] = 0;hcvtag[id] = 0; } } void build(int L,int R,int id){ l[id] = L;r[id] = R; mx[id] = -inf;hmx[id] = -inf; if(L == R){ mx[id] = a[L]; hmx[id] = a[L]; return ; } int mid = (L + R)>>1; build(L,mid,lson); build(mid + 1,R,rson); pushup(id); } int ask1(int L,int R,int id){ if(l[id] >= L && r[id] <= R){ return mx[id]; } pushdown(id); int ans = -inf; int mid = (l[id] + r[id])>>1; if(L <= mid){ ans = max(ans,ask1(L,R,lson)); } if(R > mid){ ans = max(ans,ask1(L,R,rson)); } pushup(id); return ans; } int ask2(int L,int R,int id){ if(l[id] >= L && r[id] <= R){ return hmx[id]; } pushdown(id); int ans = -inf; int mid = (l[id] + r[id])>>1; if(L <= mid){ ans = max(ans,ask2(L,R,lson)); } if(R > mid){ ans = max(ans,ask2(L,R,rson)); } pushup(id); return ans; } void add(int L,int R,int id,int d){ if(l[id] >= L && r[id] <= R){ pushadd(id,d,d); return ; } pushdown(id); int mid = (l[id] + r[id])>>1; if(L <= mid){ add(L,R,lson,d); } if(R > mid){ add(L,R,rson,d); } pushup(id); } void cov(int L,int R,int id,int d){ if(l[id] >= L && r[id] <= R){ pushcov(id,d,d); return ; } pushdown(id); int mid = (l[id] + r[id])>>1; if(L <= mid){ cov(L,R,lson,d); } if(R > mid){ cov(L,R,rson,d); } pushup(id); } }tr; int main(){ scanf("%d",&t); for(int i = 1;i <= t;i++){ scanf("%d",&a[i]); } tr.build(1,t,1); scanf("%d",&e); getchar(); int x,y,z; char tpy[3]; for(int i = 1;i <= e;i++){ scanf("%s",&tpy); if(tpy[0] == 'Q'){ scanf("%d%d",&x,&y); printf("%d\n",tr.ask1(x,y,1)); }else if(tpy[0] == 'A'){ scanf("%d%d",&x,&y); printf("%d\n",tr.ask2(x,y,1)); }else if(tpy[0] == 'P'){ scanf("%d%d%d",&x,&y,&z); tr.add(x,y,1,z); }else if(tpy[0] == 'C'){ scanf("%d%d%d",&x,&y,&z); tr.cov(x,y,1,z); } getchar(); } return 0; }