偏序问题

偏序集合是数学中，特别是序理论中，指配备了部分排序关系的集合。 这个理论将排序、顺序或
排列这个集合的元素的直觉概念抽象化。这种排序不必然需要是全部的，就是说不必要保证此集
合内的所有对象的相互可比较性。

一般的说偏序集合的两个元素 x 和 y 可以处于四个相互排斥的关联中任何一个：要么 x\<y ，要么x>y，要么x=y，要么x和y是不可比较的。
么 ，要么 ，要么 和 是不可比较的（三个都不是）。

问题形式：给定n个k元组，对于每个元组i，问有多少个元组j满足j里的每个元素都小于对应的i里的元素。

偏序问题离线时是比较容易解决的，如果强制在线，只能使用树套树，现在还不会，以后再说，这里只讨论离线的。

一维偏序问题

一维偏序其实就是全序的，排序就行。

二维偏序问题

二维偏序问题可以用树状数组，先把第一关键字排序，然后往后扫描，扫描到i时，用树状数组对[1,i)的元素进行统计，然后求第二关键字满足条件的个数即可。
时间复杂度O(nlogn)

三维偏序问题

目前只会CDQ分治
既然是分治的话，之前也写过MergeSort，格式大概就那样，先把第一维排序，然后分成左右两个区间，这样可以保证有区间不会对左区间有贡献，只考虑左区间对右区间的贡献，先分别对左右两区间操作，完成后左右两区间内已经分别按第二关键字排好序了，然后双指针分别扫描左右区间，对于右区间的元素j，把左区间中第二关键字小于j的元素分别加入树状数组，注意加入的是第三关键字值，这样统计有多少个元组的第三关键字小于j就行了。
最后在归并排序，把第二关键字排序即可。
时间复杂度O(nlog^2n)

多维偏序问题

可以CDQ分治套CDQ分治，也可以使用bitset和分块来做。

洛谷P3810 陌上花开
三维偏序板子

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5+5, maxk = 2e5+5;
int n, k, m;
struct zyh{
    int a, b, c;
    int w, t;
}nums[maxn], tmp[maxn];
int c[maxk], ans[maxn];
inline int lowbit(int i){
    return i & (-i);
}
void add(int i, int d){
    while (i<=k){
        c[i] += d;
        i += lowbit(i);
    }
    return;
}
int sum(int i){
    int ans = 0;
    while (i){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
void cdq(int l, int r){
    if (l==r)   return;
    int mid = (l+r) >> 1;
    cdq(l, mid);    cdq(mid+1, r);
    int i = l, j = mid+1, cnt = 0;
    for ( ; j<=r; j++){
        while (i<=mid && nums[i].b<=nums[j].b)  add(nums[i++].c, nums[i].t);
        nums[j].w += sum(nums[j].c);
    }
    for (i--; i>=l; i--)  add(nums[i].c, -nums[i].t);
    i = mid;
    i = l, j = mid+1;
    while (i<=mid && j<=r){
        if (nums[i].b <= nums[j].b) tmp[++cnt] = nums[i++];
        else    tmp[++cnt] = nums[j++];
    }
    while (i<=mid)  tmp[++cnt] = nums[i++];
    while (j<=r)    tmp[++cnt] = nums[j++];
    for (i=l, j=1; i<=r; i++, j++)  nums[i] = tmp[j];
    return;
}
inline bool cmp(struct zyh x, struct zyh y){
    if (x.a != y.a) return x.a < y.a;
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}
inline bool equal(struct zyh x, struct zyh y){
    if (x.a==y.a && x.b==y.b && x.c==y.c)   return true;
    return false;
}
int main(){
    scanf ("%d %d", &n, &k);
    for (int i=1; i<=n; i++){
        scanf ("%d %d %d", &nums[i].a, &nums[i].b, &nums[i].c);
        nums[i].w = 0, nums[i].t = 1;
    }
    sort (nums+1, nums+n+1, cmp);
    int cnt = 1;
    tmp[1] = nums[1];
    for (int i=2; i<=n; i++){
        if (!equal(nums[i], nums[i-1])) tmp[++cnt] = nums[i];
        else    tmp[cnt].t++;
    }
    m = n, n = cnt;
    for (int i=1; i<=n; i++)    nums[i] = tmp[i], nums[i].w = nums[i].t-1;
    cdq(1, n);
    for (int i=1; i<=n; i++)    ans[nums[i].w] += nums[i].t;
    for (int i=0; i<m; i++)
        printf ("%d\n", ans[i]);
    return 0;
}

考试

三维偏序 + 离散化

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5+5, maxm = 6e5+5;
int n, q;
struct zyh{
    int x, y, z;
    int w, t;
    int idx;
}nums[maxn], tmp[maxn];
struct zyha{
    int w, i, j, v;
}disc[maxm];
int cnt, tempn;
int c[maxm], m;
int ans[maxn/2], mp1[maxn], mp2[maxn];
inline int lowbit(int i){
    return i & (-i);
}
inline void add(int i, int d){
    while (i<=m){
        c[i] += d;
        i += lowbit(i);
    }
    return;
}
inline int sum(int i){
    int ans = 0;
    while (i){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
void cdq(int l, int r){
    if (l==r)   return;
    int mid = (l+r) >> 1;
    cdq(l, mid);    cdq(mid+1, r);
    int i=l, j=mid+1, cnt=0;
    for ( ; j<=r; j++){
        while (i<=mid && nums[i].y>=nums[j].y){
            add(nums[i].z, nums[i].t);
            i++;
        }
        nums[j].w += sum(m) - sum(nums[j].z-1);
    }
    for (i--; i>=l; i--)    add(nums[i].z, -nums[i].t);
    i=l, j=mid+1, cnt=0;
    while (i<=mid && j<=r){
        if (nums[i].y >= nums[j].y)   tmp[++cnt] = nums[i++];
        else    tmp[++cnt] = nums[j++];
    }
    while (i<=mid)  tmp[++cnt] = nums[i++];
    while (j<=r)    tmp[++cnt] = nums[j++];
    for (i=l, j=1; i<=r; i++, j++)  nums[i] = tmp[j];
    return;
}
inline int read(){
    int x=0;    char ch=getchar();
    while (ch<'0' || ch>'9')    ch=getchar();
    while (ch>='0' && ch<='9'){
        x = x*10 + ch-'0';
        ch=getchar();
    }
    return x;
}
inline bool cmp(struct zyha x, struct zyha y){
    return x.w < y.w;
}
inline bool cmp1(struct zyh a, struct zyh b){
    if (a.x != b.x) return a.x > b.x;
    if (a.y != b.y) return a.y > b.y;
    return a.z > b.z;
}
inline bool equal(struct zyh a, struct zyh b){
    if (a.x==b.x && a.y==b.y && a.z==b.z)   return true;
    return false;
}
int main(){
    int a, b;
    cnt = 0;
    scanf ("%d %d", &n, &q);
    tempn = n;
    for (int i=1; i<=n; i++){
        disc[++cnt].w = read(), disc[cnt].i = i, disc[cnt].j = 1;
        disc[++cnt].w = read(), disc[cnt].i = i, disc[cnt].j = 2;
        disc[++cnt].w = disc[cnt].w + disc[cnt-1].w, disc[cnt].i = i, disc[cnt].j = 3;
    }
    for (int i=n+1; i<=n+q; i++){
        disc[++cnt].w = read(), disc[cnt].i = i, disc[cnt].j = 1;
        disc[++cnt].w = read(), disc[cnt].i = i, disc[cnt].j = 2;
        disc[++cnt].w = read(), disc[cnt].i = i, disc[cnt].j = 3;
    }
    sort (disc+1, disc+1+cnt, cmp);
    disc[1].v = 1;
    for (int i=2; i<=cnt; i++){
        if (disc[i].w == disc[i-1].w)   disc[i].v = disc[i-1].v;
        else    disc[i].v = disc[i-1].v + 1;
    }
    m = disc[cnt].v;
    for (int i=1; i<=cnt; i++){
        if (disc[i].j==1)   nums[disc[i].i].x = disc[i].v;
        else if (disc[i].j==2)  nums[disc[i].i].y = disc[i].v;
        else    nums[disc[i].i].z = disc[i].v;
    }

    for (int i=1; i<=n; i++)  nums[i].t = 1;
    for (int i=n+1; i<=n+q+1; i++)  nums[i].t = 0;
    for (int i=1; i<=n+q+1; i++)    nums[i].idx = i;
    sort (nums+1, nums+n+q+1, cmp1);
    cnt = 1, tmp[1] = nums[1];
    for (int i=2; i<=n+q; i++){
        if (equal(nums[i], nums[i-1]))
            tmp[cnt].t += nums[i].t;
        else
            tmp[++cnt] = nums[i];
        mp1[nums[i].idx] = tmp[cnt].idx;
    }
    n = cnt;
    for (int i=1; i<=n; i++){
        nums[i] = tmp[i];
        nums[i].w = nums[i].t;
    }
    cdq(1, n);
    for (int i=1; i<=n; i++)    mp2[nums[i].idx] = nums[i].w;
    for (int i=1+tempn; i<=tempn+q; i++)    printf ("%d\n", mp2[mp1[i]]);
    return 0;
}