CF EDU-162 (已更新：C)
CF-EDU-162(已更新：C)
结果上看还不坏，但赛时写题过程十分若只(⊙﹏⊙)
C
赛时想到了求区间和的思路，可能是比赛前还在补线段树的题——我居然在半个小时里把线段树和树状数组都写了一次
（而且交上去wa了），然后才想到用前缀和做……
分析
题意得要想明白，特别要结合样例来看，是说对于数组a从a[l]到a[r]，如果存在数组b满足区间[l,r]内：
- 和相同
- a[i]!=b[i]
- b[i]>0
由1，2可知，，，直接说结论：要保证a[i]!=b[i]且和相同，意味着我们只能转移a[i]的权值来使a[i]相对原来的值发生变化
只要权值发生变化就可以了
那具体每个a[i]是怎样变化？自然是可以加可以减，但是第3个条件使得对于权值为1的a[i]，它们的值只能增加，这个增加量我们称为"必要增加量",且它只能来自其它权值不为1的a[i]的减少量,我们称为"最大减少量",因此,只要使得区间内最大减少量——(最大为)所有(a[i]-1)之和能大于等于必要增加量——(最小为)1的个数就可以了
操作
我的做法是赋值再求和,如果a[i]为1,将其赋值为-1,否则,a[i]-=1,这样一来,原本as数组中的1权值变成了-1——变成了它对区间内必要增加量的贡献,其它树的权值减去了1——变成了它对区间内最大减少量的贡献.
这样新数组的区间和只要>=0即满足条件.
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
#define lc p<<1
#define rc p<<1|1
const int N=3e5+5;
int a[N],p[N];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t,x,y,q,n,cnt=0,ans=0;cin>>t;
while(t--){
cin>>n>>q;
mem(p);
rep(i,1,n){
cin>>x;
//赋值再求和
if(x==1) x-=2;
else x--;
p[i]=p[i-1]+x;
}
while(q--){
cin>>x>>y;
if(x==y){
cout<<"NO"<<endl;
continue;
}
if(p[y]-p[x-1]>=0) cout<<"YES";
else cout<<"NO";
cout<<endl;
}
}
return 0;
}