2021 ICPC NanJing D

题目链接

题意

def Sort(A):
  n = len(A)
  for i in range(n):
    for j in range(n):
      if a[i] < a[j]:
        swap(a[i], a[j])

给定长度为$nn$的序列$AA$，求序列$AA$长度为$kk$的前缀序列执行上述代码时进行交换操作的次数$(1\le k\le n)(1\backslash leq\; k\backslash leq\; n)$

数据范围

• $1\le n\le 10^{5}1\; \backslash leq\; n\; \backslash leq\; 10^5$
• $1\le a_i\le n1\; \backslash leq\; a\_i\; \backslash leq\; n$

输入样例

3
5
2 3 2 1 5
3
1 2 3
1
1

输出样例

0 2 3 5 7
0 2 4
0

题解

我写残了，我有罪

通过我们分析观察可以发现，第一轮会将最大值放到序列的最前端，并且其实第一轮改变的是一个上升序列，比如对于2 3 2 1 5，其第1、第2、第5位组成的改变的上升序列，在第一轮之后到排序完需要的步数是第一轮过后的类似逆序对一样的东西，跟逆序对不同的是相同的数字只能算一次。

推到这里之后基本已经出来了，我们可以从后往前一个一个删掉元素同时维护需要的步数，维护时一定要注意对于重复元素的计算！！

Code

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

template<typename T>
inline T read() {
    T s = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
    return s * f;
}
#define gn() read<int>()

#define ll long long

constexpr int N = 1e5 + 9;
int a[N], vis[N], id[N];
int b[N], n;

ll ans[N]; int cnt[N];

struct Segment {
    int tree[N];

    static int lowbit(int x) {
        return (-x) & x;
    }

    void change(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }

    int sum(int x) {
        int val = 0;
        while (x) {
            val += tree[x];
            x -= lowbit(x);
        }
        return val;
    }

    int query(int l, int r) {
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }
} tree;

void solve() {
    n = gn();
    for (int i = 1; i <= n; ++i) {
        tree.tree[i] = 0, cnt[i] = 0; id[i] = 0;
        vis[i] = false;
    }


    int maxn = 0; queue<int> x; int num = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = gn(); b[i] = a[i];
        if (a[i] > maxn) {
            maxn = a[i];
            vis[i] = true;
            x.push(a[i]);
            ++num;
        }
    }

    b[1] = maxn;
    id[b[1]] = 1;
    for (int i = 2; i <= n; ++i) {
        if (vis[i]) {
            b[i] = x.front();
            x.pop();
        }
        if (id[b[i]] == 0) id[b[i]] = i;
    }
    x.pop();

    deque<int> Q;
    for (int i = 1; i <= n; ++i) {
        Q.push_back(b[i]);
//        cout << b[i] << " \n"[i == n];
    }

    ll sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += tree.query(b[i] + 1, n);
        if (++cnt[b[i]] == 1) tree.change(b[i], 1);
//        cout << cnt[b[i]] << "***\n";
//        cout << sum << '\n';
    }

    ans[n] = sum + num - 1;
    sum += num - 1; int prenum = 0;

    for (int i = n; i > 1; --i) {
        int now = Q.back();
//        cout << i << '\n';
//        for (auto to : Q) {
//            cout << to << ' ';
//        }
//        cout << '\n';
        if (not vis[i]) {
            sum -= tree.query(now + 1, n);
            ans[i - 1] = sum;
            if (--cnt[now] == 0) tree.change(now, -1);
            Q.pop_back();
        } else {
            sum -= 1;
            int pre = Q.front();
            sum -= i - cnt[pre];
//            cout << '?' << i - cnt[pre] << '\n';
            Q.pop_front();

            if (--cnt[pre] == 0) tree.change(pre, -1);
            sum -= tree.query(now + 1, n);
//            cout << '!' << tree.query(now + 1, n);

            sum += id[now] - 2;
//            cout << "wuwu" << id[now] << '\n';

            Q.pop_back();
            Q.push_front(now);
            ans[i - 1] = sum;
            ++prenum;
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " \n"[i == n];
    }
}

int main() {

    int _ = gn();
    while(_--) solve();
}

/*
3
5
2 3 2 1 5
3
1 2 3
1
1
18
6 5 12 12 11 2 10 10 5 10 13 15 13 10 17 7 11 2
 */