血压(st表)

血压

Time Limit: 2000 MS Memory Limit: 32768 K Total Submit: 104(17 users) Total Accepted: 20(13 users) Rating:  Special Judge: No

Description

众所周知，zrr的心理素质十分良好，面对众多离谱的事情他都能保持心态。 但是突然出现了n个新生让zrr措手不及，这里用a[i]表示每个新生提问的离谱程度，表示第i个新生去向zrr提问时，zrr怒气值的改变量。 当然很多新生也十分优秀，提出的问题很有讨论意义，所以a[i]也可能是负数。 现在一共有m天，每天开始时zrr的怒气值会变为0，每天都会有一段[l,r]区间的新生从左到右依次向zrr提问。 每天zrr有一个怒气上限k，这天的任何时候一但zrr的怒气值大于或者等于k，那么zrr就会破防。 每一天请求出我们亲爱的zrr学姐有没有破防。

Input

第一行一个数T表示数据组数(1<=T<=3) 对于每组数据 第一行一个数n，表示学生数(1<=n<=100000) 第二行n个数a[1],a[2]...a[n]，表示每个学生的离谱程度(-100<=a[i]<=100) 第三行一个数m，表示天数(1<=m<=100000) 接下来m行每行三个整数，l,r,k意义如题所述(1<=l<=r<=n  -1e9<=k<=1e9)

Output

每组数据输出m行，如果zrr当天破防了请输出“Yes”，否则输出“No”

Sample Input

1 3 1 -2 3 3 1 1 1 1 2 1 1 3 3

Sample Output

Yes Yes No

Source

20211114

 ST表应用,但是注意前缀和要减去之前的,负数特判

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int N=100010,M=35;
int q,k,n,m,t,l,r,a[N],s[N],f[N][M],g[N][M],lg[N];
void prework(){
    t=lg[n];
    for(int i=1;i<=n;i++){
        f[i][0]=s[i];
        g[i][0]=s[i];
    }
    for(int j=1;j<=t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
int getmax(int l,int r){
    int z=lg[r-l+1];
    return max(f[l][z],f[r-(1<<z)+1][z]);
}
int main() {
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &n);
        for (int i = 2; i <= n; i++)lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            s[i]=s[i-1]+a[i];
        }
        prework();
        scanf("%d",&m);
        while (m--) {
            scanf("%d%d%d", &l, &r,&k);
            if(k<=0){
                printf("Yes\n");
            }
            else if((getmax(l,r)-s[l-1])<k){
                printf("No\n");
            }
            else{
                printf("Yes\n");
            }
        }
    }
}