【BZOJ2253】[BJWC2010]纸箱堆叠

这个题目显然是一个严格化的三维偏序,即
a_i < a_j,b_i < b_j,c_i < c_j
那么问题显然就变成cdq优化转移了,注意这里是严格的,因此我们划分区间的时候,要保证所有第一维相同的数字在同一个区间,而不会被mid给分开……但是这样真的不会破坏复杂度吗我也不知道……

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 2e5 + 10;

lo a, p, n, lsh[ms], ta, tre[ms], ans;//lsh == 离散化 

struct node
{
    lo x, y, z, ans;

    inline bool operator < (const node &a) const
    {
        if(y != a.y)
            return y < a.y;
        return z < a.z;
    }
}ter[ms], tmp[ms];

inline bool cmp(node a, node 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 int lowbit(int x)
{
    return x & (-x);
}

inline void change(int x, lo v)
{
    while(x <= ta)
        tre[x] = max(tre[x], v), x += lowbit(x);    
}

inline lo ask(int x)
{
    lo rt = 0;
    while(x)
        rt = max(rt, tre[x]), x -= lowbit(x);
    return rt;
}

inline void clear(int x)
{
    while(x <= ta)
    {
        if(tre[x])
            tre[x] = 0;
        else
            break;
        x += lowbit(x);
    }
}

void merge(int l, int r)
{
    if(l >= r)
        return;
    int mid = (l + r) >> 1, t1 = mid, t2 = mid + 1; mid = ms;
    while(t1 >= l || t2 <= r)//为了保证三维偏序的严格,我们把第一维所有相同的数字划在一起而不是分到左右两边 
    {
        if(t1 >= l && ter[t1].x != ter[t1 + 1].x)
        {
            mid = t1; break;
        }
        if(t2 <= r && ter[t2].x != ter[t2 - 1].x)
        {
            mid = t2 - 1; break;
        }
        t1 --, t2 ++;
    }
    if(mid == ms)//如果第一维直接都是一样的,那不用算了 
        return;
    merge(l, mid);//先去计算左边 
    t1 = l, t2 = mid + 1;
    sort(ter + l, ter + mid + 1), sort(ter + mid + 1, ter + r + 1);
    for(ri i = l; i <= r; i ++)
    {
        if(t2 > r || (t1 <= mid && ter[t1].y < ter[t2].y))//如果右边的区间算完了,或者左边要比右边小 
            change(ter[t1].z, ter[t1].ans), t1 ++;
        else//否则更新答案 
            ter[t2].ans = max(ter[t2].ans, ask(ter[t2].z - 1) + 1), t2 ++;
    }
    for(ri i = l; i <= mid; i ++)//清空左边的影响 
        clear(ter[i].z);
    sort(ter + mid + 1, ter + r + 1, cmp), merge(mid + 1, r);//再去算右边 
}

int main()
{
    re(a), re(p), re(n);
    lo tmp = a % p;
    for(ri i = 1; i <= n; i ++, tmp = tmp * a % p)
    {
        ter[i].x = tmp, tmp = tmp * a % p, ter[i].y = tmp, tmp = tmp * a % p, ter[i].z = tmp;
        if(ter[i].x > ter[i].y)//提前排好序 
            swap(ter[i].x, ter[i].y);
        if(ter[i].x > ter[i].z)
            swap(ter[i].x, ter[i].z);
        if(ter[i].y > ter[i].z)
            swap(ter[i].y, ter[i].z);
        ter[i].ans = 1;
        lsh[++ ta] = ter[i].x, lsh[++ ta] = ter[i].y, lsh[++ ta] = ter[i].z;
    }
    sort(lsh + 1, lsh + 1 + ta);
    ta = unique(lsh + 1, lsh + 1 + ta) - lsh - 1;
    for(ri i = 1; i <= n; i ++)//离散化 
    {
        ter[i].x = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].x) - lsh;
        ter[i].y = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].y) - lsh;
        ter[i].z = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].z) - lsh;
    }
    sort(ter + 1, ter + 1 + n, cmp);
    merge(1, n);//cdq 
    for(ri i = 1; i <= n; i ++)//比较答案 
        ans = max(ans, ter[i].ans);
    printf("%lld", ans);
}

1 thought

发表评论

电子邮件地址不会被公开。 必填项已用*标注