QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#166969 | #7108. Couleur | ucup-team1113 | AC ✓ | 2767ms | 39352kb | C++20 | 4.4kb | 2023-09-06 21:58:18 | 2023-09-06 21:58:18 |
Judging History
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