結果

問題 No.151 セグメントフィッシング
コンテスト
ユーザー latte0119
提出日時 2015-10-26 21:22:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 168 ms / 5,000 ms
コード長 2,468 bytes
コンパイル時間 2,032 ms
コンパイル使用メモリ 175,880 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-09-13 11:41:05
合計ジャッジ時間 4,479 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct RBST{
    struct node{
        node *lch,*rch;
        int val,sum,cnt;
        node(int val):val(val),sum(val),cnt(1),lch(NULL),rch(NULL){}
    };

    node *root;
    RBST():root(NULL){}

    inline int count(node *t){return t?t->cnt:0;}
    inline int sum(node *t){return t?t->sum:0;}

    node *update(node *t){
        if(!t)return t;
        t->cnt=count(t->lch)+count(t->rch)+1;
        t->sum=sum(t->lch)+sum(t->rch)+t->val;
        return t;
    }

    node *merge(node *a,node *b){
        if(!a)return b;
        if(!b)return a;
        if(rand()%(count(a)+count(b))<count(a)){
            a->rch=merge(a->rch,b);
            return update(a);
        }
        else{
            b->lch=merge(a,b->lch);
            return update(b);
        }
    }

    pair<node *,node *>split(node *t,int k){
        if(!t)return make_pair(t,t);
        if(k<=count(t->lch)){
            pair<node *,node *>s=split(t->lch,k);
            t->lch=s.second;
            return make_pair(s.first,update(t));
        }
        else{
            pair<node *,node *>s=split(t->rch,k-count(t->lch)-1);
            t->rch=s.first;
            return make_pair(update(t),s.second);
        }
    }
    void insert(int k,int x){
        pair<node *,node *>s=split(root,k);
        root=merge(merge(s.first,new node(x)),s.second);
    }
    int erase(int k){
        pair<node *,node *>s1,s2;
        int ret;
        s1=split(root,k);
        s2=split(s1.second,1);
        ret=s2.first->val;
        root=merge(s1.first,s2.second);
        return ret;
    }

    int sum(int l,int r){
        pair<node *,node *>s1,s2;
        int ret;
        s1=split(root,l);
        s2=split(s1.second,r-l);
        ret=s2.first->sum;
        root=merge(merge(s1.first,s2.first),s2.second);
        return ret;
    }
};

int N,Q;
RBST L,R;

signed main(){
    cin>>N>>Q;
    for(int i=0;i<N;i++){
        L.insert(i,0);
        R.insert(i,0);
    }

    while(Q--){
        char type;
        int x,y;
        cin>>type>>x>>y;
        if(type=='L'){
            int val=L.erase(x);
            L.insert(x,val+y);
        }
        else if(type=='R'){
            int val=R.erase(x);
            R.insert(x,val+y);
        }
        else{
            cout<<L.sum(x,y)+R.sum(x,y)<<endl;
        }
        int l=L.erase(0);
        int r=R.erase(N-1);
        L.insert(N-1,r);
        R.insert(0,l);
    }
    return 0;
}
0