QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#157796 | #7108. Couleur | ucup-team180# | AC ✓ | 1414ms | 22192kb | C++14 | 3.6kb | 2023-09-02 15:51:45 | 2023-09-02 15:51:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct binary_indexed_tree{
int N;
vector<int> BIT;
binary_indexed_tree(){
}
binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
}
void add(int i, int x){
i++;
while (i <= N){
BIT[i] += x;
i += i & -i;
}
}
int sum(int i){
int ans = 0;
while (i > 0){
ans += BIT[i];
i -= i & -i;
}
return ans;
}
int sum(int L, int R){
return sum(R) - sum(L);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int i = 0; i < T; i++){
int n;
cin >> n;
vector<int> a(n);
for (int j = 0; j < n; j++){
cin >> a[j];
a[j]--;
}
vector<long long> inv(n, 0);
vector<vector<int>> num(n);
vector<binary_indexed_tree> BIT(n);
set<pair<int, int>> st1;
multiset<long long> st2;
auto compress = [&](int l, int r){
vector<int> b;
for (int j = l; j < r; j++){
b.push_back(a[j]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int j = l; j < r; j++){
a[j] = lower_bound(b.begin(), b.end(), a[j]) - b.begin();
}
return b;
};
st1.insert(make_pair(0, n));
num[0] = compress(0, n);
int m = num[0].size();
BIT[0] = binary_indexed_tree(m);
for (int j = 0; j < n; j++){
inv[0] += BIT[0].sum(a[j] + 1, m);
BIT[0].add(a[j], 1);
}
st2.insert(0);
st2.insert(inv[0]);
long long z;
for (int j = 0; j < n; j++){
z = *prev(st2.end());
cout << z;
if (j < n - 1){
cout << ' ';
}
long long p;
cin >> p;
p ^= z;
p--;
auto itr = prev(st1.lower_bound(make_pair(p + 1, 0)));
int L = (*itr).first;
int R = (*itr).second;
st1.erase(make_pair(L, R));
st1.insert(make_pair(L, p));
st1.insert(make_pair(p + 1, R));
st2.erase(st2.find(inv[L]));
if (p - L < R - 1 - p){
swap(inv[L], inv[p + 1]);
swap(num[L], num[p + 1]);
swap(BIT[L], BIT[p + 1]);
for (int k = L; k <= p; k++){
BIT[p + 1].add(a[k], -1);
}
for (int k = L; k <= p; k++){
inv[p + 1] -= BIT[p + 1].sum(a[k]);
}
if (L < p){
for (int k = L; k < p; k++){
if (a[k] > a[p]){
inv[p + 1]--;
}
}
num[L] = compress(L, p);
m = num[L].size();
BIT[L] = binary_indexed_tree(m);
for (int k = L; k < p; k++){
inv[L] += BIT[L].sum(a[k] + 1, m);
BIT[L].add(a[k], 1);
}
inv[p + 1] -= inv[L];
st2.insert(inv[L]);
}
st2.insert(inv[p + 1]);
} else {
for (int k = p; k < R; k++){
BIT[L].add(a[k], -1);
}
for (int k = p; k < R; k++){
inv[L] -= BIT[L].sum(a[k] + 1, num[L].size());
}
if (p + 1 < R){
for (int k = p + 1; k < R; k++){
if (a[p] > a[k]){
inv[L]--;
}
}
num[p + 1] = compress(p + 1, R);
m = num[p + 1].size();
BIT[p + 1] = binary_indexed_tree(m);
for (int k = p + 1; k < R; k++){
inv[p + 1] += BIT[p + 1].sum(a[k] + 1, m);
BIT[p + 1].add(a[k], 1);
}
inv[L] -= inv[p + 1];
st2.insert(inv[p + 1]);
}
if (L < p){
st2.insert(inv[L]);
}
}
}
cout << '\n';
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
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: 1414ms
memory: 22192kb
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