初涉k-d tree

听说k-d tree是一个骗分的好东西？（但是复杂度差评？？？

还听说绍一的kdt常数特别小？

KDT是什么

KDT的全称是k-degree tree，顾名思义，这是一种处理多维空间的数据结构。

例如，给定一张二维图，每次会插入一些点，并且查询一个矩形区域内的点数。

上面这个问题可以离线cdq分治，也可以离线离散化处理，这两个做法可以参见初涉二维数点问题。不过这就是2-d tree基础的应用，使得我们可以在线处理这个问题。

网上关于KDT的解释博客有很多，但我认为在了解了k-d tree的作用之后，直接上代码更利于理解一些。

预备知识：

1.平衡树

(2.线段树)

KDT的题目

【矩形求和】bzoj4066: 简单题

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令	参数限制	内容
1 x y A	1<=x,y<=N，A是正整数	将格子x,y里的数字加上A
2 x₁ y₁ x₂ y₂	1<=x₁<= x₂<=N 1<=y₁<= y₂<=N	输出x₁ y₁ x₂ y₂这个矩形内的数字和
3	无	终止程序

Input

输入文件第一行一个正整数N。

接下来每行一个操作。每条命令除第一个数字之外，

均要异或上一次输出的答案last_ans，初始时last_ans=0。

Output

对于每个2操作，输出一个对应的答案。

HINT

数据规模和约定

1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。

样例解释见OJ2683

题目分析

直接挂代码吧。

  1 #include<bits/stdc++.h>
  2 const int maxn = 200035;
  3 
  4 int n,root,D;
  5 long long lastAns,tot,lim;
  6 struct point
  7 {
  8     int d[2],mn[2],mx[2],l,r;　　//d[]表示当前点（下面有用[]重载过）
  9     long long sum,v;　　　　　//mn[]表示这棵子树内的点中坐标最小值，mx[]同理
 10     int &operator [] (int a)
 11     {
 12         return d[a];
 13     }
 14     friend bool operator == (point a, point b)
 15     {
 16         return b.d[0]==a.d[0]&&b.d[1]==a.d[1];
 17     }
 18     friend bool operator < (point a, point b)
 19     {
 20         return a[D] < b[D];
 21     }
 22 }now,a[maxn],t[maxn];
 23 
 24 int read()
 25 {
 26     char ch = getchar();
 27     long long num = 0;
 28     bool fl = 0;
 29     for (; !isdigit(ch); ch = getchar())
 30         if (ch=='-') fl = 1;
 31     for (; isdigit(ch); ch = getchar())
 32         num = (num<<1)+(num<<3)+ch-48;
 33     if (fl) num = -num;
 34     return num;
 35 }
 36 bool inside(int a1, int b1, int c1, int d1, int a2, int b2, int c2, int d2)　　　　　　//如果矩形1完全包含在矩形2里
 37 {
 38     return a1 >= a2 && c1 <= c2 && b1 >= b2 && d1 <= d2;
 39 }
 40 bool ouside(int a1, int b1, int c1, int d1, int a2, int b2, int c2, int d2)　　　　　　//如果矩形1和矩形2丝毫不相交　　　　　　
 41 {
 42     return c1 < a2 || a1 > c2 || d1 < b2 || d2 < b1;
 43 }
 44 void update(int x)　　　　　　　　　　//类似于线段树的pushup，将子树x的信息更新
 45 {
 46     int l = a[x].l, r = a[x].r;
 47     for (int i=0; i<=1; i++)
 48     {
 49         a[x].mn[i] = a[x].mx[i] = a[x][i];
 50         if (l){
 51             a[x].mn[i] = std::min(a[x].mn[i], a[l].mn[i]);
 52             a[x].mx[i] = std::max(a[x].mx[i], a[l].mx[i]);        
 53         }
 54         if (r){
 55             a[x].mn[i] = std::min(a[x].mn[i], a[r].mn[i]);
 56             a[x].mx[i] = std::max(a[x].mx[i], a[r].mx[i]);
 57         }
 58     }
 59     a[x].sum = a[l].sum+a[r].sum+a[x].v;　　　　//本题中有点权
 60 }
 61 void insert(int &k, int D)　　　　　　　　　　　　//类似平衡树的插入，每一次换一维比较
 62 {
 63     if (!k){
 64         k = ++tot;
 65         a[k][0] = a[k].mn[0] = a[k].mx[0] = now[0];
 66         a[k][1] = a[k].mn[1] = a[k].mx[1] = now[1];
 67     }
 68     if (a[k]==now){
 69         a[k].v += now.v, a[k].sum += now.v;　　//如果已经存在这个点
 70         return;
 71     }
 72     if (a[k][D] > now[D])
 73         insert(a[k].l, D^1);　　　　　　　　　　//D^1代表每一层插入换一维度比较（kdt核心）
 74     else insert(a[k].r, D^1);
 75     update(k);
 76 }
 77 int rebuild(int l, int r, int D)　　　　　　　　//kdt的重构（此处不同于替罪羊重构）
 78 {
 79     if (l > r) return 0;
 80     int mid = (l+r)>>1;
 81     ::D = D;
 82     std::nth_element(t+l, t+mid, t+r+1);
 83     a[mid] = t[mid];
 84     a[mid].l = rebuild(l, mid-1, D^1);
 85     a[mid].r = rebuild(mid+1, r, D^1);
 86     update(mid);
 87     return mid;
 88 }
 89 long long query(int x, int aa, int bb, int cc, int dd)
 90 {
 91     if (!x) return 0;
 92     long long tmp = 0;
 93     if (inside(a[x].mn[0], a[x].mn[1], a[x].mx[0], a[x].mx[1], aa, bb, cc, dd))
 94         return a[x].sum;
 95     if (ouside(a[x].mn[0], a[x].mn[1], a[x].mx[0], a[x].mx[1], aa, bb, cc, dd))
 96         return 0;
 97     if (inside(a[x][0], a[x][1], a[x][0], a[x][1], aa, bb, cc, dd)) tmp = a[x].v;
 98     tmp += query(a[x].l, aa, bb, cc, dd)+query(a[x].r, aa, bb, cc, dd);
 99     return tmp;
100 }
101 int main()
102 {
103     n = read();
104     lim = 10000;　　　　　　//设置阈值，插入次数超过阈值就重构
105     int tt,aa,bb,cc,dd,w,i;
106     memset(a, 0, sizeof a);
107     for (;;)
108     {
109         tt = read();
110         if (tt==3) break;
111         aa = read()^lastAns, bb = read()^lastAns;
112         if (tt==2){
113             cc = read()^lastAns, dd = read()^lastAns;
114             lastAns = query(root, aa, bb, cc, dd);
115             printf("%lld
",lastAns);
116         }else{
117             w = read()^lastAns;
118             now[0] = aa, now[1] = bb, now.v = w, now.sum = w;
119             insert(root, 0);
120             if (tot == lim){
121                 for (i=1; i<=tot; i++) t[i] = a[i];
122                 root = rebuild(1, tot, 0);　　　　　　//暴力重构
123                 lim += 10000;
124             }
125         }
126     }
127     return 0;
128 }

本题的关键已经注释在程序里了。

【单点最近点】bzoj2648: SJY摆棋子

Description

这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M

以后M行，每行3个数 t x y

如果t=1 那么放下一个黑色棋子

如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

题目分析

不管题目要求的是什么，其实我们对于KDT的维护都是大致相同的，变化的大多是query操作。

例如这题，结合我们已经维护好的节点信息：$mn[]$,$mx[]$等，应该如何query呢。

比方说我们现在在root节点上，那么我们可以得到的是root这个点与查询的点的距离，并且还知道整张图x,y坐标的最小及最大值。

这里我们可以用类似于启发式搜索的思想处理query。

我们处理出$f(x,y)=y到x矩形的距离$——其中“到x矩形的距离”指的是y点离最近属于矩形的点的距离。形象来说就是，一个网格图上这个矩形是一座城市，现在我在一个点上想要最快到达这个城市（到这个城市任何一个点都行）的距离。

1 inline int get(node a, node b)
2 {
3     int ret = 0;
4     for (int i=0; i<=1; i++) ret += std::max(0, a.mn[i]-b[i]);
5     for (int i=0; i<=1; i++) ret += std::max(0, b[i]-a.mx[i]);
6     return ret;
7 }

这就是这个距离函数。

有了这个距离函数，我们就可以得出当前节点的左右儿子所管辖的矩形距离查询点最少有多远。

那么为了更优，我们当然是要先走估价少的那一边。注意这里是启发式地query，而不是单纯的贪心。两者的区别是：启发式先走估计花费低的；贪心只走估计花费低的。

于是我们的query就解决了。

  1 /**************************************************************
  2     Problem: 2648
  3     User: AntiQuality
  4     Language: C++
  5     Result: Accepted
  6     Time:13684 ms
  7     Memory:57548 kb
  8 ****************************************************************/
  9  
 10 #include<bits/stdc++.h>
 11 const int maxn = 600035;
 12  
 13 int n,m,D,root,tot,sum,ans;
 14 struct node
 15 {
 16     int d[2],mn[2],mx[2],l,r;
 17     int &operator [](int a){return d[a];}
 18     bool operator == (node a)
 19     {
 20         return a.d[0]==d[0]&&d[1]==a.d[1];
 21     }
 22     bool operator < (node a) const
 23     {
 24         return d[D] < a.d[D];
 25     }
 26 }a[maxn],t[2*maxn],now;
 27  
 28 int read()
 29 {
 30     char ch = getchar();
 31     int num = 0;
 32     bool fl = 0;
 33     for (; !isdigit(ch); ch = getchar())
 34         if (ch=='-') fl = 1;
 35     for (; isdigit(ch); ch = getchar())
 36         num = (num<<1)+(num<<3)+ch-48;
 37     if (fl) num = -num;
 38     return num;
 39 }
 40 void rec(int x)
 41 {
 42     for (int i=0; i<=1; i++)
 43         a[x].mn[i] = a[x].mx[i] = a[x][i];
 44 }
 45 inline void update(int x)
 46 {
 47     int l = a[x].l, r = a[x].r;
 48     rec(x);
 49     for (int i=0; i<=1; i++)
 50     {
 51         if (l){
 52             a[x].mn[i] = std::min(a[x].mn[i], a[l].mn[i]);
 53             a[x].mx[i] = std::max(a[x].mx[i], a[l].mx[i]);
 54         }
 55         if (r){
 56             a[x].mn[i] = std::min(a[x].mn[i], a[r].mn[i]);
 57             a[x].mx[i] = std::max(a[x].mx[i], a[r].mx[i]);
 58         }
 59     }
 60 }
 61 int rebuild(int l, int r, int D)
 62 {
 63     if (l > r) return 0;
 64     int mid = (l+r)>>1;
 65     ::D = D;
 66     std::nth_element(t+l, t+mid, t+r+1);
 67     a[mid] = t[mid];
 68     a[mid].l = rebuild(l, mid-1, D^1);
 69     a[mid].r = rebuild(mid+1, r, D^1);
 70     update(mid);
 71     return mid;
 72 }
 73 void insert(int &x, int k)
 74 {
 75     if (!x){
 76         x = ++tot;
 77         a[x][0] = now[0], a[x][1] = now[1];
 78         rec(x);
 79     }
 80     if (a[x]==now) return;
 81     if (now[k] < a[x][k])
 82         insert(a[x].l, k^1);
 83     else insert(a[x].r, k^1);
 84     update(x);
 85 }
 86 inline int dis(node a, node b)
 87 {
 88     return abs(a[0]-b[0])+abs(a[1]-b[1]);
 89 }
 90 inline int get(node a, node b)
 91 {
 92     int ret = 0;
 93     for (int i=0; i<=1; i++) ret += std::max(0, a.mn[i]-b[i]);
 94     for (int i=0; i<=1; i++) ret += std::max(0, b[i]-a.mx[i]);
 95     return ret;
 96 }
 97 void query(int x)
 98 {
 99     int l = a[x].l, r = a[x].r, rl = 2e9, rr = 2e9, lgh = dis(a[x], now);
100     ans = std::min(ans, lgh);
101     if (l) rl = get(a[l], now);
102     if (r) rr = get(a[r], now);
103     if (rl < rr){
104         if (rl < ans) query(l);
105         if (rr < ans) query(r);
106     }else{
107         if (rr < ans) query(r);
108         if (rl < ans) query(l);
109     }
110 }
111 int query()
112 {
113     ans = 2e9;
114     query(root);
115     return ans;
116 }
117 int main()
118 {
119     n = read(), m = read();
120     for (int i=1; i<=n; i++) t[i][0] = read(), t[i][1] = read();
121     root = rebuild(1, n, 0);
122     tot = n;
123     for (int i=1; i<=m; i++)
124     {
125         int tt = read(), x = read(), y = read();
126         now[0] = x, now[1] = y;
127         if (tt==1){
128             insert(root, 0);
129         }else
130             printf("%d
",query());
131     }
132     return 0;
133 }

【单点k远点】2626: JZPFAR

Description

　　平面上有n个点。现在有m次询问，每次给定一个点(px, py)和一个整数k，输出n个点中离(px, py)的距离第k大的点的标号。如果有两个(或多个)点距离(px, py)相同，那么认为标号较小的点距离较大。

Input

　　第一行，一个整数n，表示点的个数。
　　下面n行，每行两个整数x_i, y_i，表示n个点的坐标。点的标号按照输入顺序，分别为1..n。
　　下面一行，一个整数m，表示询问个数。
　　下面m行，每行三个整数px_i, py_i, k_i，表示一个询问。

Output

　　m行，每行一个整数，表示相应的询问的答案。

数据规模和约定

　　50%的数据中，n个点的坐标在某范围内随机分布。
　　100%的数据中，n<=10^5, m<=10^4, 1<=k<=20，所有点(包括询问的点)的坐标满足绝对值<=10^9，n个点中任意两点坐标不同，m个询问的点的坐标在某范围内随机分布。

题目分析

这题是KDT查询单点第k远的应用。

其间有一个技巧：在小根堆里插入$k$个$-INF$，每次考虑当前值是否大于堆顶。如果当前值大于堆顶，那么弹出堆顶并且插入当前值。这里小根堆就相当于一个缓存区的作用，是挺巧妙的一种技巧。

那么有了上面这个trick我们就可以大胆query了。

  1 /**************************************************************
  2     Problem: 2626
  3     User: AntiQuality
  4     Language: C++
  5     Result: Accepted
  6     Time:22804 ms
  7     Memory:15364 kb
  8 ****************************************************************/
  9  
 10 #include<bits/stdc++.h>
 11 const int maxn = 100035;
 12  
 13 int D;
 14 struct point
 15 {
 16     long long d[2],mn[2],mx[2],l,r,id;
 17     long long &operator [](int x){return d[x];}
 18     bool operator < (point a) const
 19     {
 20         return d[D] < a.d[D];
 21     }
 22 }t[maxn],a[maxn],now;
 23 struct node
 24 {
 25     long long val,id;
 26     bool operator < (node a) const
 27     {
 28         return val > a.val||(val==a.val&&id < a.id);
 29     }
 30     node(long long a, long long b):val(a),id(b) {}
 31 };
 32 int n,m,k,root;
 33 std::priority_queue<node> q;
 34   
 35 int read()
 36 {
 37     char ch = getchar();
 38     int num = 0;
 39     bool fl = 0;
 40     for (; !isdigit(ch); ch = getchar())
 41         if (ch=='-') fl = 1;
 42     for (; isdigit(ch); ch = getchar())
 43         num = (num<<1)+(num<<3)+ch-48;
 44     if (fl) num = -num;
 45     return num;
 46 }
 47 void clear(std::priority_queue<node> &q)
 48 {
 49     std::priority_queue<node> emt;
 50     std::swap(q, emt);
 51 }
 52 void rec(int x)
 53 {
 54     for (int i=0; i<=1; i++) a[x].mn[i] = a[x].mx[i] = a[x][i];
 55 }
 56 void update(int x)
 57 {
 58     int l = a[x].l, r = a[x].r;
 59     rec(x);
 60     for (int i=0; i<=1; i++)
 61     {
 62         if (l){
 63             a[x].mn[i] = std::min(a[x].mn[i], a[l].mn[i]);
 64             a[x].mx[i] = std::max(a[x].mx[i], a[l].mx[i]);
 65         }
 66         if (r)
 67         {
 68             a[x].mn[i] = std::min(a[x].mn[i], a[r].mn[i]);
 69             a[x].mx[i] = std::max(a[x].mx[i], a[r].mx[i]);
 70         }
 71     }
 72 }
 73 int build(int l, int r, int k)
 74 {
 75     if (l > r) return 0;
 76     int mid = (l+r)>>1;
 77     D = k;
 78     std::nth_element(t+l, t+mid, t+r+1);
 79     a[mid] = t[mid];
 80     a[mid].l = build(l, mid-1, k^1);
 81     a[mid].r = build(mid+1, r, k^1);
 82     update(mid);
 83     return mid;
 84 }
 85 long long sqr(long long x){return x*x;}
 86 long long dis(point a, point b)
 87 {
 88     return sqr(a[0]-b[0])+sqr(a[1]-b[1]);
 89 }
 90 long long get(point a)
 91 {
 92     long long ret = 0;
 93     for (int i=0; i<=1; i++)
 94         ret += std::max(sqr(now[i]-a.mn[i]), sqr(now[i]-a.mx[i]));
 95     return ret;
 96 }
 97 void query(int x)
 98 {
 99     if (!x) return;
100     long long ll = -1e17, lr = -1e17, pur = dis(now, a[x]);
101     int l = a[x].l, r = a[x].r;
102     if (pur > q.top().val||(pur==q.top().val&&a[x].id<q.top().id))
103         q.pop(), q.push(node(pur, a[x].id));
104     if (l) ll = get(a[l]);
105     if (r) lr = get(a[r]);
106     if (ll > lr){
107         if (ll >= q.top().val) query(l);
108         if (lr >= q.top().val) query(r);
109     }else{
110         if (lr >= q.top().val) query(r);
111         if (ll >= q.top().val) query(l);
112     }
113 }
114 int main()
115 {
116     n = read();
117     for (int i=1; i<=n; i++) t[i][0] = read(), t[i][1] = read(), t[i].id = i;
118     root = build(1, n, 0);
119     m = read();
120     while (m--)
121     {
122         clear(q);
123         now[0] = read(), now[1] = read(), k = read();
124         for (int i=1; i<=k; i++) q.push(node(-1, 0));
125         query(root);
126         printf("%lld
",q.top().id);
127     }
128     return 0;
129 }

【全图k远点对】4520: [Cqoi2016]K远点对

Description

已知平面内 N 个点的坐标，求欧氏距离下的第 K 远点对。

Input

输入文件第一行为用空格隔开的两个整数 N， K。接下来 N 行，每行两个整数 X,Y，表示一个点

的坐标。1 < = N < = 100000， 1 < = K < = 100， K < = N*(N−1)/2 ， 0 < = X, Y < 2^31。

Output

输出文件第一行为一个整数，表示第 K 远点对的距离的平方（一定是个整数）。

题目分析

全图k远点对？

乍一看好像很玄学？

其实是和单点k远点的思路一样的。我们先向小根堆添加$2k$个$-INF$，然后枚举查询这n个点。之后的事情就都一样了。

复杂度似乎是$O(nsqrt{n})$？

  1 /**************************************************************
  2     Problem: 4520
  3     User: AntiQuality
  4     Language: C++
  5     Result: Accepted
  6     Time:1772 ms
  7     Memory:15364 kb
  8 ****************************************************************/
  9  
 10 #include<bits/stdc++.h>
 11 const int maxn = 100035;
 12  
 13 int D;
 14 struct point
 15 {
 16     long long d[2],mn[2],mx[2],l,r,id;
 17     long long &operator [](int x){return d[x];}
 18     bool operator < (point a) const
 19     {
 20         return d[D] < a.d[D];
 21     }
 22 }t[maxn],a[maxn],now;
 23 struct node
 24 {
 25     long long val,id;
 26     bool operator < (node a) const
 27     {
 28         return val > a.val||(val==a.val&&id < a.id);
 29     }
 30     node(long long a, long long b):val(a),id(b) {}
 31 };
 32 int n,m,k,root;
 33 std::priority_queue<node> q;
 34  
 35 int read()
 36 {
 37     char ch = getchar();
 38     int num = 0;
 39     bool fl = 0;
 40     for (; !isdigit(ch); ch = getchar())
 41         if (ch=='-') fl = 1;
 42     for (; isdigit(ch); ch = getchar())
 43         num = (num<<1)+(num<<3)+ch-48;
 44     if (fl) num = -num;
 45     return num;
 46 }
 47 void clear(std::priority_queue<node> &q)
 48 {
 49     std::priority_queue<node> emt;
 50     std::swap(q, emt);
 51 }
 52 void rec(int x)
 53 {
 54     for (int i=0; i<=1; i++) a[x].mn[i] = a[x].mx[i] = a[x][i];
 55 }
 56 void update(int x)
 57 {
 58     int l = a[x].l, r = a[x].r;
 59     rec(x);
 60     for (int i=0; i<=1; i++)
 61     {
 62         if (l){
 63             a[x].mn[i] = std::min(a[x].mn[i], a[l].mn[i]);
 64             a[x].mx[i] = std::max(a[x].mx[i], a[l].mx[i]);
 65         }
 66         if (r)
 67         {
 68             a[x].mn[i] = std::min(a[x].mn[i], a[r].mn[i]);
 69             a[x].mx[i] = std::max(a[x].mx[i], a[r].mx[i]);
 70         }
 71     }
 72 }
 73 int build(int l, int r, int k)
 74 {
 75     if (l > r) return 0;
 76     int mid = (l+r)>>1;
 77     D = k;
 78     std::nth_element(t+l, t+mid, t+r+1);
 79     a[mid] = t[mid];
 80     a[mid].l = build(l, mid-1, k^1);
 81     a[mid].r = build(mid+1, r, k^1);
 82     update(mid);
 83     return mid;
 84 }
 85 long long sqr(long long x)
 86 {
 87     return x*x;
 88 }
 89 long long dis(point a, point b)
 90 {
 91     return sqr(a[0]-b[0])+sqr(a[1]-b[1]);
 92 }
 93 long long get(point a)
 94 {
 95     long long ret = 0;
 96     for (int i=0; i<=1; i++)
 97         ret += std::max(sqr(now[i]-a.mn[i]), sqr(now[i]-a.mx[i]));
 98     return ret;
 99 }
100 void query(int x)
101 {
102     if (!x) return;
103     long long ll = -1e17, lr = -1e17, pur = dis(now, a[x]);
104     int l = a[x].l, r = a[x].r;
105     if (pur > q.top().val)
106         q.pop(), q.push(node(pur, a[x].id));
107     if (l) ll = get(a[l]);
108     if (r) lr = get(a[r]);
109     if (ll > lr){
110         if (ll >= q.top().val) query(l);
111         if (lr >= q.top().val) query(r);
112     }else{
113         if (lr >= q.top().val) query(r);
114         if (ll >= q.top().val) query(l);
115     }
116 }
117 int main()
118 {
119     n = read(), k = read()<<1;
120     for (int i=1; i<=n; i++) t[i][0] = read(), t[i][1] = read(), t[i].id = i;
121     root = build(1, n, 0);
122     for (int i=1; i<=k; i++) q.push(node(-1, 0));
123     for (int i=1; i<=n; i++)
124     {
125         now = a[i];
126         query(root);
127     }
128     printf("%lld
",q.top().val);
129     return 0;
130 }

【半平面内点权和】2850: 巧克力王国

Description

巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎，因为大家都不喜

欢过于甜的巧克力。对于每一块巧克力，我们设x和y为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的

评判标准，所以每个人都有两个参数a和b，分别为他自己为牛奶和可可定义的权重，因此牛奶和可可含量分别为x

和y的巧克力对于他的甜味程度即为ax + by。而每个人又有一个甜味限度c，所有甜味程度大于等于c的巧克力他都

无法接受。每块巧克力都有一个美味值h。现在我们想知道对于每个人，他所能接受的巧克力的美味值之和为多少

Input

第一行两个正整数n和m，分别表示巧克力个数和询问个数。接下来n行，每行三个整数x,y,h，含义如题目所示。再

接下来m行，每行三个整数a,b,c，含义如题目所示。

Output

输出m行，其中第i行表示第i个人所能接受的巧克力的美味值之和。

HINT

1 <= n, m <= 50000，1 <= 10^9，-10^9 <= a, b, x, y <= 10^9。

题目分析

一开始把这题想复杂了。这题求的是半平面内点权和没错，不过查询时候并不需要多少复杂的思路。$ax + by<c$这个条件容易发现是单调的，于是我们就把它看作是一个单独的判断函数就行了。

这样query时候就可以像矩形求和一样，如果当前区间都满足条件则加上整颗子树的价值，否则递归判断下去。

 1 #include<bits/stdc++.h>
 2 const int maxn = 50003;
 3 
 4 int D,n,m,a,b,c,root;
 5 struct node
 6 {
 7     int d[2],mn[2],mx[2],l,r,v;
 8     long long sum;
 9     int &operator [](int a){return d[a];}
10     bool operator < (node a) const {return d[D]<a.d[D];}
11 }f[maxn],t[maxn];
12 
13 int read()
14 {
15     char ch = getchar();
16     int num = 0;
17     bool fl = 0;
18     for (; !isdigit(ch); ch = getchar())
19         if (ch=='-') fl = 1;
20     for (; isdigit(ch); ch = getchar())
21         num = (num<<1)+(num<<3)+ch-48;
22     if (fl) num = -num;
23     return num;
24 }
25 void update(int x)
26 {
27     int l = f[x].l, r = f[x].r;
28     for (int i=0; i<=1; i++)
29     {
30         f[x].mx[i] = f[x].mn[i] = f[x][i];
31         if (l){
32             f[x].mn[i] = std::min(f[x].mn[i], f[l].mn[i]);
33             f[x].mx[i] = std::max(f[x].mx[i], f[l].mx[i]);
34         }
35         if (r){
36             f[x].mn[i] = std::min(f[x].mn[i], f[r].mn[i]);
37             f[x].mx[i] = std::max(f[x].mx[i], f[r].mx[i]);
38         }
39     }
40     f[x].sum = f[l].sum+f[r].sum+f[x].v;
41 }
42 int build(int l, int r, int k)
43 {
44     if (l > r) return 0;
45     int mid = (l+r)>>1;
46     D = k;
47     std::nth_element(t+l, t+mid, t+r+1);
48     f[mid] = t[mid];
49     f[mid].l = build(l, mid-1, k^1);
50     f[mid].r = build(mid+1, r, k^1);
51     update(mid);
52     return mid;
53 }
54 int legal(int x, int y)
55 {
56     return a*x+b*y < c;
57 }
58 int calc(int x)
59 {
60     if (!x) return 0;
61     node a = f[x];
62     return legal(a.mn[0], a.mn[1])+legal(a.mn[0], a.mx[1])+legal(a.mx[0], a.mx[1])+legal(a.mx[0], a.mn[1]);
63 }
64 long long query(int x)
65 {
66     int l = f[x].l, r = f[x].r, ll = calc(l), lr = calc(r);
67     long long ret = 0;
68     if (calc(x)==4) return f[x].sum;
69     else if (legal(f[x][0], f[x][1])) ret += f[x].v;
70     if (ll) ret += query(l);
71     if (lr) ret += query(r);
72     return ret;
73 }
74 int main()
75 {
76     n = read(), m = read();
77     for (int i=1; i<=n; i++)
78     {
79         t[i][0] = read(), t[i][1] = read();
80         t[i].v = t[i].sum = read();
81     }
82     root = build(1, n, 0);
83     for (int i=1; i<=m; i++)
84     {
85         a = read(), b = read(), c = read();
86         printf("%lld
",query(root));
87     }
88     return 0;
89 }

END