QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #161446 | #7108. Couleur | ucup-team987# | AC ✓ | 2313ms | 27560kb | C++20 | 6.5kb | 2023-09-02 23:58:02 | 2023-09-02 23:58:03 |
Judging History
answer
#include<iostream>
#include<set>
#include<cassert>
#include <cassert>
#include <vector>
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class T> struct fenwick_tree {
using U = internal::to_unsigned_t<T>;
public:
fenwick_tree() : _n(0) {}
explicit fenwick_tree(int n) : _n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += U(x);
p += p & -p;
}
}
T sum(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return sum(r) - sum(l);
}
private:
int _n;
std::vector<U> data;
U sum(int r) {
U s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
} // namespace atcoder
using namespace std;
#include<vector>
#include<algorithm>
template<typename T>
struct rangefreq{
int n;
vector<vector<T> >dat;
rangefreq(const vector<T>&v={})
{
n=1;
while(n<v.size())n<<=1;
dat.assign(2*n-1,{});
for(int i=0;i<v.size();i++)dat[i+n-1].push_back(v[i]);
for(int i=n-2;i>=0;i--)
{
dat[i].resize(dat[i*2+1].size()+dat[i*2+2].size());
merge(dat[i*2+1].begin(),dat[i*2+1].end(),
dat[i*2+2].begin(),dat[i*2+2].end(),
dat[i].begin()
);
}
}
int query(int a,int b,T x,int k=0,int l=0,int r=-1)const//[a,b) count(*<x)
{
if(r<0)r=n;
if(b<=l||r<=a)return 0;
else if(a<=l&&r<=b)return lower_bound(dat[k].begin(),dat[k].end(),x)-dat[k].begin();
else return query(a,b,x,k*2+1,l,(l+r)/2)+query(a,b,x,k*2+2,(l+r)/2,r);
}
};
int N;
int A[1<<17];
long long inv[1<<17];
long long first_inv()
{
atcoder::fenwick_tree<int>BIT(N);
long long ret=0;
for(int i=N;i--;)
{
ret+=BIT.sum(0,A[i]-1);
BIT.add(A[i]-1,1);
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
for(;T--;)
{
cin>>N;
for(int i=0;i<N;i++)cin>>A[i];
rangefreq seg(vector<int>(A,A+N));
auto low=[&seg](int l,int r,int x){return l==r?0:seg.query(l,r,x);};
auto upp=[&seg](int l,int r,int x){return l==r?0:(r-l)-seg.query(l,r,x+1);};
multiset<long long>ANS;
set<int>del;
del.insert(-1);
del.insert(N);
inv[0]=first_inv();
ANS.insert(inv[0]);
for(int i=0;i<N;i++)
{
long long z=*ANS.rbegin();
cout<<z<<(i+1==N?"\n":" ");
long long p;cin>>p;
p^=z;
p--;
auto it=del.lower_bound(p);
assert(0<=p&&p<N&&*it!=p);
int r=*it;
int l=*--it+1;
del.insert(p);
ANS.erase(ANS.find(inv[l]));
long long pre_inv=inv[l];
pre_inv-=upp(l,p,A[p]);
pre_inv-=low(p+1,r,A[p]);
long long Linv=0,Rinv=0;
if(p-l<r-p)
{
for(int i=l;i<p;i++)
{
pre_inv-=low(p+1,r,A[i]);
Linv+=low(i+1,p,A[i]);
}
Rinv=pre_inv-Linv;
}
else
{
for(int i=p+1;i<r;i++)
{
pre_inv-=upp(l,p,A[i]);
Rinv+=low(i+1,r,A[i]);
}
Linv=pre_inv-Rinv;
}
if(l<p)
{
inv[l]=Linv;
ANS.insert(Linv);
}
if(p+1<r)
{
inv[p+1]=Rinv;
ANS.insert(Rinv);
}
}
}
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3892kb
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: 2313ms
memory: 27560kb
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