记录编号	549293	评测结果	EEEEEEE
题目名称	3347.有限制区间元素询问I	最终得分	0
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	未通过
代码语言	C++	运行时间	7.905 s
提交时间	2020-02-09 18:00:30	内存使用	1190.11 MiB

#include<iostream>
#include<cstdio>
#include<algorithm> 
using namespace std;
int V[200001],a[200001];
int sum[102400001],root[800001],ch[102400001][2];
int n,tn,m,tot,a1,a2,a3,a4,mi,mx;
bool Function(int x,int y)
{
	return x<y;
}
void LSH()
{
	sort(a+1,a+1+tn,Function);
	n=unique(a+1,a+1+tn)-a-1;
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		sum[x]=0;
		return ;
	}
	ch[x][0]=++tot;
	ch[x][1]=++tot;
	//if(tot%1000==0)
		//cout<<tot/1000<<' ';
	int mid=(l+r)>>1;
	build(ch[x][0],l,mid);
	build(ch[x][1],mid+1,r);
}
void Fir_build(int x,int l,int r)
{
	root[x]=++tot;
	//if(tot%1000==0)
		//cout<<tot/1000<<' ';
	build(root[x],1,n);
	if(l==r)
		return;
	int mid=(l+r)>>1;
	Fir_build(x<<1,l,mid);
	Fir_build(x<<1|1,mid+1,r);
}
void pushup(int x)
{
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]; 
}
void ADD(int x,int l,int r,int K,int V)
{
	if(l==r)
	{
		sum[x]+=V;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=K)
		ADD(ch[x][0],l,mid,K,V);
	else
		ADD(ch[x][1],mid+1,r,K,V);
	pushup(x);
}
void Fir_ADD(int x,int l,int r,int ID,int K,int V)
{
	ADD(root[x],1,n,K,V);
	if(l==r)
		return;
	int mid=(l+r)>>1;
	if(ID<=mid)
		Fir_ADD(x<<1,l,mid,ID,K,V);
	else
		Fir_ADD(x<<1|1,mid+1,r,ID,K,V); 
}
int Query(int x,int l,int r,int nl,int nr)
{
	if(nl<=l&&nr>=r)
		return sum[x];
	int mid=(l+r)>>1,res=0;
	if(nl<=mid)
	{
		res+=Query(ch[x][0],l,mid,nl,nr);
	}
	if(nr>mid)
		res+=Query(ch[x][1],mid+1,r,nl,nr);
	return res;
}
int Fir_Query(int x,int l,int r,int nl,int nr,int Vl,int Vr)
{
	if(nl<=l&&nr>=r)
	{
		return Query(root[x],1,n,Vl,Vr);
	}
	int mid=(l+r)>>1,res=0;
	if(nl<=mid)
		res+=Fir_Query(x<<1,l,mid,nl,nr,Vl,Vr);
	if(nr>mid)
		res+=Fir_Query(x<<1|1,mid+1,r,nl,nr,Vl,Vr);
	return res;	
}
int main()
{
	freopen("LBEQ-I.in","r",stdin);
	freopen("LBEQ-I.out","w",stdout);
	scanf("%d%d",&tn,&m);
	mi=998244353;
	for(int i=1;i<=tn;i++)
	{
		scanf("%d",&a[i]);
		V[i]=a[i];
		mi=min(mi,a[i]);
		mx=max(mx,a[i]);
	}
	LSH();
	Fir_build(1,1,tn);
	for(int i=1;i<=tn;i++)
	{
		int K1=lower_bound(a+1,a+n+1,V[i])-a;
		Fir_ADD(1,1,tn,i,K1,V[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&a1,&a2,&a3,&a4);
		int K1=lower_bound(a+1,a+1+n,a3)-a;
		int K2=upper_bound(a+1,a+1+n,a4)-a;
		K2--;
		if(a3>mx||a4<mi)
		{
			cout<<0<<endl;
			continue;
		}
		cout<<Fir_Query(1,1,tn,a1,a2,K1,K2)<<endl;
	}
	return 0;
}