【ツリーセット】【bzoj 3236】:[Ahoi 2013]作業

http://www.lydsy.com/JudgeOnline/problem.php?id=3236
BITセットSBT
Treapは救いようがなくて、いくら定数を最適化しても過ぎられないので、勝手にSBTに変えました....
SBTのszを始めます.私が使っているsメンテナンスの結果、狂RE......
最後に90 sカードを通しました....モーチームより遅いです.....
2 h虐待されました.....
早く知っていてください......
莫队はOのロゴなのに、私のはOです.なぜ遅くて理解できませんか?.................
きっと私が弱すぎます......Orz 5 s过ぎる神犇...
..........................
後で時間があったら試してみます.http://hi.baidu.com/greencloud/item/0e25878061444bde5e0ec1f7

//#define _TEST _TEST
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
    int r=0,k=1;char c=getchar();
    for(;c'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return k*r;
}
/////////////////////////////////////////////////
int n,m;
int A[100010];
inline int rnd(){return (rand()<<16)|rand();}
struct data{int id,l,r,a,b;}q[1000010];
bool cmp(data a,data b){return a.rT[RS].sz) r_rot(o);
		else if(T[T[LS].r].sz>T[RS].sz) l_rot(LS),r_rot(o);
		else return;
	}
	else
	{
		if(!RS) return;
		if(T[T[RS].r].sz>T[LS].sz) l_rot(o);
		else if(T[T[RS].l].sz>T[LS].sz) r_rot(RS),l_rot(o);
		else return;
	}
    maintain(LS,0); maintain(RS,1);
    maintain(o,0);  maintain(o,1);
}
inline void insert(int &o,int x)
{
	if(o==0)
	{
		o=++sz; T[o].sz=T[o].s=T[o].cnt=1; T[o].x=x; T[o].w=0; T[o].sum=0;
		return;
	}
	T[o].s++; T[o].sz++;
	if(xT[o].x)
	{
		insert(RS,x);
		maintain(o,1);
	}
	else T[o].cnt++;
}
inline int query1(int o,int x)
{
	int res=0;
	while(o)
	{
		if(xT[o].x) res+=T[LS].s+T[o].cnt,o=RS;
		else return res+T[LS].s+T[o].cnt;
	}
	return res;
}
inline int query2(int o,int x)
{
	int res=0;
	while(o)
	{
		if(xT[o].x) o=RS;
		else return res+T[RS].s+T[o].cnt;
	}
	return res;
}
inline void add(int o,int clr,int x)
{
	while(o)
	{
		T[o].sum+=x;
		if(clrT[o].x) o=RS;
		else T[o].w+=x,o=0;
	}
}
inline int query3(int o,int x)
{
	int res=0;
	while(o)
	{
		if(xT[o].x) res+=T[LS].sum+T[o].w,o=RS;
		else return res+T[LS].sum+T[o].w;
	}
	return res;
}
inline int query4(int o,int x)
{
	int res=0;
	while(o)
	{
		if(xT[o].x) o=RS;
		else return res+T[RS].sum+T[o].w;
	}
	return res;
}
}/////////////////////////////////
namespace BIT
{/////////////////////////////////
inline void insert(int o,int x)
{
	for(;o<=n;o+=o&-o)
	    SBT::insert(SBT::root[o],x);
}
inline int query1(int o,int a,int b)
{
	using namespace SBT;
	int s=0;
	for(;o>0;o-=o&-o)
	    s+=SBT::query2(root[o],a) + SBT::query1(root[o],b);
    return s;
}
inline int query2(int o,int a,int b)
{
	using namespace SBT;
	int s=0;
	for(;o>0;o-=o&-o)
	    s+=SBT::query3(root[o],b) + SBT::query4(root[o],a) - SBT::query3(root[o],n);
    return s;
}
inline void add(int o,int clr,int x)
{
	for(;o<=n;o+=o&-o)
	    SBT::add(SBT::root[o],clr,x);
}
}/////////////////////////////////
/////////////////////////////////////////////////
void input()
{
	using namespace BIT;
    scanf("%d%d",&n,&m);
    int x;
    rep(i,1,n)
    	insert(i,A[i]=getint());
    rep(i,1,m)
    	q[i].id=i, q[i].l=getint(), q[i].r=getint(), q[i].a=getint(), q[i].b=getint();
   	sort(&q[1],&q[m+1],cmp);
}
void solve()
{
	using namespace BIT;
	int cur=1;
	int id,l,r,a,b;
	rep(i,1,n)
	{
		int &lst=last[A[i]];
        if(lst==0) add(i,A[i],1);
        else add(lst,A[lst],-1), add(i,A[i],1);
        last[A[i]]=i;
        
		for(;q[cur].r==i && cur<=m;cur++)
		{
			id=q[cur].id; l=q[cur].l-1; r=q[cur].r; a=q[cur].a; b=q[cur].b;
			
			int s1=query1(r,a,b)-r;
			int s2=query1(l,a,b)-l;
            ans1[id]=s1-s2;
            
            s1=query2(r,a,b);
            s2=query2(l,a,b);
            ans2[id]=s1-s2;
		}
	}
	rep(i,1,m) printf("%d %d
",ans1[i],ans2[i]);
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input(),
    solve();
    return 0;
}