个人排位赛5补题记录

Another Longest Increasing Subsequence Problem (SPOJ LIS2)

比赛时一眼看出是CDQ分治，结果疯狂Wa4...

赛后不断去翻题解，直接复制别人代码的关键部分都无法AC，debug了将近一个小时~

最后找到了原因：dp[0]没有赋初值1（所有dp[$i\ne 0$]都为默认值0），导致计算最长上升子序列时，第0号元素无法对长度作贡献。

AC代码:

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;

int n, m, unq[maxn], unq_cnt = 0;
int dp[maxn];
struct info{
    int a, b, c;
};

vector<info> infos, tmp, tmp2;

int tag[maxn], fenwik[maxn], cur_time = 0;

void add(int pos, int delta){
    for(int i=pos; i<=unq_cnt+2; i+=(-i)&i){
        if(tag[i] != cur_time) tag[i] = cur_time, fenwik[i] = 0;
        fenwik[i] = max(delta, fenwik[i]);
    }
}

int query(int pos){
    int ret = 0;
    for(int i=pos; i>0; i-=(-i)&i){
        if(tag[i] != cur_time) tag[i] = cur_time, fenwik[i] = 0;
        ret = max(ret, fenwik[i]);
    }
    return ret;
}

bool cmp_b(info i1, info i2){
    if(i1.b != i2.b) return i1.b < i2.b;
    return i1.a < i2.a;
}

void cdq(int from, int to){
    if(from == to) return;
    int mid = (from + to) >> 1;
    cdq(from, mid);

    sort(infos.begin() + from, infos.begin() + mid + 1, cmp_b);

    for(int i=mid + 1; i<=to; i++) tmp[i] = infos[i];
    sort(tmp.begin() + mid + 1, tmp.begin() + to + 1, cmp_b);

    cur_time++;
    int l = from, r = mid + 1;
    while(l <= mid && r <= to){
        if(infos[l].b < tmp[r].b){
            add(infos[l].c, dp[infos[l].a]);
            l++;
        }else{
            int & ans = dp[tmp[r].a];
            ans = max(ans, query(tmp[r++].c - 1) + 1);
        }
    }
    while(r <= to){
        int & ans = dp[tmp[r].a];
        ans = max(ans, query(tmp[r].c - 1) + 1);
        r++;
    }
    cdq(mid + 1, to);
}

void solve(){
    cin >> n;
    tmp = vector<info>(n);
    infos = vector<info>(n);
    for(int i=0, x, y; i<n; i++){
        cin >> x >> y;
        infos[i] = {i, x, y};
        unq[unq_cnt++] = y;
    }

    sort(unq, unq + unq_cnt);
    unq_cnt = unique(unq, unq + unq_cnt) - unq;
    for(int i=0; i<n; i++){
        infos[i].c = lower_bound(unq, unq + unq_cnt, infos[i].c) - unq + 1;
    }
    dp[0] = 1;
    cdq(0, n - 1);
    int ans = 1;
    for(int i=0; i<n; i++) ans = max(ans, dp[i]);
    cout << ans << '\n';
}

signed main(){
    Android;
    solve();
}