#1171749 (C++17) No.3590 I Love Inversions

• 問題: No.3590 I Love Inversions
• ユーザー: ococonomy1
• 提出日時: 2026-07-17 21:27:17
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 2,125 ms / 5,000 ms
• コード長: 6,178 bytes
• コンパイル時間: 1,333 ms
• コンパイル使用メモリ: 217,732 KB
• 実行使用メモリ: 5,888 KB
• 平均クエリ数: 12103.46
• 最終ジャッジ日時: 2026-07-17 21:27:41
• 合計ジャッジ時間: 23,714 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 43

ソースコード

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
#define MOD 998244353
//#define MOD 1000000007
#define el '\n'
#define El '\n'
#define YESNO(x) ((x) ? "Yes" : "No")
#define YES YESNO(true)
#define NO YESNO(false)
#define EXIT_ANS(x) {cout << (x) << '\n'; return;}
template <typename T> void inline SORT(T &v){sort(v.begin(),v.end()); return;}
template <typename T> void inline REV(T &v){reverse(v.begin(),v.end()); return;}
template <typename T> void inline VEC_UNIQ(T &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return;}
template <typename T> auto inline MAX(T &v){return *max_element(v.begin(),v.end());}
template <typename T> auto inline MIN(T &v){return *min_element(v.begin(),v.end());}
template <typename T> auto inline SUM(vector<T> &v){T ans = 0; for(int i = 0; i < (int)v.size(); i++)ans += v[i]; return ans;}
template <typename T> void inline DEC(T &v){for(int i = 0; i < (int)v.size(); i++)v[i]--; return;}
template <typename T> void inline INC(T &v){for(int i = 0; i < (int)v.size(); i++)v[i]++; return;}
void inline TEST(void){cerr << "TEST" << endl; return;}
template <typename T,typename S> bool inline chmin(T &x,S y){
    if(x > (T)y){
        x = (T)y;
        return true;
    }
    return false;
}
template <typename T,typename S> bool inline chmax(T &x,S y){
    if(x < (T)y){
        x = (T)y;
        return true;
    }
    return false;
}
template <typename T = long long> vector<T> inline get_vec(int n){
    vector<T> ans(n);
    for(int i = 0; i < n; i++)cin >> ans[i];
    return ans;
}
template <typename T> void inline print_vec(vector<T> &vec,bool kaigyou = false){
    int n = (int)vec.size();
    for(int i = 0; i < n; i++){
        cout << vec[i];
        if(kaigyou || i == n - 1)cout << '\n';
        else cout << ' ';
    }
    if(!n)cout << '\n';
    return;
}
template <typename T> void inline debug_vec(vector<T> &vec,bool kaigyou = false){
    int n = (int)vec.size();
    for(int i = 0; i < n; i++){
        cerr << vec[i];
        if(kaigyou || i == n - 1)cerr << '\n';
        else cerr << ' ';
    }
    if(!n)cerr << '\n';
    return;
}
vector<vector<int>> inline get_graph(int n,int m = -1,bool direct = false,bool decrement = true){
    if(m == -1)m = n - 1;
    vector<vector<int>> g(n);
    while(m--){
        int u,v;
        cin >> u >> v;
        if(decrement)u--,v--;
        g[u].push_back(v);
        if(!direct)g[v].push_back(u);
    }
    return g;
}
template <typename T> vector<vector<pair<T,int>>> inline get_weighted_graph(int n,int m = -1,bool direct = false,bool decrement = true){
    if(m == -1)m = n - 1;
    vector<vector<pair<T,int>>> g(n);
    while(m--){
        int u,v;
        cin >> u >> v;
        if(decrement)u--,v--;
        ll w; cin >> w;
        g[u].push_back(pair(w,v));
        if(!direct)g[v].push_back(pair(w,u));
    }
    return g;
}

ll print_question(int l,int r){
    cout << "? ";
    cout << l +1 << ' ';
    cout << r + 1 << endl;
    ll x; cin >> x;
    return x;
}

void print_ans(vector<int> p){
    INC(p);
    cout << "! ";
    print_vec(p);
    cout << flush;
    return;
}

//フェネック木(BIT とも呼ばれるアレ) operator+, operator+=,operator- さえ定義できていればオンラインに区間和を取得できる。
//オーダーはセグ木と一緒だが、定数倍が圧倒的に良い。ほぼ定数。
template <typename T> class ococo_fenwicktree{
private:
    int n;
    vector<T> a;
public:

    //初め、全て0で埋まっている
    ococo_fenwicktree(int N){
        n = N + 1;
        a.resize(n);
        for(int i = 1; i < n; i++){
            a[i] = 0;
            int temp = i + 1;
            while(!(temp % 2)){
                temp /= 2;
            }
        }
    }

    void add_num(int i,T x){
        int idx = i + 1;
        while(idx < n){
            a[idx] += x;
            idx += (idx & -idx);
        }
    }

    //[0,r] の区間和を取得する。
    T get_sum(int r){
        if(r < 0)return 0;
        T ans = 0;
        int idx = r + 1;
        while(idx > 0){
            ans += a[idx];
            idx -= idx & -idx;
        }
        return ans;
    }

    T get_sum(int l,int r){
        T ans = get_sum(r);
        ans -= get_sum(l - 1);
        return ans;
    }

    void update_num(int i,T x){
        T val = get_sum(i) - get_sum(i - 1);
        T dif = x - val;
        add_num(i,dif);
        return;
    }
};


#define MULTI_TEST_CASE false
void solve(void){
    //問題を見たらまず「この問題設定から言えること」をいっぱい言う
    //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く
    //複数の解法のアイデアを思いついた時は全部メモしておく
    //g++ -D_GLIBCXX_DEBUG -Wall -O2 a.cpp -o o
    
    int n;
    cin >> n;
    ll prv_inv = 0;
    vector<ll> dif(n);
    for(int i = 1; i < n; i++){
        ll temp = print_question(0,i);
        dif[i] = temp - prv_inv;
        prv_inv = temp;
        //dif == 0 -> 今までで一番大きい数である
        //dif == 1 -> 今までで二番目に大きい数

        //dif == i -> 今までで一番小さい数
    }
    //debug_vec(dif);
    vector<int> ans(n);
    ococo_fenwicktree<int> BIT(n);
    for(int i = 0; i < n; i++)BIT.add_num(i,1);
    
    for(int i = n - 1; i >= 0; i--){
        //[0,x] に 1 が dif[i] 個ijouある、最小の x
        dif[i] = i - dif[i] + 1;
        int ok = n - 1,ng = -1;
        while(ok - ng >= 2){
            int mid = (ok + ng) / 2;
            if(BIT.get_sum(0,mid) >= dif[i])ok = mid;
            else ng = mid;
        }
        ans[i] = ok;
        BIT.update_num(ok,0);
    }
    print_ans(ans);
    

    return;
}

void calc(void){
    return;
}

signed main(void){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    calc();
    int t = 1;
    if(MULTI_TEST_CASE)cin >> t;
    while(t--){
        solve();
    }
    return 0;
}