BZOJ 2850 巧克力王国

发表于 | 更新于

Link

Solution

留一个KDTree模板。。 另外，如果要强转int64，需要在每个优先级相同的并列的表达式里面都强转 比如 

1
int64 res=a*x+b*y

必须写成 

1
int64 res=(int64)a*x+(int64)b*y

居然被这种问题坑了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "lucida"
using std::max;
using std::min;
using std::pair;
using std::nth_element;
const int MAXN=50000+11,INF=2e9;
struct point {
	int x[2];
	point() {}
	point(int x0,int x1) {
		x[0]=x0;
		x[1]=x1;
	}
	int64 inner(int64 a,int64 b) {
		return a*x[0]+b*x[1];
	}
	int &operator [](int d) {
		return x[d];
	}
	const int &operator [](int d) const{
		return x[d];
	}
};
struct cmp {
	int d;
	cmp(int d):d(d) {}
	template <class T> 
	bool operator () (const pair<point,T> &a,const pair<point,T> &b) {
		return a.first[d]<b.first[d];
	}
};
namespace kdtree {
	struct Node *null;
	//0 min 1 mx
	struct Node {
		Node *son[2];
		point p,m[2];
		int64 val,sumv;
		Node():sumv(0) {
			m[0]=point(INF,INF);
			m[1]=point(-INF,-INF);
			son[0]=son[1]=0;
		}
		Node(point p,int64 val):p(p),val(val),sumv(val) {
			m[0]=m[1]=p;
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN);
			return Me++;
		}
		void Up() {
			for(int d=0;d<2;++d) {
				chkmn(m[0][d]=p[d],min(son[0]->m[0][d],son[1]->m[0][d]));
				chkmx(m[1][d]=p[d],max(son[0]->m[1][d],son[1]->m[1][d]));
			}
			sumv=val+son[0]->sumv+son[1]->sumv;
		}
		int64 PoMin(int64 a,int64 b) {
			int64 res=LLONG_MAX;
			for(int s0=0;s0<2;++s0)
				for(int s1=0;s1<2;++s1)
					chkmn(res,a*m[s0][0]+b*m[s1][1]);
			return res;
		}
		int64 PoMax(int64 a,int64 b) {
			int64 res=LLONG_MIN;
			for(int s0=0;s0<2;++s0)
				for(int s1=0;s1<2;++s1)
					chkmx(res,a*m[s0][0]+b*m[s1][1]);
			return res;
		}
	}*_null=null=new Node;
	//查询所有满足ax+by<c 的点权和
	struct KDTree {
		Node *root;
		void Build(Node *&pos,int L,int R,pair<point,int64> p[],int d) {
			if(L>R) return;
			int Mid=(L+R)>>1;
			nth_element(p+L,p+Mid,p+R+1,cmp(d));
			pos=new Node(p[Mid].first,p[Mid].second);
			if(L!=R) {
				Build(pos->son[0],L,Mid-1,p,d^1);
				Build(pos->son[1],Mid+1,R,p,d^1);
				pos->Up();
			}
		}
		KDTree(pair<point,int64> p[],int n) {
			Build(root,1,n,p,0);
		}
		int64 Query(Node *&pos,int a,int b,int64 c) {
			if(!pos) return 0;
			int64 pmn=pos->PoMin(a,b),pmx=pos->PoMax(a,b);
			if(pmx<c) return pos->sumv;
			else if(pmn>=c) return 0;
			else return Query(pos->son[0],a,b,c)+pos->val*(pos->p.inner(a,b)<c)+Query(pos->son[1],a,b,c);
		}
		int64 Query(int a,int b,int64 c) {
			return Query(root,a,b,c);
		}
	};
}using kdtree::KDTree;
int main() {
	freopen("input","r",stdin);
	static pair<point,int64> ch[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=n;++i)
		is>>ch[i].first[0]>>ch[i].first[1]>>ch[i].second;
	KDTree kdt(ch,n);
	for(int i=1;i<=m;++i) {
		int a,b;int64 c;is>>a>>b>>c;
		int64 Ans=kdt.Query(a,b,c);
		os<<Ans<<'\n';
	}
	return 0;
}