BZOJ3295动态逆序对

时间：2024-09-21 15:05:50

一道比较傻的CDQ分治

CDQ: 主要用于解决三位偏序的问题

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cstring>

using namespace std;

inline long long read()

{

    long long x = 0, flag = 1;

    char c;

    while(! isgraph(c = getchar()))

        if(c == '-')

            flag *= - 1;

    while(isgraph(c))

        x = x * 10 + c - '0', c = getchar();

    return x * flag;

}

void println(long long x)

{

    if(x < 0)

        putchar('-'), x *= - 1;

    if(x == 0)

        putchar('0');

    long long ans[10 + (1 << 4)], top = 0;

    while(x)

        ans[top ++] = x % 10, x /= 10;

    for(; top; top --)

        putchar(ans[top - 1] + '0');

    putchar('\n');

}

const long long MAXN = (long long)1e5 + (1 << 5);

struct spot

{

    long long t, pos, w;

    spot(){}

    spot(long long t, long long pos, long long w): t(t), pos(pos), w(w){}

}a[MAXN], b[MAXN];

long long pos[MAXN];

long long operator <(spot x, spot y)

{

    if(x.t != y.t)

        return x.t < y.t;

    return x.pos < y.pos;

}

long long n;

long long ans[MAXN];

long long tree[MAXN];

void modify(long long u, long long delta)

{

    while(u <= n)

        tree[u] += delta, u += (u & (-u));

}

long long query(long long u)

{

    long long ret = 0;

    while(u)

        ret += tree[u], u -= (u & (- u));

    return ret;

}

long long cmp(spot x, spot y)

{

    return x.pos < y.pos;

}

void CDQ(long long L, long long R)

{

    if(L + 1 >= R)

        return;

    long long top = 0;

    long long mid = (L + R) >> 1;

    for(long long i = L; i < mid; i ++)

        b[top] = a[i], b[top ++].t = - 1;

    for(long long i = mid; i < R; i ++)

        b[top ++] = a[i];

    sort(b, b + top, cmp);

    long long cnt = 0;

    for(long long i = 0; i < top; i ++)

    {

        if(b[i].t == - 1)

            modify(b[i].w, 1), cnt ++;

        else

            ans[b[i].t] += query(n) - query(b[i].w);

    }

    for(long long i = 0; i < top; i ++)

        if(b[i].t == - 1)

            modify(b[i].w, - 1);

    CDQ(L, mid);

    CDQ(mid, R);

}

long long cmp2(spot x, spot y)

{

    if(x.t != y.t)

        return x.t < y.t;

    return x.pos > y.pos;

}

long long cmp1(spot x, spot y)

{

    return x.pos > y.pos;

}

void CDQ1(long long L, long long R)

{

    if(L + 1 >= R)

        return;

    long long top = 0;

    long long mid = (L + R) >> 1;

    for(long long i = L; i < mid; i ++)

        b[top] = a[i], b[top ++].t = - 1;

    for(long long i = mid; i < R; i ++)

        b[top ++] = a[i];

    sort(b, b + top, cmp1);

    long long cnt = 0;

    for(long long i = 0; i < top; i ++)

    {

        if(b[i].t == - 1)

            modify(b[i].w, 1), cnt ++;

        else

            ans[b[i].t] += query(b[i].w);

    }

    for(long long i = 0; i < top; i ++)

        if(b[i].t == - 1)

            modify(b[i].w, - 1);

    CDQ1(L, mid);

    CDQ1(mid, R);

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("BZOJ3295.in", "r", stdin);

    freopen("BZOJ3295.out", "w", stdout);

    #endif

    n = read();

    long long m = read();

    for(long long i = 0; i < n; i ++)

        a[i].pos = i, a[i].w = read(), a[i].t = n - m, pos[a[i].w] = i;

    for(long long i = 0; i < m; i ++)

        a[pos[read()]].t = n - i;

    sort(a, a + n);

    memset(ans, 0, sizeof(ans));

    memset(tree, 0, sizeof(tree));

    CDQ(0, n);

    sort(a, a + n, cmp2);

    CDQ1(0, n);

    for(long long i = n - m + 2; i <= n; i ++)

        ans[i] += ans[i - 1];

    for(long long i = n; i > n - m; i --)

        println(ans[i]);

}

顺便, 承蒙YAY大神的指导, 学会了一个可以用来出数据的函数random_shuffle(int&, int&), 用于随机打乱区间中的元素. 附上对拍代码

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<cctype>

#include<algorithm>

using namespace std;

inline int read()

{

    int x = 0, flag = 1;

    char c;

    while(! isgraph(c = getchar()))

        if(c == '-')

            flag *= - 1;

    while(isgraph(c))

        x = x * 10 + c - '0', c = getchar();

    return x * flag;

}

void println(int x)

{

    if(x < 0)

        putchar('-'), x *= - 1;

    if(x == 0)

        putchar('0');

    int ans[10 + (1 << 4)], top = 0;

    while(x)

        ans[top ++] = x % 10, x /= 10;

    for(; top; top --)

        putchar(ans[top - 1] + '0');

    putchar('\n');

}

const int maxn=1e5+10;

int a[maxn];

int main() {

    freopen("bzoj3295.in","w",stdout);

    srand(time(0));

    int n=100000;

    printf("%d %d\n",n,n);

    for (int i=1;i<=n;++i) a[i]=i;

    random_shuffle(a+1,a+n+1);

    for (int i=1;i<=n;++i) printf("%d ",a[i]);

    puts("");

    random_shuffle(a+1,a+n+1);

    for (int i=1;i<=n;++i) printf("%d ",a[i]);

    puts("");

}

对拍用的BAT

@echo off

:loop

mkd

BZOJ3295

ni

fc BZOJ3295.out ni.out

if not errorlevel 1 goto loop

pause

相关文章