QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166969#7108. Couleurucup-team1113AC ✓2767ms39352kbC++204.4kb2023-09-06 21:58:182023-09-06 21:58:18

Judging History

你现在查看的是最新测评结果

  • [2023-09-06 21:58:18]
  • 评测
  • 测评结果:AC
  • 用时:2767ms
  • 内存:39352kb
  • [2023-09-06 21:58:18]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define pll pair<ll, ll>
#define tll tuple<ll, ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define x first
#define y second
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10, maxp = 20;
const ll mod = 998244353;
const ll inf = 0x3f3f3f3f;

int n, A[maxn + 10];
int tot, sum[maxn * maxp + 10], ch[maxn * maxp * 10][2], root[maxn + 2];
map<int, ll> mp; // mp[i]表示以A[i + 1]为开头的段的逆序对数(key均为已删除的位置)
multiset<ll> ms; // 保存所有段的逆序对数量

// 新建线段树节点
int newNode()
{
    tot++;
    sum[tot] = 0;
    ch[tot][0] = ch[tot][1] = 0;
    return tot;
}

// 添加一个整数 pos
void add(int id, int l, int r, int old, int pos)
{
    sum[id] = sum[old];
    ch[id][0] = ch[old][0];
    ch[id][1] = ch[old][1];

    if (l == r)
        sum[id]++;
    else
    {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            add(ch[id][0] = newNode(), l, mid, ch[old][0], pos);
        else
            add(ch[id][1] = newNode(), mid + 1, r, ch[old][1], pos);
        sum[id] = sum[ch[id][0]] + sum[ch[id][1]];
    }
}

// 询问整数 ql 到 qr 一共有几个
int query(int id, int l, int r, int ql, int qr)
{
    if (ql > qr)
        return 0;
    if (ql <= l && r <= qr)
        return sum[id];
    int mid = (l + r) >> 1;
    return (ql <= mid ? query(ch[id][0], l, mid, ql, qr) : 0) +
           (qr > mid ? query(ch[id][1], mid + 1, r, ql, qr) : 0);
}

// 启发式分裂,将区间 [L + 1, R - 1] 从 X 处分裂
void split(int L, int R, int X)
{
    ll old = mp[L];
    ms.erase(ms.find(old));
    // base:一个元素是 A[X] 的逆序对数
    ll base = query(root[R - 1], 1, n, 1, A[X] - 1) - query(root[X], 1, n, 1, A[X] - 1);
    base += query(root[X - 1], 1, n, A[X] + 1, n) - query(root[L], 1, n, A[X] + 1, n);
    if (X - L < R - X)
    {
        // 左半边更短,枚举左半边
        // a:[L + 1, X - 1] 的逆序对数
        // b:base + 一个元素在 [L + 1, X - 1],另一个元素在 [X + 1, R - 1] 的逆序对数
        ll a = 0, b = base;
        for (int i = L + 1; i < X; i++)
        {
            a += query(root[i - 1], 1, n, A[i] + 1, n) - query(root[L], 1, n, A[i] + 1, n);
            b += query(root[R - 1], 1, n, 1, A[i] - 1) - query(root[X], 1, n, 1, A[i] - 1);
        }
        mp[L] = a;
        ms.insert(mp[L]);
        mp[X] = old - a - b;
        ms.insert(mp[X]);
    }
    else
    {
        // 右半边更短,枚举右半边
        // a:[X + 1, R - 1] 的逆序对数
        // b:base + 一个元素在 [L + 1, X - 1],另一个元素在 [X + 1, R - 1] 的逆序对数
        ll a = 0, b = base;
        for (int i = X + 1; i < R; i++)
        {
            a += query(root[i - 1], 1, n, A[i] + 1, n) - query(root[X], 1, n, A[i] + 1, n);
            b += query(root[X - 1], 1, n, A[i] + 1, n) - query(root[L], 1, n, A[i] + 1, n);
        }
        mp[L] = old - a - b;
        ms.insert(mp[L]);
        mp[X] = a;
        ms.insert(mp[X]);
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> A[i];

    // 将 A[1] 到 A[n] 依次加入主席树
    // root[i] 就是加入 A[i] 之后的情况
    tot = 0;
    for (int i = 1; i <= n; i++)
        add(root[i] = newNode(), 1, n, root[i - 1], A[i]);

    // 计算整个序列的逆序对数
    ll tmp = 0;
    for (int i = 1; i <= n; i++)
        tmp += query(root[i - 1], 1, n, A[i] + 1, n);

    // 把下标 0 和 n + 1 视为已删除的下标,方便处理
    mp.clear();
    ms.clear();
    mp[0] = tmp;
    ms.insert(tmp);
    mp[n + 1] = 0;
    ms.insert(0);

    ll ans = *prev(ms.end());
    for (int i = 1; i <= n; i++)
    {
        cout << ans << " \n"[i == n];
        ll x;
        cin >> x;
        x ^= ans;
        auto it = prev(mp.lower_bound(x));
        split(it->first, next(it)->first, x);
        ans = *prev(ms.end());
    }
}

int main()
{
    ios;
    // freopen("sample.txt", "r", stdin);
    // freopen("resout.txt", "w", stdout);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7700kb

input:

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

output:

7 0 0 0 0
20 11 7 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2767ms
memory: 39352kb

input:

11116
10
10 5 10 3 6 4 8 5 9 8
31 27 24 11 12 3 0 2 3 1
10
8 2 7 2 8 10 1 10 9 10
6 5 2 13 2 1 0 1 3 1
10
7 10 7 6 1 3 10 6 7 9
21 18 10 1 6 5 4 8 9 10
10
2 10 4 8 8 5 7 2 6 7
20 10 9 1 15 0 4 2 9 7
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
6 3 5 2 7 10 9 1 4 8
10
1 10 1 3...

output:

21 18 16 12 10 6 4 1 1 0
12 12 10 10 4 4 4 2 1 0
20 16 9 5 3 3 3 0 0 0
22 14 8 8 5 5 2 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
19 12 7 4 4 2 2 1 0 0
20 18 8 3 1 1 0 0 0 0
45 21 21 10 3 3 3 0 0 0
17 11 8 2 1 1 1 0 0 0
13 4 1 0 0 0 0 0 0 0
29 27 22 15 9 7 4 3 1 0
26 16 9 2 1 1 1 1 1 0
0 0 0 0 0 ...

result:

ok 11116 lines

Extra Test:

score: 0
Extra Test Passed