結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2018-06-09 01:08:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,155 ms / 3,000 ms |
コード長 | 3,561 bytes |
コンパイル時間 | 1,874 ms |
コンパイル使用メモリ | 178,096 KB |
実行使用メモリ | 34,488 KB |
最終ジャッジ日時 | 2024-06-30 12:12:05 |
合計ジャッジ時間 | 10,312 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;#ifdef _DEBUG#define _GLIBCXX_DEBUG#include "dump.hpp"#else#define dump(...)#endif#define int long long// typedef __int128_t Int;#define DBG 1#define rep(i, a, b) for (int i = (a); i < (b); i++)#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)#define loop(n) rep(loop, (0), (n))#define all(c) begin(c), end(c)const int INF =sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;const int MOD = (int)(1e9) + 7;const double PI = acos(-1);const double EPS = 1e-9;template <class T> bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template <class T> bool chmin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}template <typename T> struct BinaryIndexedTree {// 1-indexedint n;vector<T> d;// d[x] が管理する区間の長さは,x の最も下の立っているビット(x&-x)BinaryIndexedTree(int m) : n(m) {// 0 以外の値で初期化をするとき// ・add を 𝑁 回呼び出せば 𝑂(𝑁 log 𝑁)// ・𝑣𝑥 = 1 で初期化するなら bit[x] = x & -x; (x&-x は区間の長さ)// ・一般には bit[x] を 𝑣𝑥 で初期化したのち// for (int x = 1; x < N; ++x) bit[x + (x & -x)] += bit[x];d.assign(m + 1, 0);}T sum(int a, int b) { return sum(b) - sum(a - 1); }T sum(int i) {// iから0にiの最も下の立っているbitを使って到達する最短距離// 次に足すべき区間は,番号から区間の長さを引くと求まるT ret(0);for (int j = i; j > 0; j -= j & (-j))ret += d[j];return ret;}void add(int i, T x) {// iからnにiの最も下の立っているbitを使って到達する最短距離// 次に更新すべき区間は,番号に区間の長さを足すと求まるfor (int j = i; j <= n; j += j & (-j))d[j] += x;}int lower_bound(T w) {// 二分木の分かれ方に従って二分探索する// 左の子に進むか右の子に進むかを知るためには,左の子の範囲の和がわかればよい// (index/2)// ちょうど BIT がもっている情報,𝑂(1) 時間で得られる//if (w <= 0)return 0;int x(0), y;for (y = 1; 2 * y <= n; y <<= 1);for (int k = y; k > 0; k >>= 1) {if (x + k <= n && d[x + k] < w) {w -= d[x + k];x += k;}}return x + 1;}};template <typename T> vector<T> compress(vector<T> &a) {// 座標圧縮vector<T> ret;ret.insert(ret.end(), all(a));sort(all(ret));ret.erase(unique(all(ret)), ret.end());rep(i, 0, a.size()) a[i] = distance(ret.begin(), lower_bound(all(ret), a[i]));return ret;}int theNunberOfInversion(vector<int> &a) {compress(a);BinaryIndexedTree<int> bit(a.size());int ans(0);rep(i, 0, a.size()) {ans += i - bit.sum(a[i]);bit.add(a[i], 1);}return ans;}signed main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(12);int N;cin >> N;vector<int> A(N);rep(i, 0, N) { cin >> A[i]; }rep(i, 0, N) A.push_back(A[i]);vector<int> v(2 * N);BinaryIndexedTree<int> bit(2 * N);compress(A);int ans = 0;rep(i, 0, N) {ans += i - bit.sum(A[i] + 1);bit.add(A[i] + 1, 1);}rep(i, 0, N) {cout<<ans<<endl;bit.add(A[i]+1,-1);ans-=bit.sum(A[i]);ans+=bit.sum(A[i]+2,N);bit.add(A[i]+1,1);}return 0;}