记录编号	344597	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 小鱼之美	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	32.430 s
提交时间	2016-11-10 13:08:22	内存使用	38.03 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=500010;
int t,n,m,X[2][2],x[N][2];
#define lc x<<1
#define rc (x<<1)|1
long long tag[N][2];int now;
void change(int x,int l,int r,int L,int R,int d1,int d2){
	if (l>=L&&r<=R){tag[x][0]+=d1;tag[x][1]+=d2;return;}
	int mid=(l+r)>>1;
	if (R>mid) change(rc,mid+1,r,L,R,d1,d2);
	if (L<=mid) change(lc,l,mid,L,R,d1,d2);
}
int visit(int x,int l,int r,int p){
	while (l!=r){
		tag[lc][0]+=tag[x][0];
		tag[lc][1]+=tag[x][1];
		tag[rc][0]+=tag[x][0];
		tag[rc][1]+=tag[x][1];
		tag[x][0]=tag[x][1]=0;
		int mid=(l+r)>>1;
		if (p>mid) l=mid+1,x=rc;
			else r=mid,x=lc;
	}
	return x;
}
struct ask{int tp,l,r,x,y;}q[N];
void go_to(int T){//将时间戳转移到T时刻 
	while (now<T){
		now++;
		if (q[now].tp!=3) change(1,1,n,q[now].l,q[now].r,q[now].x,q[now].y);
	}
	while (now>T){
		if (q[now].tp!=3) change(1,1,n,q[now].l,q[now].r,-q[now].x,-q[now].y);
		now--;
	}
}
int ansl[N],ansr[N],a[N],b[N];
//鱼i时间在[ansl[i],ansr[i]]内处于网内 
//整体二分,得到鱼在网内的最小时刻和最大时刻 
//[l,r]为答案区间,[L,R]为询问区间 
void solvel(int l,int r,int L,int R){
	if (L>R) return;
	if (l==r){
		for (int i=L;i<=R;i++) ansl[a[i]]=l;
		return;
	}
	int mid=(l+r)>>1,lp=L-1,rp=R+1;
	go_to(mid);
	for (int i=L;i<=R;i++){
		int v=a[i],p=visit(1,1,n,v);
		if (x[v][0]+tag[p][0]>=X[0][0]&&x[v][1]+tag[p][1]>=X[0][1])
			b[++lp]=v;else b[--rp]=v;
	}
	for (int i=L;i<=R;i++) a[i]=b[i];
	solvel(l,mid,L,lp);
	solvel(mid+1,r,rp,R);
}
void solver(int l,int r,int L,int R){
	if (L>R) return;
	if (l==r){
		for (int i=L;i<=R;i++) ansr[a[i]]=l;
		return;
	}
	int mid=(l+r)>>1,lp=L-1,rp=R+1;
	go_to(mid+1);
	for (int i=L;i<=R;i++){
		int v=a[i],p=visit(1,1,n,v);
		if (x[v][0]+tag[p][0]<=X[1][0]&&x[v][1]+tag[p][1]<=X[1][1])
			b[--rp]=v;else b[++lp]=v;
	}
	for (int i=L;i<=R;i++) a[i]=b[i];
	solver(l,mid,L,lp);
	solver(mid+1,r,rp,R);
}
struct bit{
	int a[N];
	int sum(int r){
		int ans=0;
		for (;r;r-=(r&-r)) ans+=a[r];
		return ans;
	}
	int sum(int l,int r){return sum(r)-sum(l-1);}
	void add(int p,int d){
		for (;p<=n;p+=(p&-p)) a[p]+=d;
	}
	void clear(){memset(a,0,sizeof a);}
}T;
struct opt{int tp,T,l,r,p;}Q[N];
bool cmp(const opt &x,const opt &y){
	return x.T==y.T?x.tp<y.tp:x.T<y.T;
}
int ans[N];
int main()
{
	freopen("skyfishs.in","r",stdin);
	freopen("skyfishs.out","w",stdout);
	scanf("%d",&t);
	while (t--){
		scanf("%d%d%d%d%d",&n,&X[0][0],&X[0][1],&X[1][0],&X[1][1]);
		for (int i=1;i<=n;i++)
			scanf("%d%d",&x[i][0],&x[i][1]);
		scanf("%d",&m);
		T.clear();
		memset(tag,0,sizeof tag);
		memset(Q,0,sizeof Q);
		memset(q,0,sizeof q);
		for (int i=1;i<=m;i++){
			scanf("%d%d%d",&q[i].tp,&q[i].l,&q[i].r);
			if (q[i].tp==1) scanf("%d",&q[i].x);
			if (q[i].tp==2) scanf("%d",&q[i].y);
		}
		q[m+1].l=1;q[m+1].r=n;
		q[m+1].x=q[m+1].y=1e9;
		now=0;
		for (int i=1;i<=n;i++) a[i]=i;
		solvel(0,m+1,1,n);
		for (int i=1;i<=n;i++) a[i]=i;
		solver(0,m+1,1,n);
		int cnt=0;
		for (int i=1;i<=m;i++)
		if (q[i].tp==3){
			cnt++;Q[cnt].tp=3;Q[cnt].T=i;
			Q[cnt].l=q[i].l;Q[cnt].r=q[i].r;
		}
		for (int i=1;i<=n;i++)
		if (ansl[i]<=ansr[i]){
			cnt++;Q[cnt].tp=1;Q[cnt].T=ansl[i];Q[cnt].p=i;
			cnt++;Q[cnt].tp=2;Q[cnt].T=ansr[i]+1;Q[cnt].p=i;
		}
		sort(Q+1,Q+cnt+1,cmp);
		for (int i=1;i<=cnt;i++){
			if (Q[i].tp==1) T.add(Q[i].p,1);
			if (Q[i].tp==2) T.add(Q[i].p,-1);
			if (Q[i].tp==3) ans[Q[i].T]=T.sum(Q[i].l,Q[i].r);
		}
		for (int i=1;i<=m;i++)
		if (q[i].tp==3) printf("%d\n",ans[i]);
	}
	return 0;
}