记录编号	365625	评测结果	AAAAAAAAAA
题目名称	[AHOI 2013] 作业	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	16.060 s
提交时间	2017-01-21 09:03:02	内存使用	125.80 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char CH;inline void R_int(int &x){
	while(CH=getchar(),CH<'!');x=CH-48;
	while(CH=getchar(),CH>'!')x=x*10+CH-48;
}
const int SIZEN=100005,maxn=SIZEN*20,maxm=SIZEN*10,maxq=SIZEN*3*17,N=17;
int n,m,h[SIZEN],low[SIZEN];
struct Rabit_Tree{
	int rx[SIZEN],ls[maxn],rs[maxn],v[maxn],len,pos,qx,ans[maxm],s,t;
	int build(int l,int r){
		int rt=++len;if(l==r)return rt;
		int mid=(l+r)>>1;
		ls[rt]=build(l,mid),rs[rt]=build(mid+1,r);
		return rt;
	}
	int set(int r0,int l,int r){
		int rt=++len;
		if(l==r){v[rt]=v[r0]+qx;return rt;}
		int mid=(l+r)>>1;
		if(pos<=mid)ls[rt]=set(ls[r0],l,mid),rs[rt]=rs[r0];
		else rs[rt]=set(rs[r0],mid+1,r),ls[rt]=ls[r0];
		v[rt]=v[ls[rt]]+v[rs[rt]];
		return rt;
	}
	int get(int r0,int rt,int l,int r){
		if(s<=l&&r<=t)return v[rt]-v[r0];
		int mid=(l+r)>>1,res=0;
		if(s<=mid)res+=get(ls[r0],ls[rt],l,mid);
		if(t> mid)res+=get(rs[r0],rs[rt],mid+1,r);
		return res;
	}
	void init(){
		len=0;qx=1;rx[0]=build(1,n);
		for(int i=1;i<=n;i++)pos=h[i],rx[i]=set(rx[i-1],1,n);
	}
	void Ans(int l,int r,int a,int b,int num){
		s=a,t=b;ans[num]=get(rx[l-1],rx[r],1,n);
	}
}A;
struct Rabit_tree{int to,next,ope;}e[maxm<<1];
int head[SIZEN],ans[maxm],a[maxm],b[maxm],c[maxm],pre[SIZEN],len=1;
int size[maxq],ch[maxq][2],rx[SIZEN],key,cnt=1;
void Rabit_set(int prt,int son,int ope){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,e[len].ope=ope;
}
int Rabit_set(int p){
	if(!p)p=++cnt;//,printf("set:%d\n",cnt);
	int res=p;
	bool c;
	for(int i=N;~i;i--){
		c=key>>i&1;
		if(!ch[p][c])ch[p][c]=++cnt;//,printf("ch:[%d]%d \n",c,p);
		p=ch[p][c],size[p]++;
	}
	return res;
}
int Rabit_sum(int p){
	if(!p)return 0;int res=0;bool c;
	for(int i=N;~i;i--){
		c=key>>i&1;
		if(c)res+=size[ch[p][0]];
		p=ch[p][c];
	}
	return res;
}
void Rabit_add(int i){
	for(;i<=n;i+=low[i])rx[i]=Rabit_set(rx[i]);
}
int Rabit_get(int l,int r){
	int res=0,i;
	for(i=l-1;i;i-=low[i])res-=Rabit_sum(rx[i]);
	for(i=r;i;i-=low[i])res+=Rabit_sum(rx[i]);
	return res;
}
#define to e[i].to
void Rabit_ans(){
	int rt,i;
	for(rt=1;rt<=n;rt++){
		key=pre[h[rt]]+1,pre[h[rt]]=rt,Rabit_add(h[rt]);
		for(i=head[rt];i;i=e[i].next)
			key=c[to]+1,ans[to]+=Rabit_get(a[to],b[to])*e[i].ope;
	}
}
int main(){
	freopen("ahoi2013_homework.in","r",stdin);
	freopen("ahoi2013_homework.out","w",stdout);
	R_int(n),R_int(m);int i,x,y;
	for(i=1;i<=n;i++)R_int(h[i]),low[i]=i&(-i);
	A.init();
	for(i=1;i<=m;i++)
		R_int(x),R_int(y),R_int(a[i]),R_int(b[i]),A.Ans(x,y,a[i],b[i],i),
		Rabit_set(x-1,i,-1),Rabit_set(y,i,1),c[i]=x;
	Rabit_ans();
	for(i=1;i<=m;i++)printf("%d %d\n",A.ans[i],ans[i]);
	//printf("->%d",cnt);
}