求查错?
查看原帖
求查错?
90972
shitbro楼主2020/10/26 16:32
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
struct node {
	int x,y,p;
}B[N];
struct tr {
	int l,r,v;
}t[N << 5];
int tot = 0;
int bx[N],by[N],x[N],y[N],root[N];
bool cmp(node a,node b) {
	return a.x < b.x;
}
bool cmp1(node a,node b) {
	return a.y < b.y;
}
int build(int l,int r) {
	int p = ++ tot,mid = (l + r) >> 1;
	if(l < r) {
		t[p].l = build(l,mid);
		t[p].r = build(mid + 1,r);
	}
	return p;
}
int update(int last,int l,int r,int k,int P) {
	int p = ++ tot,mid = (l + r) >> 1;
	t[p].l = t[last].l;
	t[p].r = t[last].r; 
	t[p].v = t[last].v + P;
	if(l < r) {
		if(k <= mid) t[p].l = update(t[last].l,l,mid,k,P);
		else t[p].r = update(t[last].r,mid + 1,r,k,P);
	}
	return p;
}
int query(int x,int l,int r,int k) {
	if(l == r) return t[x].v;
	int mid = (l + r) >> 1;
	if(k <= mid) return query(t[x].l,l,mid,k);
	else return t[x].v + query(t[x].r,mid + 1,r,k);
}
int main() {
	int n,m; scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i ++) {
		scanf("%d%d%d",&B[i].x,&B[i].y,&B[i].p);
		x[i] = B[i].x;
		y[i] = B[i].y;
	}
	sort(x + 1,x + 1 + n);
	sort(y + 1,y + 1 + n);
	int cntx = unique(x + 1,x + 1 + n) - (x + 1);
	int cnty = unique(y + 1,y + 1 + n) - (y + 1);
	for(int i = 1;i <= n;i ++) {
		B[i].x = lower_bound(x + 1,x + 1 + cntx,B[i].x) - x;
		B[i].y = lower_bound(y + 1,y + 1 + cnty,B[i].y) - y;
	}
	root[0] = build(1,cnty);
	for(int i = 1;i <= n;i ++) {
		root[i] = update(i - 1,1,cnty,B[i].y,B[i].p);
	}
	while(m --) {
		int X1,Y1,X2,Y2; scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		int X = lower_bound(x + 1,x + 1 + cntx,X2) - x;
		int XX = lower_bound(x + 1,x + 1 + cntx,X1) - x - 1;
		int Y = lower_bound(y + 1,y + 1 + cnty,Y2) - y;
		int YY = lower_bound(y + 1,y + 1 + cnty,Y1) - y - 1;
		printf("%d\n",query(root[X],1,cnty,Y) - query(root[X],1,cnty,YY) - query(root[XX],1,cnty,Y) + query(root[XX],1,cnty,YY));  
	}
	return 0;
}

2020/10/26 16:32
加载中...