#1171762 (C++23) No.3590 I Love Inversions

• 問題: No.3590 I Love Inversions
• ユーザー: tau1235
• 提出日時: 2026-07-17 21:34:06
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 2,184 ms / 5,000 ms
• コード長: 6,583 bytes
• コンパイル時間: 2,327 ms
• コンパイル使用メモリ: 348,052 KB
• 実行使用メモリ: 50,944 KB
• 平均クエリ数: 12104.46
• 最終ジャッジ日時: 2026-07-17 21:34:32
• 合計ジャッジ時間: 25,818 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

#include<bits/stdc++.h>
using namespace std;

template<typename S,S (*op)(S,S),S (*e)(),typename F,S (*mapping)(F,S),F (*composition)(F,F),F (*id)()>
struct SplayTree{
  struct Node{
    S key,val,valrev;
    F lazy;
    int cnt;
    bool rev;
    bool has_lazy;
    Node *l,*r,*p;
    Node():key(e()),val(e()),valrev(e()),lazy(id()),cnt(1),rev(false),has_lazy(false),l(nullptr),r(nullptr),p(nullptr){}
  };
  Node* root;
  SplayTree():root(nullptr){}
  SplayTree(vector<S> &a){
    *this=SplayTree();
    int n=a.size();
    auto dfs=[&](auto dfs,Node* p,int l,int r)-> Node* {
      if (r-l<=0) return nullptr;
      int mid=(l+r)/2;
      Node* t=newNode(a[mid]);
      t->p=p;
      t->l=dfs(dfs,t,l,mid);
      t->r=dfs(dfs,t,mid+1,r);
      return update(t);
    };
    root=dfs(dfs,nullptr,0,n);
  }

private:
  inline static const int NODES=1e6;
  inline static Node pool[NODES];
  inline static int pid=0;
  Node* newNode(){
    assert(pid<NODES);
    pool[pid]=Node();
    return &pool[pid++];
  }
  Node* newNode(S val){
    Node* ret=newNode();
    ret->key=ret->val=ret->valrev=val;
    return ret;
  }
  int cnt(Node* t){return t?t->cnt:0;}
  S key(Node* t){return t?t->key:e();}
  S val(Node* t){return t?t->val:e();}
  S valrev(Node* t){return t?t->valrev:e();}
  Node* all_apply(Node* t,F f){
    if (!t) return t;
    t->key=mapping(f,t->key);
    t->val=mapping(f,t->val);
    t->valrev=mapping(f,t->valrev);
    t->lazy=composition(f,t->lazy);
    t->has_lazy=true;
    return t;
  }
  Node* all_reverse(Node* t){
    if (!t) return t;
    t->rev^=true;
    swap(t->val,t->valrev);
    swap(t->l,t->r);
    return t;
  }
  Node* update(Node* t){
    if (!t) return t;
    if (t->l){
      if (t->r){
        t->val=op(op(t->l->val,t->key),t->r->val);
        t->valrev=op(op(t->r->valrev,t->key),t->l->valrev);
        t->cnt=1+t->l->cnt+t->r->cnt;
      }
      else{
        t->val=op(t->l->val,t->key);
        t->valrev=op(t->key,t->l->valrev);
        t->cnt=1+t->l->cnt;
      }
    }
    else{
      if (t->r){
        t->val=op(t->key,t->r->val);
        t->valrev=op(t->r->valrev,t->key);
        t->cnt=1+t->r->cnt;
      }
      else{
        t->val=t->key;
        t->valrev=t->key;
        t->cnt=1;
      }
    }
    return t;
  }
  Node* push(Node* t){
    if (!t) return t;
    if (t->rev){
      all_reverse(t->l);
      all_reverse(t->r);
      t->rev=false;
    }
    if (t->has_lazy){
      all_apply(t->l,t->lazy);
      all_apply(t->r,t->lazy);
      t->lazy=id();
      t->has_lazy=false;
    }
    return t;
  }
  Node*& ppc(Node* p){
    if (p->p->l==p) return p->p->l;
    else return p->p->r;
  }
  void rotR(Node* t){
    assert(t->p);
    Node* p=t->p;
    t->p=p->p;
    if (p->p) ppc(p)=t;
    p->p=t;
    if (t->r) t->r->p=p;
    p->l=t->r;
    t->r=p;
  }
  void rotL(Node* t){
    assert(t->p);
    Node* p=t->p;
    t->p=p->p;
    if (p->p) ppc(p)=t;
    p->p=t;
    if (t->l) t->l->p=p;
    p->r=t->l;
    t->l=p;
  }
  void rotate(Node* t){
    assert(t->p);
    if (t->p->l==t) rotR(t);
    else rotL(t);
  }
  Node* splay(Node* t){
    push(t);
    while (t->p){
      Node* p=t->p;
      if (!p->p){
        rotate(t);
        update(p);
        update(t);
      }
      else{
        Node* pp=p->p;
        push(pp);
        push(p);
        push(t);
        if (p->l==t){
          if (pp->l==p) rotate(p),rotate(t);
          else rotate(t),rotate(t);
        }
        else{
          if (pp->r==p) rotate(p),rotate(t);
          else rotate(t),rotate(t);
        }
        update(pp);
        update(p);
        update(t);
      }
    }
    return update(t);
  }
  Node* find(Node* &t,int k){
    assert(0<=k&&k<cnt(t));
    while (true){
      push(t);
      if (cnt(t->l)==k) break;
      if (cnt(t->l)<k){
        k-=cnt(t->l)+1;
        t=t->r;
      }
      else t=t->l;
    }
    return splay(t);
  }
  Node* insert(Node* &t,int k,S val){
    assert(0<=k&&k<=cnt(t));
    Node* x=newNode(val);
    if (k==cnt(t)){
      x->l=t;
      if (t) t->p=x;
      return t=update(x);
    }
    Node* p=find(t,k);
    x->l=p->l;
    x->r=p;
    if (p->l) p->l->p=x;
    p->l=nullptr;
    p->p=x;
    update(p);
    return t=update(x);
  }
  Node* erase(Node* &t,int k){
    assert(0<=k&&k<cnt(t));
    Node* p=find(t,k);
    if (k==0){
      if (p->r) p->r->p=nullptr;
      return t=p->r;
    }
    if (k==cnt(p)-1){
      if (p->l) p->l->p=nullptr;
      return t=p->l;
    }
    p->r->p=nullptr;
    Node* r=find(p->r,0);
    r->l=p->l;
    p->l->p=r;
    return t=update(r);
  }
  Node* between(Node* &t,int l,int r){
    assert(0<=l&&l<=r&&r<=cnt(t));
    if (l==r) return nullptr;
    if (l==0&&r==cnt(t)) return t;
    if (l==0) return (t=splay(find(t,r)))->l;
    if (r==cnt(t)) return (t=splay(find(t,l-1)))->r;
    Node* pr=splay(find(t,r));
    pr->l->p=nullptr;
    Node* pl=splay(find(pr->l,l-1));
    pl->p=pr;
    pr->l=pl;
    t=update(pr);
    return pl->r;
  }
  Node* merge(Node* l,Node* r){
  }
  pair<Node*,Node*> split(Node* t,int k){
  }
  tuple<Node*,Node*,Node*> split(Node* t,int l,int r){
  }
  S get(Node* &t,int k){
    assert(0<=k&&k<cnt(t));
    find(t,k);
    return key(t);
  }
  S prod(Node* &t,int l,int r){
    assert(0<=l&&l<=r&&r<=cnt(t));
    return val(between(t,l,r));
  }
  Node* apply(Node* &t,int l,int r,F f){
    assert(0<=l&&l<=r&&r<=cnt(t));
    Node* p=between(t,l,r);
    if (!p) return t;
    all_apply(p,f);
    return t=splay(p);
  }
  Node* reverse(Node* &t,int l,int r){
    assert(0<=l&&l<=r&&r<=cnt(t));
    Node* p=between(t,l,r);
    if (!p) return t;
    all_reverse(p);
    return t=splay(p);
  }
public:
  void insert(int p,S x){insert(root,p,x);}
  void erase(int p){erase(root,p);}
  S get(int p){return get(root,p);}
  S prod(int l,int r){return prod(root,l,r);}
  void apply(int l,int r,F f){apply(root,l,r,f);}
  void reverse(int l,int r){reverse(root,l,r);}
  int size(){return cnt(root);}
};

int op(int a,int b){return 0;}
int e(){return 0;}
int mapping(int f,int x){return 0;}
int composition(int f,int g){return 0;}
int id(){return 0;}

int main(){
  using ll=long long;
  int n;
  cin>>n;
  auto query=[&](int l,int r){
    cout<<"? "<<l+1<<" "<<r<<endl;
    ll x;
    cin>>x;
    return x;
  };
  vector<ll> qs(n+1);
  qs[0]=0;
  for (int i=1;i<=n;i++) qs[i]=query(0,i);
  SplayTree<int,op,e,int,mapping,composition,id> st;
  for (int i=0;i<n;i++){
    ll x=qs[i+1]-qs[i];
    st.insert(i-x,i);
  }
  vector<int> ans(n);
  for (int i=0;i<n;i++) ans[st.get(i)]=i;
  cout<<"! ";
  for (int i=0;i<n;i++) cout<<ans[i]+1<<" \n"[i==n-1];
  cout<<flush;
}