Luogu 省选计划 #1

• 整体二分
• CDQ 分治

问题 2（P3527）

一次模拟下雨是把所有国家的一起下了，不妨所有国家一起二分。二分定义域为时间轴，初始把所有国家都挂在 \(k / 2\) 上，然后根据结果分别缩小范围，但每一层虽然是若干个区间但是还是那样扫过去。用线段树维护，可以做到 \(O(n \log^2 n)\)。（\(n,m,k\) 同阶）
https://www.luogu.com.cn/blog/78372/parallel-binsearch
这个里面告诉我，还可以 \(O(n \log n)\)。【待补】

问题 4（P3810）

\(k\) 维偏序用 bitset 直接暴力怎么做：
\(A_{i,j}\) 维护是否 \(a_i \le a_j\)。这个排序之后扫一遍过去就可以维护了。
最朴素的做法，开 \(k\) 个数组分别维护，最后合并即可。

\(3\) 维偏序，\(1e5\)。怎么办，首先由于数组最后也要合并，只需要用一个数组一直存即可。然后发现空间 \(1e10 = 1\operatorname{GB}\) 过不去，考虑分块每次只算一部分内容，假设块长为 \(l\)，那么空间复杂度 \(O(\cfrac{nl}{\omega})\)，时间复杂度 \(O(\cfrac{n^3}{l\omega})\)。显然空间不超限制的时候尽量增大 \(l\)，取 \(l = 30000\) 可以过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
struct tin {
    int a, b, c, ind;
}q[100010];
bitset<100010> x[30010];
bool cmpa(tin a, tin  b) {return a.a < b.a;}
bool cmpb(tin a, tin  b) {return a.b < b.b;}
bool cmpc(tin a, tin  b) {return a.c < b.c;}
int ans[200010];
const int m = 30000;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int n, k; cin >> n >> k;
    f(i, 1, n) {
        cin >> q[i].a >> q[i].b >> q[i].c;
        q[i].ind = i;
    }
    int num = (n + m - 1) / m;
    f(i, 1, num ){
        int kl = (m * (i - 1) + 1), kr = min(n, m * i);
        bitset<100010> std;
        vector<int> v;
        sort(q + 1, q + n + 1, cmpa); 
        f(i, 1, n) {
            std[q[i].ind] = 1;
            v.push_back(q[i].ind);
            if(i == n || q[i].a != q[i+1].a) {
                for(int j : v) {
                    if(j >= kl && j <= kr) x[j - kl + 1] = std;
                    
                }
                v.clear();
            }
        }
        f(i, 1, n) std[i] = 0;
        sort(q + 1, q + n + 1, cmpb); 
        f(i, 1, n) {
            std[q[i].ind] = 1;
            v.push_back(q[i].ind);
            if(i == n || q[i].b != q[i+1].b) {
                for(int j : v) {
                    if(j >= kl && j <= kr) x[j - kl + 1] &= std;
                }
                v.clear();
            }
        }
        f(i, 1, n) std[i] = 0;
        sort(q + 1, q + n + 1, cmpc); 
    
        f(i, 1, n ) {
            std[q[i].ind] = 1;
            v.push_back(q[i].ind);
            if(i == n || q[i].c != q[i+1].c) {
                for(int j : v) {
                    if(j >= kl && j <= kr) x[j - kl + 1] &= std;
                }
                v.clear();
            }
        }    
        f(i, 1, kr - kl + 1) {
            ans[x[i].count() - 1] ++;
        }
    }
    f(i, 0, n - 1) cout << ans[i] << endl;
    
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}

但是正经 CDQ 分治也是要做的。