记录编号	367345	评测结果	AAAAAAAAAA
题目名称	[HDOJ5140]Hun Gui Wei公司	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	1.226 s
提交时间	2017-01-30 10:28:16	内存使用	51.43 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;
struct Node {
	long long sum;
	Node *lc, *rc;
};
Node p[maxn<<5], *root[maxn], *p_;
int N, x[maxn], y[maxn];
struct Mes {
	int s, x, y;
	bool operator < (const Mes& a) const {
		return x < a.x;
	}
} m[maxn];
int w, d, le, ri;
void build(int l, int r, Node *s0, Node *&s) {
	s = ++p_; *s = *s0; s->sum += d;
	if(l==r) return;
	int mid = (l+r)>>1;
	if(w<=mid) build(l, mid, s0->lc, s->lc);
	else build(mid+1, r, s0->rc, s->rc);
}
long long query(int l, int r, Node *s0, Node *s) {
	if(le<=l && r<=ri) return s->sum-s0->sum;
	int mid = (l+r)>>1;
	long long ans = 0;
	if(le<=mid) ans += query(l, mid, s0->lc, s->lc);
	if(ri>mid) ans += query(mid+1, r, s0->rc, s->rc);
	return ans;
}
int main() {
	freopen("hunguiwei.in", "r", stdin);
	freopen("hunguiwei.out", "w", stdout);
	while(scanf("%d", &N)!=EOF) {
		for(int i=1; i<=N; ++i) {
			scanf("%d%d%d", &m[i].s, &m[i].x, &m[i].y);
			x[i] = m[i].x; y[i] = m[i].y;
		}
		sort(x+1, x+N+1);
		sort(y+1, y+N+1);
		sort(m+1, m+N+1);
		root[0] = p_ = p->lc = p->rc = p;
		for(int i=1; i<=N; ++i) {
			w = lower_bound(y+1, y+N+1, m[i].y)-y; 
			d = m[i].s;
			build(1, N, root[i-1], root[i]);
		}
		int Q; scanf("%d", &Q);
		long long x1, x2, y1, y2, k = 0;
		while(Q--) {
			scanf("%lld %lld %lld %lld", &x1, &x2, &y1, &y2);
			x1 += k, x2 -= k, y1 += k, y2 -= k;
			if(x1>x2) swap(x1, x2);
			if(y1>y2) swap(y1, y2);
			x1 = lower_bound(x+1, x+N+1, x1)-x;
			x2 = upper_bound(x+1, x+N+1, x2)-x-1;
			y1 = lower_bound(y+1, y+N+1, y1)-y;
			y2 = upper_bound(y+1, y+N+1, y2)-y-1;
			le = y1, ri = y2;
			k = query(1, N, root[x1-1], root[x2]);
			printf("%lld\n", k);
		}
	}
	getchar(), getchar();
	return 0;
}