记录编号	549378	评测结果	AAAAAAA
题目名称	有限制区间元素询问I	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	2.863 s
提交时间	2020-02-10 16:34:20	内存使用	18.24 MiB

/*
5 1
1 3 2 4 5
1 4 2 5
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define int long long int
using namespace std;
int a[200001],b[200001],c[200001];
int n,m,l,r,up,down,block;
bool Function(int x,int y)
{
	return x<y;
}
signed main()
{
	freopen("LBEQ-I.in","r",stdin);
	freopen("LBEQ-I.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	block=sqrt(n);
	int nblock=n/block;
	for(int i=1;i<=nblock;i++)
	{
		sort(b+(i-1)*block+1,b+i*block+1,Function);
	}
	if(block*nblock<n)
	{
		sort(b+(block*nblock)+1,b+1+n,Function);
	}
	for(int i=1;i<=nblock;i++)
	{
		c[(i-1)*block+1]=b[(i-1)*block+1];
		for(int j=2;j<=block;j++)
		{
			c[(i-1)*block+j]=c[(i-1)*block+j-1]+b[(i-1)*block+j];
		}
	}
	if(block*nblock<n)
	{
		c[block*nblock+1]=b[block*nblock+1];
		for(int j=block*nblock+2;j<=n;j++)
		{
			c[j]=c[j-1]+b[j];
		} 
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld%lld",&l,&r,&down,&up);
		int ans=0;
		if((r-l+1)<=2*block)
		{
			for(int j=l;j<=r;j++)
			{
				if(a[j]<=up&&a[j]>=down)
					ans+=a[j];
			}
			cout<<ans<<endl;
			continue;
		}
		if((l-1)%block!=0)
		{
			int MD=(l/block+1)*block;
			for(int j=l;j<=MD;j++)
			{
				if(a[j]<=up&&a[j]>=down)
					ans+=a[j];
			}
			l=(l/block+1)*block+1;//把l换到整块的起点 
		}
		if(r%block!=0)
		{
			int MD=(r/block)*block+1;
			for(int j=MD;j<=r;j++)
			{
				if(a[j]<=up&&a[j]>=down)
					ans+=a[j];
			}
			r=(r/block)*block;//现在l和r都是块的端点 
		} 
		int K1=(l-1)/block+1;//l所在块的ID;
		int K2=r/block;//r所在块的ID;
		for(int j=K1;j<=K2;j++)
		{
			int A1=lower_bound(b+(j-1)*block+1,b+j*block+1,down)-b;
			int A2=upper_bound(b+(j-1)*block+1,b+j*block+1,up)-b;
			bool F1=0,F2=0;
			if(A2>j*block)
			{
				A2=j*block;
				F2=1;
			}
			if(A1>j*block)
			{
				F1=1;
			}
			if(A2==(j-1)*block+1)
				continue;
			if(F1)
				continue;
			if(A1==(j-1)*block+1)
			{
				A1=1;
			}
			ans+=c[A2-1+F2]-c[A1-1];//c[0]肯定为0，如果整个块都比down要大就不减去了 
		} 
		printf("%lld\n",ans);
	}
	return 0;
}