TLE on 1,2,3,4

做法是莫队+树状数组。

感激不尽。

#include<bits/stdc++.h>
//#define int long long
using namespace std;

namespace io
{
	inline int read(){int x=0,w=0;char c=0;while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;}
	template<typename T>inline void write(T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
	template<typename T>inline void write_(T x){write(x),putchar(' ');}
	template<typename T>inline void writeln(T x){write(x),putchar('\n');}
}
using namespace io;

const int N=1e5+10,M=1e6+10;
int n,m,a[N],cnt[N],bl[M],sz,ans[M];
struct qry{int l,r,id,a,b;}q[M];
bool cmp(qry a,qry b){return(bl[a.l]^bl[b.l])?bl[a.l]<bl[b.l]:((bl[a.l]&1)?a.r<b.r:a.r>b.r);}

struct tree
{
	int c[N];
	inline int lowbit(int x){return x&(-x);}
	void update(int x,int y) {for(int i=x;i<=n;i+=lowbit(i))c[i]+=y;}
	int sum(int x){int ans=0;while(x)ans+=c[x],x-=lowbit(x);return ans;}
}tr;

void add(int x)
{
	x=a[x];
	if(!cnt[x])	tr.update(x,1);
	++cnt[x];
}

void del(int x)
{
	x=a[x];
	--cnt[x];
	if(!cnt[x])	tr.update(x,-1);
}

signed main()
{
	n=read(),m=read();
	sz=n/sqrt(m*2/3);
	for(int i=1;i<=n;i++) bl[i]=(i-1)/sz+1;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		int ql=q[i].l,qr=q[i].r;
		while(l<ql) del(l++);
		while(l>ql) add(--l);
		while(r<qr) add(++r);
		while(r>qr) del(r--);
		ans[q[i].id]=tr.sum(q[i].b)-tr.sum(q[i].a-1);
	}
	for(int i=1;i<=m;i++) writeln(ans[i]);
	return 0;
}