血压(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
#include
#include
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<> 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])
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！