NEUOJ 1702：撩妹全靠魅力值（CDQ分治三维偏序）

http://acm.neu.edu.cn/hustoj/problem.php?id=1702

思路：三维偏序模板题，用CDQ分治+树状数组或者树套树。对于三元组（x，y，z），先对x进行排序，然后对x进行CDQ分治降维，在分治的区间对y进行排序，用树状数组维护z。

还不太理解CDQ分治。等待UPDATE。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <string>
  7 #include <iostream>
  8 #include <stack>
  9 #include <map>
 10 #include <queue>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 #define N 100010
 15 #define INF 0x3f3f3f3f
 16 struct node {
 17     int id, x, y, z;
 18     node () {}
 19     node (int x, int y, int z, int id) : x(x), y(y), z(z), id(id) {}
 20     bool operator == (const node &A) const {
 21         return (x == A.x && y == A.y && z == A.z);
 22     }
 23 } p[N];
 24  
 25 int gap, same[N], bit[N], ans[N];
 26  
 27 bool cmpx(const node &a, const node &b) {
 28     if(a.x != b.x) return a.x < b.x;
 29     if(a.y != b.y) return a.y < b.y;
 30     return a.z < b.z;
 31 }
 32  
 33 bool cmpy(const node &a, const node &b) {
 34     if(a.y != b.y) return a.y < b.y;
 35     if(a.x != b.x) return a.x < b.x;
 36     return a.z < b.z;
 37 }
 38  
 39 bool cmpid(const node &a, const node &b) { return a.id < b.id; }
 40  
 41 int lowbit(int x) { return x & (-x); }
 42  
 43 void update(int x, int val) {
 44     while(x <= gap) {
 45         bit[x] += val;
 46         x += lowbit(x);
 47     }
 48 }
 49  
 50 int query(int x) {
 51     int ans = 0;
 52     while(x) {
 53         ans += bit[x];
 54         x -= lowbit(x);
 55     }
 56     return ans;
 57 }
 58  
 59 void CDQ(int l, int r) {
 60     if(l == r) return ;
 61     int mid = (l + r) >> 1;
 62     CDQ(l, mid); CDQ(mid + 1, r);
 63     sort(p + l, p + r + 1, cmpy);
 64     for(int i = l; i <= r; i++)
 65         if(p[i].x <= mid) update(p[i].z, 1);
 66         else ans[p[i].id] += query(p[i].z);
 67     for(int i = l; i <= r; i++)
 68         if(p[i].x <= mid) update(p[i].z, -1);
 69 }
 70  
 71 int main()
 72 {
 73     int t;
 74     scanf("%d", &t);
 75     while(t--) {
 76         int n, a, b, c;
 77         scanf("%d", &n);
 78         gap = 0;
 79         for(int i = 1; i <= n; i++) {
 80             scanf("%d%d%d", &a, &b, &c);
 81             p[i] = node(a, b, c, i);
 82             if(c > gap) gap = c;
 83         }
 84         sort(p + 1, p + 1 + n, cmpx);
 85         memset(same, 0, sizeof(same));
 86         for(int i = 1; i <= n; ) {
 87             int j = i + 1;
 88             while(p[i] == p[j] && j <= n) j++;
 89             while(i < j) same[p[i++].id] = p[j-1].id;
 90         }
 91         memset(bit, 0, sizeof(bit));
 92         memset(ans, 0, sizeof(ans));
 93         for(int i = 1; i <= n; i++) p[i].x = i;
 94         CDQ(1, n);
 95         sort(p + 1, p + 1 + n, cmpid);
 96         for(int i = 1; i <= n; i++)
 97             printf("%d
", ans[same[p[i].id]]);
 98     }
 99     return 0;
100 }