记录编号	344167	评测结果	WWWWWWWWWW
题目名称	2533.[HZOI 2016] 小鱼之美	最终得分	0
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	21.276 s
提交时间	2016-11-09 21:56:49	内存使用	24.29 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
int tag[N][2],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){
	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];
//[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);
}
int sum[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);
		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);
		}
		for (int i=1;i<=n;i++) a[i]=i;
		solvel(0,m,1,n);
		for (int i=1;i<=n;i++) a[i]=i;
		solver(0,m,1,n);
		memset(sum,0,sizeof sum);
		for (int i=1;i<=n;i++)
		if (x[i][0]<=X[1][0]&&x[i][1]<=X[1][1]&&ansl[i]<=ansr[i])
			sum[ansl[i]]++,sum[ansr[i]+1]--;
		for (int i=1;i<=m;i++){
			sum[i]+=sum[i-1];
			if (q[i].tp==3) printf("%d\n",sum[i]);
		}
	}
	return 0;
}