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

#include <cstdio>
#include <cstring>
#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;
	bool operator < (const Date & a)const{
		return level<a.level;
	}
}p[maxn];
int n,m,cnt,level[maxn],limit[maxn];
int root[maxn];LL ans;
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("hunguiwei.in","r",stdin);freopen("hunguiwei.out","w",stdout);
	//freopen("test.in","r",stdin);freopen("test.out","w",stdout);
	//system("fc test.out test.ans");
	while(scanf("%d",&n)!=EOF)Init();
	getchar();getchar();
	return 0;
}
void Init(){ans=cnt=0;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&p[i].earn,&p[i].level,&p[i].limit);
		limit[i]=p[i].limit;
		level[i]=p[i].level;
	}
	sort(limit+1,limit+n+1);
	sort(level+1,level+n+1);
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		p[i].limit=lower_bound(limit+1,limit+n+1,p[i].limit)-limit;
		root[i]=root[i-1];
		Insert(p[i].limit,p[i].earn,root[i],1,n);
	}
	scanf("%d",&m);//printf("%d ",m);
	for(int i=1;i<=m;i++){//puts("ooooooooooooooooooooooooooooooooooooooooooooo");
		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);
		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;
		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;
		ans=Query(s,t,root[pr-1],root[rt],1,n);

		printf("%lld\n",ans);
	}
}