题解 P3157 【[CQOI2011]动态逆序对】CDQ

眠ㅤㅤㅤ · 2019-02-17 19:02:11 · 个人记录

#include <bits/stdc++.h>
constexpr auto Inf = 0x3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
    inline LL read() {
        LL o = 0, f = 1; char c = getchar();
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
        return o * f;
    }
    inline char recd() {
        char o; while ((o = getchar()) != 'Q' && o < 'D'); return o;
    }
}
using namespace IO;

const int SIZE = 1E5 + 7;

struct _Ask {
    int per, p, w;
    _Ask(int per = 0, int p = 0, int w = 0) : per(per), p(p), w(w) {};
    bool operator < (const _Ask& Tmp) {
        return per < Tmp.per;
    }
} Ask[SIZE << 1], Tmp[SIZE << 1];

int N, M, Ind[SIZE];

LL BIT[SIZE];

void Upd(int pos, int w = 1) {
    while (pos <= N) BIT[pos] += w, pos += pos & -pos;
}

LL Que(int pos) {
    LL ans = 0; while (pos) ans += BIT[pos], pos -= pos & -pos;
    return ans;
}

LL ans[SIZE];

void CDQ(int L, int R) {
    if (L == R) return;
    int M = (L + R) >> 1; CDQ(L, M), CDQ(M + 1, R);
    int Lpos = L, Rpos = M + 1, now = L;

    while (Lpos <= M && Rpos <= R) {
        if (Ask[Lpos].w > Ask[Rpos].w)
            Upd(Ask[Lpos].p), Tmp[now++] = Ask[Lpos++];
        else
            ans[Ask[Rpos].per] += Que(Ask[Rpos].p), Tmp[now++] = Ask[Rpos++];
    }
    while (Lpos <= M)
        Upd(Ask[Lpos].p), Tmp[now++] = Ask[Lpos++];
    while (Rpos <= R)
        ans[Ask[Rpos].per] += Que(Ask[Rpos].p), Tmp[now++] = Ask[Rpos++];
    for (int pos = L; pos <= M; pos++)
        Upd(Ask[pos].p, -1);
    for (int pos = L; pos <= R; pos++)
        Ask[pos] = Tmp[pos];
}

int main() {
    N = read(), M = read();
    for (int pos = 1, w; pos <= N; pos++)
        w = read(), Ask[Ind[w] = pos] = _Ask(0, pos, w);
    int per = N;
    for (int pos = M, w; pos; pos--)
        w = read(), Ask[Ind[w]].per = per--;
    for (int pos = 1; pos <= N; pos++)
        if (!Ask[pos].per) Ask[pos].per = per--;

    sort(Ask + 1, Ask + 1 + N), CDQ(1, N);
    sort(Ask + 1, Ask + 1 + N);
    for (int pos = 1; pos <= N; pos++)
        swap(Ask[pos].p, Ask[pos].w);
    CDQ(1, N);
    for (int pos = 1; pos <= N; pos++) ans[pos] += ans[pos - 1];
    for(int pos = N; pos > N - M; pos--)
        printf("%lld\n", ans[pos]);
}