[cf] 795 div2 D. Max GEQ Sum

前言

t a g : tag : tag: 单调栈 所有子区间 数据结构 线段树
传送门 :

题意 :
给定给一个数组 a [ ] a[] a[],询问是否满足

∀ i   m a x ( a i , a i + 1... a j − 1 , a j ) ≥ a i + a i + 1 + . . . a j − 1 + a j \forall _i\ max(a_i,a_i+1...a_{j-1},a_j) \ge a_i+a_{i+1}+...a_{j-1}+a_j ∀i​ max(ai​,ai​+1...aj−1​,aj​)≥ai​+ai+1​+...aj−1​+aj​

数据范围 :
t : 1 e 5 , n : 2 e 5 t :1e5,n:2e5 t:1e5,n:2e5

思路 :

显然的,我们并不能直接 n 2 n^2 n2的进行枚举区间

但是我们可以知道的是 m a x ( a [ l , r ] ) max(a[l,r]) max(a[l,r])

我们设 a [ x ] a[x] a[x]是上式求出来的值,那么他所能覆盖的区间必然是固定的即 L [ x ] , R [ x ] L[x],R[x] L[x],R[x]

L [ x ] L[x] L[x]表示左边大于 a [ x ] a[x] a[x]的第一个数的下标
R [ x ] R[x] R[x]表示右边大于 a [ x ] a[x] a[x]的第一个数的下标

这样子我们就可以求出来 a [ x ] a[x] a[x]所服务的区间
即 [ L [ x ] + 1 , R [ x ] − 1 ] [L[x]+1,R[x]-1] [L[x]+1,R[x]−1]

因此对于题中的式子我们就可以简化为
a [ x ] ≥ m a x ( s u m [ r ] − s u m [ l − 1 ] ) a[x]\ge max(sum[r]-sum[l-1]) a[x]≥max(sum[r]−sum[l−1])

即最大化 L [ x ] , R [ x ] L[x],R[x] L[x],R[x]里面的区间和,判断是否可行

十年 c f cf cf一场空,不开 l l ll ll见祖宗
因为对自己的线段树和单调栈不够自信, w a 2 wa2 wa2之后一直在看自己的代码到底是不是有漏洞

Q A Q QAQ QAQ完全没注意到 L L LL LL

code :

const int N = 2e5+10;
const ll INF =  1e18;

const double eps = 1e-5;

struct node{
	int l,r;
	ll minv;
	ll maxv;                  
}tr[N*4];
int n;

ll pre[N];
ll L[N],R[N];
ll a[N];

void pushup(int u){
	tr[u].maxv = max(tr[u