結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2023-11-01 13:57:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 467 ms / 3,000 ms |
コード長 | 2,344 bytes |
コンパイル時間 | 1,100 ms |
コンパイル使用メモリ | 131,428 KB |
最終ジャッジ日時 | 2025-02-17 17:15:45 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cstring>#include<cassert>#include<cmath>#include<ctime>#include<iomanip>#include<numeric>#include<stack>#include<queue>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<bitset>#include<random>#include<functional>#include<utility>using namespace std;template<class T,T (*op)(T,T),T (*e)()> struct segtree{private:int size,N;vector<T> node;public:segtree(int N = 0) : segtree(vector<T>(N,e())) {}segtree(const vector<T> &V){N = (int)V.size();size = 1;while(size < N) size <<= 1;node.resize(2*size);for(int i = 0;i < N;i++) node[i+size] = V[i];for(int i = size-1;i >= 1;i--) node[i] = op(node[i*2],node[i*2+1]);}void replace(int pos,T x) {func_update(pos,x,[](T u,T v){return u = v;});}void add(int pos,T x) {func_update(pos,x,[](T u,T v){return u + v;});}void func_update(int pos,T x) {func_update(pos,x,op);}void func_update(int pos,T x,T (*func)(T,T)){assert(0 <= pos && pos < N);pos += size;node[pos] = func(node[pos],x);pos >>= 1;while(pos){node[pos] = op(node[pos*2],node[pos*2+1]);pos >>= 1;}}T operator[](int pos){assert(0 <= pos && pos < N);return node[pos+size];}T prod(int l,int r){assert(0 <= l && l <= r && r <= N);T L = e(),R = e();l += size,r += size;while(l < r){if(l & 1) L = op(L,node[l++]);if(r & 1) R = op(node[--r],R);l >>= 1,r >>= 1;}return op(L,R);}T prod() {return node[1];}};int op(int a,int b) {return a+b;}int e() {return 0;}int N,A[5 << 17];void solve(){cin >> N;vector<int> comp;for(int i = 0;i < N;i++) cin >> A[i],comp.push_back(A[i]);sort(comp.begin(),comp.end());comp.erase(unique(comp.begin(),comp.end()),comp.end());long long inv = 0;segtree<int,op,e> seg(comp.size());for(int i = 0;i < N;i++){int id = lower_bound(comp.begin(),comp.end(),A[i])-comp.begin();inv += seg.prod(id+1,comp.size());seg.add(id,1);}cout << inv << "\n";for(int i = 0;i+1 < N;i++){int id = lower_bound(comp.begin(),comp.end(),A[i])-comp.begin();inv -= seg.prod(0,id);inv += seg.prod(id+1,comp.size());cout << inv << "\n";}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;/* cin >> tt; */while(tt--) solve();}