20ptsTLE求助(玄关)
查看原帖
20ptsTLE求助(玄关)
1199534
ycy1124楼主2024/6/24 16:26
#include<bits/stdc++.h>
using namespace std;
struct Node{
	long long w;
}a[2000001];
long long b[500001],ans=0;
long long n,k1,k2;
void work(int p,int l,int r){
	int mid=(l+r)>>1;
	if(l==r){
		a[p].w=b[l];
		return;
	}
	work(p*2,l,mid);
	work(p*2+1,mid+1,r);
	a[p].w=a[p*2].w+a[p*2+1].w;
}
int work1(int p,int l,int r,int x,int y){
	int mid=(l+r)>>1;
	if(l>=x&&r<=y){
		return a[p].w;
	}
	if(x>mid){
		return work1(p*2+1,mid+1,r,x,y);
	}
	else if(y<=mid){
		return work1(p*2,l,mid,x,y);
	}
	else{
		return work1(p*2,l,mid,x,y)+work1(p*2+1,mid+1,r,x,y);
	}
}
void read(long long &x){
	x=0;
	int f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
int main(){
	read(n);
	read(k1);
	read(k2);
	for(int i=1;i<=n;i++){
		read(b[i]);
	}
	work(1,1,n);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			if(work1(1,1,n,i,j)>=k1&&work1(1,1,n,i,j)<=k2){
				ans++;
			}
		}
	}
	printf("%lld",ans);
	return 0;
}
2024/6/24 16:26
加载中...