题意

求三元组的严格上升子序列

思路

先考虑暴力\(dp\)一下

for(int i = 1;i <= n;++i)

    for(int j = 1;j < i;++j)

        if(x[i] > x[j] && y[i] > y[j] && z[i] > z[j])

            f[i] = max(f[i],f[j] + 1)

考虑用\(CDQ\)分治优化这个\(dp\)。

大体思路是，先按照第一维排序，保证第一维是严格上升的。然后\(CDQ\)一下第二维。树状数组维护第三维(需要先离散化)。这里用到的是树状数组维护前缀最大值。

有两个\(bug\)调了很久。

bug1

直接套用了三维偏序的板子。其实这个题在\(CDQ\)的时候是不能像这样的

void cdq(int l,int r) {

    if(r <= l) return;

    cdq(l,mid),cdq(mid + 1,r);

    //……

}

因为在\(cdq\)右边之前，必须保证右边已经从左边获取过答案了。这就是求\(LIS\)与求三维偏序不同的地方。

正确操作应该是

void cdq(int l,int r){

    if(r <= l) return;

    cdq(l,mid);

    //……

    cdq(mid + 1,r)

}

其实这个\(bug\)挺\(low\)的，感觉自己智障了2333

bug2

因为题目中说必须是严格递增的。所以\(mid\)的位置就不能直接取中间了。

需要找到一个\(x[mid]\)与\(x[mid + 1]\)不同的位置。

代码

/*

* @Author: wxyww

* @Date:   2019-02-15 10:45:05

* @Last Modified time: 2019-02-16 15:29:12

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<map>

#include<vector>

#include<ctime>

using namespace std;

typedef long long ll;

const int N = 300000 + 10;

map<int,int>ma;

ll read() {

    ll x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') {

        if(c=='-') f=-1;

        c=getchar();

    }

    while(c>='0'&&c<='9') {

        x=x*10+c-'0';

        c=getchar();

    }

    return x*f;

}

int ls[N],tree[N];

struct node {

    int x[10],ans;

}a[N];

ll A,P,n;

int js;

void clear(int pos) {

    while(pos <= js) {

        tree[pos] = 0;

        pos += pos & -pos;

    }

}

void update(int pos,int x) {

    while(pos <= js) {

        tree[pos] = max(x,tree[pos]);

        pos += pos & -pos;

    }

}

int query(int pos) {

    int ret = 0;

    while(pos) {

        ret = max(ret,tree[pos]);

        pos -= pos & -pos;

    }

    return ret;

}

node tmp[N];

bool cmp(node x,node y) {

    if(x.x[1] != y.x[1])

     return x.x[1] < y.x[1];

    if(x.x[2] != y.x[2]) return x.x[2] < y.x[2];

    return x.x[3] < y.x[3];

}

bool cmy(node x,node y) {

    if(x.x[2] != y.x[2]) return x.x[2] < y.x[2];

    return x.x[3] < y.x[3];

}

void cdq(int l,int r) {

    if(r <= l) return;

    //保证右边第一维严格大于左边

    sort(a + l,a + r + 1,cmp);

    int mid = (l + r) >> 1;

    int tt = 1e9;

    for(int i = l;i < r;++i) if(a[i].x[1] != a[i + 1].x[1] && abs(mid - i) < abs(mid - tt)) tt = i;

    if(tt == 1e9) return;

    mid = tt;

    //保证两边第二维分别有序

    cdq(l,mid);

    sort(a + l,a + mid + 1,cmy);

    sort(a + mid + 1,a + r + 1,cmy);

    int L = l,R = mid + 1,now = l;

    while(L <= mid && R <= r) {

        if(a[L].x[2] <= a[R].x[2]) {

            update(a[L].x[3],a[L].ans);

            ++L;

        }

        else a[R].ans = max(a[R].ans,query(a[R].x[3] - 1) + 1),++R;

    }

    while(R <= r) a[R].ans = max(a[R].ans,query(a[R].x[3] - 1) + 1),++R;

    for(int i = l;i <= L;++i) clear(a[i].x[3]);

    cdq(mid + 1,r);

}

int main() {

    A = read(),P = read(),n = read();

    ll now = 1;

    int tot = 0;

    for(int i = 1;i <= n;++i)

        for(int j = 1;j <= 3;++j)

            ls[++tot] = a[i].x[j] = now = now * A % P,a[i].ans = 1;

    sort(ls + 1,ls + tot + 1);

    ma[ls[1]] = ++js;

    for(int i = 2;i <= tot;++i) if(ls[i] != ls[i - 1]) ma[ls[i]] = ++js;

    for(int i = 1;i <= n;++i) {

        for(int j = 1;j <= 3;++j)

            a[i].x[j] = ma[a[i].x[j]];

        sort(a[i].x + 1,a[i].x + 4);

    }

    cdq(1,n);

    int ans = 0;

    for(int i = 1;i <= n;++i) ans = max(ans,a[i].ans);

    cout<<ans;

    return 0;

}

巴特西

bzoj2253 纸箱堆叠

题意

思路

bug1

bug2

代码

最新文章

热门文章