记录编号	364405	评测结果	AAAAAAAAAA
题目名称	1851.[HDOJ5140]Hun Gui Wei公司	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	1.276 s
提交时间	2017-01-16 14:19:45	内存使用	54.67 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ls(x) (a[x].lc)
#define rs(x) (a[x].rc)
#define LL long long
const int maxn=150000; 
struct Node{
	int lc,rc;LL sum;
}a[maxn*22];
struct Date{
	int Earn,Level,Limit;
}peo[maxn];
int n,m,cnt,Limit[maxn],Level[maxn];
int root[maxn],rank_limit[maxn];
LL ans;
bool comp1(const Date & a,const Date & b){return a.Level<b.Level;}
void Insert(int x,LL z,int & rt,int l,int r){
	a[++cnt]=a[rt];rt=cnt;
	a[rt].sum+=z;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)Insert(x,z,ls(rt),l,mid);
	else Insert(x,z,rs(rt),mid+1,r);
}
LL Query(int s,int t,int pr,int rt,int l,int r){
	if(s>t)return 0;
	if(s<=l && t>=r)return a[rt].sum-a[pr].sum;
	int mid=(l+r)>>1;
	if(t<=mid)return Query(s,t,ls(pr),ls(rt),l,mid);
	if(s>mid)return Query(s,t,rs(pr),rs(rt),mid+1,r);
	return Query(s,t,ls(pr),ls(rt),l,mid)+Query(s,t,rs(pr),rs(rt),mid+1,r);

}
void Init();
int main(){
	//freopen("test.in","r",stdin);freopen("test.out","w",stdout);
	//system("diff hunguiwei.out hunguiwei.ans");
	freopen("hunguiwei.in","r",stdin);freopen("hunguiwei.out","w",stdout);
	while(scanf("%d",&n)!=EOF)Init();
	getchar();getchar();
	return 0;
}
void Init(){
	cnt=0;ans=0;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&peo[i].Earn,&peo[i].Level,&peo[i].Limit);
		Level[i]=peo[i].Level;Limit[i]=peo[i].Limit;
	}
	sort(Limit+1,Limit+n+1);
	sort(Level+1,Level+n+1);
	for(int i=1;i<=n;i++)peo[i].Limit=lower_bound(Limit+1,Limit+n+1,peo[i].Limit)-Limit;
	sort(peo+1,peo+n+1,comp1);//按照级别排序
	for(int i=1;i<=n;i++){
		root[i]=root[i-1];
		//printf("rt=%d ",root[i]);
		Insert(peo[i].Limit,peo[i].Earn,root[i],1,n);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		LL level_l,level_r,limit_l,limit_r;
		scanf("%lld%lld%lld%lld",&level_l,&level_r,&limit_l,&limit_r);
		level_l+=ans;level_r-=ans;if(level_l>level_r)swap(level_l,level_r);
		limit_l+=ans;limit_r-=ans;if(limit_l>limit_r)swap(limit_l,limit_r);
		//printf("%d_%d_%d_%d_\n",level_l,level_r,limit_l,limit_r);
		int s=lower_bound(Limit+1,Limit+n+1,limit_l)-Limit;
		int t=upper_bound(Limit+1,Limit+n+1,limit_r)-Limit-1;
		int pr=lower_bound(Level+1,Level+n+1,level_l)-Level;
		int rt=upper_bound(Level+1,Level+n+1,level_r)-Level-1;
		/*if(Level[rt]>level_r)rt--;
		if(Level[pr]>level_l)pr--;
		if(Limit[t]>limit_r)t--;
		if(Limit[s]>limit_l)s--;*/
		//puts("oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo");
		//printf("<<%d %d %d %d>>\n",s,t,pr,rt);
		//puts("oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo");
		ans=Query(s,t,root[pr-1],root[rt],1,n);
		//puts("oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo");
		printf("%lld\n",ans);
	}
}