#634225 (C++17) No.1441 MErGe

• 問題: No.1441 MErGe
• ユーザー: beet
• 提出日時: 2021-03-26 21:25:03
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 587 ms / 1,000 ms
• コード長: 7,157 bytes
• コンパイル時間: 2,138 ms
• コンパイル使用メモリ: 205,392 KB
• 最終ジャッジ日時: 2025-01-19 21:51:42
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 28

ソースコード

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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}


template<typename Impl, typename Data, typename Node, size_t LIM>
struct RBST{
  using u32 = uint32_t;
  u32 xor128(){
    static u32 x = 123456789;
    static u32 y = 362436069;
    static u32 z = 521288629;
    static u32 w = 88675123;

    u32 t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  }

  alignas(Node) static inline char pool[sizeof(Node)*LIM];
  static inline Node* ptr = (Node*)pool;
  static inline size_t size;

  template<typename... Args>
  inline Node* create(Args&&... args){
    return new (ptr+size++) Node(std::forward<Args>(args)...);
  }

  inline size_t count(const Node *t){return Data::count(t);}

  inline Node* touch(Node *t){
    return static_cast<Impl*>(this)->touch(t);
  }

  inline void toggle(Node *t){
    return static_cast<Impl*>(this)->toggle(t);
  }

  inline Node* pushup(Node *t){
    return static_cast<Impl*>(this)->pushup(t);
  }

  Node* toggle(Node *a,size_t l,size_t r){
    auto s=split(a,l);
    auto t=split(s.second,r-l);
    auto u=touch(t.first);
    toggle(u);
    return merge(s.first,merge(u,t.second));
  }

  Node* merge(Node* a,Node* b){
    if(a==nullptr) return b;
    if(b==nullptr) return a;
    if(xor128()%(count(a)+count(b))<count(a)){
      a=touch(a);
      a->r=merge(a->r,b);
      a->r->p=a;
      return pushup(a);
    }
    b=touch(b);
    b->l=merge(a,b->l);
    b->l->p=b;
    return pushup(b);
  }

  pair<Node*, Node*> split(Node* a,size_t k){
    if(a==nullptr) return make_pair(a,a);
    a=touch(a);
    if(k<=count(a->l)){
      if(a->l) a->l->p=nullptr;
      auto s=split(a->l,k);
      a->l=s.second;
      if(a->l) a->l->p=a;
      return make_pair(s.first,pushup(a));
    }
    if(a->r) a->r->p=nullptr;
    auto s=split(a->r,k-(count(a->l)+1));
    a->r=s.first;
    if(a->r) a->r->p=a;
    return make_pair(pushup(a),s.second);
  }

  Node* insert(Node *a,size_t k,Node v){
    Node* b=create(v);
    auto s=split(a,k);
    return merge(merge(s.first,b),s.second);
  }

  Node* erase(Node *a,size_t k){
    assert(k<count(a));
    auto s=split(a,k);
    auto t=split(s.second,1);
    return merge(s.first,t.second);
  }

  Node* find_by_order(Node *a,size_t k){
    assert(k<count(a));
    a=touch(a);
    size_t num=count(a->l);
    if(k<num) return find_by_order(a->l,k);
    if(k>num) return find_by_order(a->r,k-(num+1));
    return a;
  }

  inline bool is_right(Node* a){
    return a->p and a->p->r==a;
  }

  size_t order_of_key(Node* a){
    size_t res=count(a->l);
    while(a){
      if(is_right(a)) res+=count(a->p->l)+1;
      a=a->p;
    }
    return res;
  }

  Node* build(size_t l,size_t r,const vector<Node> &vs){
    if(l+1==r) return create(vs[l]);
    size_t m=(l+r)>>1;
    return merge(build(l,m,vs),build(m,r,vs));
  }

  Node* build(const vector<Node> &vs){
    return build(0,vs.size(),vs);
  }

  template<typename T>
  Node* set_val(Node *a,size_t k,T val){
    assert(k<count(a));
    a=touch(a);
    size_t num=count(a->l);
    if(k<num) a->l=set_val(a->l,k,val);
    if(k>num) a->r=set_val(a->r,k-(num+1),val);
    if(k==num) a->val=val;
    return pushup(a);
  }

  Node* get_val(Node *a,size_t k){
    assert(k<count(a));
    a=touch(a);
    size_t num=count(a->l);
    if(k<num) return get_val(a->l,k);
    if(k>num) return get_val(a->r,k-(num+1));
    return a;
  }

  template<typename E>
  Node* update(Node *a,size_t l,size_t r,E v){
    auto s=split(a,l);
    auto t=split(s.second,r-l);
    auto u=touch(t.first);
    static_cast<Impl*>(this)->propagate(u,v);
    return merge(s.first,merge(u,t.second));
  }

  decltype(auto) query(Node *&a,size_t l,size_t r){
    auto s=split(a,l);
    auto t=split(s.second,r-l);
    auto u=t.first;
    auto res=static_cast<Impl*>(this)->query(u);
    a=merge(s.first,merge(u,t.second));
    return res;
  }
};


template<typename T, typename F, typename Flip>
struct Ushi{
  F f;
  Flip flip;
  T ti;

  Ushi(F f,Flip flip,T ti):f(f),flip(flip),ti(ti){}

  struct Node{
    Node *l,*r,*p;
    size_t cnt;
    bool rev;
    T val,dat;
    Node(T val):
      cnt(1),rev(0),val(val),dat(val){l=r=p=nullptr;}
  };

  static inline size_t count(const Node *t){
    return t?t->cnt:0;
  }

  inline void toggle(Node *t){
    swap(t->l,t->r);
    t->val=flip(t->val);
    t->dat=flip(t->dat);
    t->rev^=1;
  }

  inline bool dirty(Node *t){
    return t->rev;
  }

  inline Node* eval(Node* t){
    if(t->rev){
      if(t->l) toggle(t->l);
      if(t->r) toggle(t->r);
      t->rev=false;
    }
    return t;
  }

  inline Node* pushup(Node *t){
    t->cnt=count(t->l)+1+count(t->r);
    t->dat=t->val;
    if(t->l) t->dat=f(t->l->dat,t->dat);
    if(t->r) t->dat=f(t->dat,t->r->dat);
    return t;
  }

  inline T get_val(Node *t){
    assert(t);
    return t->val;
  }

  inline T reflect(Node *t){
    assert(t);
    return t->dat;
  }

  void dump(typename vector<Node>::iterator it,Node* const t,bool rev){
    if(!count(t)) return;

    Node *l=t->l,*r=t->r;
    if(rev) swap(l,r);
    rev^=t->rev;

    dump(it,l,rev);
    *(it+count(l))=Node(t->val);
    dump(it+count(l)+1,r,rev);
  }

  vector<Node> dump(Node* t){
    assert(t!=nullptr);
    vector<Node> vs(count(t),*t);
    dump(vs.begin(),t,false);
    return vs;
  }
};



template<typename Data, size_t LIM>
struct Basic : RBST<Basic<Data, LIM>, Data, typename Data::Node, LIM>{
  using super = RBST<Basic, Data, typename Data::Node, LIM>;
  using Node = typename Data::Node;

  Data data;

  template<class... Args>
  Basic(Args... args):data(forward<Args>(args)...){}

  inline Node* touch(Node *t){return data.eval(t);}

  using super::toggle;
  inline void toggle(Node *t){return data.toggle(t);}
  template<typename E>
  inline void propagate(Node *t,E x){return data.propagate(t,x);}
  inline Node* pushup(Node *t){return data.pushup(t);}

  inline decltype(auto) get_val(Node *a,size_t k){
    return data.get_val(super::get_val(a,k));
  }

  using super::query;
  inline decltype(auto) query(Node *a){
    return data.reflect(a);
  }
};

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,q;
  cin>>n>>q;
  auto as=read<long long>(n);

  using ll = long long;
  auto f=[&](ll a,ll b){return a+b;};
  auto flip=[&](ll a){return a;};
  using Data = Ushi<ll, decltype(f), decltype(flip)>;
  using Node = Data::Node;
  const size_t LIM = 3e6;
  Basic<Data, LIM> G(f,flip,0);

  auto A=G.build(vector<Node>(as.begin(),as.end()));


  for(int i=0;i<q;i++){
    int t,l,r;
    cin>>t>>l>>r;
    l--;
    ll sum=G.query(A,l,r);
    if(t==1){
      auto [x,y]=G.split(A,r);
      auto [p,q]=G.split(x,l);
      A=G.merge(G.merge(p,G.create(sum)),y);
    }
    if(t==2) cout<<sum<<newl;
  }
  return 0;
}