题解 P2629 【好消息，坏消息】

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 题目描述-->[p2629 好消息,坏消息](https://www.luogu.org/problemnew/show/P2629) ## 历程 刚开始看到这个题,发现是需要维护区间和,满心欢喜敲了一通线段树,简单debug之后交上去 $45pts$? 改代码的时候开始考虑这样做的正确性. 维护区间和,前后两个的区间和加起来一定等于整个区间的区间和,那我和直接求和有什么区别? ### 再次读题 发现必须要求每一个时刻老板的怒气值都$\geq 0$才行. ## ~~xjb~~分析 既然维护区间和行不通,考虑改变线段树所维护的东西. ### 考虑维护些什么? 我们需要维护一个区间的最小值,才能判断是否满足$\geq 0$ 而某一个位置的值,受前面位置的值的影响. 因此我们想到了**前缀和**. 即我们可以**维护前缀和的最小值**. ### 解决85% 既然想到了维护前缀和,那这样就很简单了. 根据题目所叙述的,我们需要从 $k,k_1,k_2 \dots n,1,2 \dots k-1$累加 所以我们要**先判断后缀的最小值是否$\leq 0$**。 显然,我们的前缀和的计算为$sum_i=\sum_{j=1}^{i}a_i$ 后缀部分$\sum_{i=k}^{n}a_i$的计算要减去$sum_{k-1}$ 又因为题目要求的计算顺序,我们需要考虑后缀和与前缀最小值的和是否$\geq 0$ 所以很容易写出这部分的代码 ```cpp for(R int i=2;i<=n;i++) { if(query(1,1,n,i,n)-sum[i-1]<0)continue; if(sum[n]-sum[i-1]+query(1,1,n,1,i-1)>=0) ans++; } ``` 看到上面的$85$%了没? 如果只单纯判断这些情况的话只能get到$85pts$ ### 考虑被遗忘的情况 检查一番,我们发现题目中这一句话 >uim必须按照时间的发生顺序逐条将消息告知给老板 #### 突然醒悟 我们还可以从$1$到$n$告诉老板! 再加上**判断是否整个区间的前缀最小值$\leq 0$**即可. 综上,我们的问题就得以解决了! ---------------------代码--------------------- ```cpp #include<bits/stdc++.h> #define R register #define N 1000008 #define ls o<<1 #define rs o<<1|1 using namespace std; int tr[N<<2],ans,n,sum[N]; inline void up(int o){tr[o]=min(tr[ls],tr[rs]);return;}; void build(int o,int l,int r) { if(l==r) { tr[o]=sum[l]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); up(o); } int query(int o,int l,int r,int x,int y) { if(x<=l and y>=r)return tr[o]; int mid=(l+r)>>1,res=2147483647; if(x<=mid)res=min(res,query(ls,l,mid,x,y)); if(y>mid)res=min(res,query(rs,mid+1,r,x,y)); return res; } int main() { scanf("%d",&n); for(R int i=1,x;i<=n;i++)scanf("%d",&x),sum[i]=sum[i-1]+x; build(1,1,n); for(R int i=2;i<=n;i++) { if(query(1,1,n,i,n)-sum[i-1]<0)continue; if(sum[n]-sum[i-1]+query(1,1,n,1,i-1)>=0) ans++; } printf("%d",ans+(tr[1]>=0)); } ```