結果

問題 No.1441 MErGe
ユーザー beetbeet
提出日時 2021-03-26 21:24:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 615 ms / 1,000 ms
コード長 7,146 bytes
コンパイル時間 2,460 ms
コンパイル使用メモリ 213,560 KB
実行使用メモリ 25,896 KB
最終ジャッジ日時 2024-11-28 21:24:17
合計ジャッジ時間 16,583 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 11 ms
5,248 KB
testcase_06 AC 11 ms
5,248 KB
testcase_07 AC 11 ms
5,248 KB
testcase_08 AC 115 ms
8,320 KB
testcase_09 AC 116 ms
7,936 KB
testcase_10 AC 207 ms
7,680 KB
testcase_11 AC 184 ms
6,784 KB
testcase_12 AC 208 ms
8,320 KB
testcase_13 AC 517 ms
24,576 KB
testcase_14 AC 525 ms
24,576 KB
testcase_15 AC 530 ms
23,552 KB
testcase_16 AC 506 ms
24,576 KB
testcase_17 AC 484 ms
23,808 KB
testcase_18 AC 300 ms
19,200 KB
testcase_19 AC 338 ms
22,144 KB
testcase_20 AC 261 ms
18,304 KB
testcase_21 AC 234 ms
15,872 KB
testcase_22 AC 345 ms
14,976 KB
testcase_23 AC 598 ms
25,856 KB
testcase_24 AC 603 ms
25,856 KB
testcase_25 AC 615 ms
25,728 KB
testcase_26 AC 601 ms
25,856 KB
testcase_27 AC 603 ms
25,728 KB
testcase_28 AC 523 ms
25,772 KB
testcase_29 AC 525 ms
25,896 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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(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;
}
0