結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー koyumeishi
提出日時 2015-06-11 04:58:58
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 268 ms / 5,000 ms
コード長 5,098 bytes
コンパイル時間 583 ms
コンパイル使用メモリ 78,680 KB
実行使用メモリ 27,844 KB
最終ジャッジ日時 2024-07-06 15:32:03
合計ジャッジ時間 2,643 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
template<class T=int>
class Segment_Tree_Lazy{
private:
    //default values are set in the constractor
    const T default_value;      //default (NULL) node value
    const T default_lazy_value; //default lazy value
    struct node{
        T value; T lazy_value;
        bool lazy; int lb; int ub;
        node* par; node* lch; node* rch;
        node(T default_value, T default_lazy_value) : 
            value(default_value),
            lazy_value(default_lazy_value),
            lazy(false),
            lb(0),ub(0),            //this node covers [lb, rb)
            par(NULL),lch(NULL),rch(NULL){
        }
    };
    T evaluate(T left_val, T right_val){    //evaluate node value
        return left_val + right_val;    //sum
        //return max(left_val, right_val);  //max
    }
    T evaluate_node_and_lazy(T node_val, T lazy_val){   //evaluate node value and lazy value
        return node_val + lazy_val; //sum
        //return max(node_val, lazy_val);   //max
        //return lazy_val;  //fill
    }
    T evaluate_lazy_and_lazy(T old_val, T new_val){ 
        //return old_val + new_val; //sum
        return new_val;     //fill
    }
    void new_lazy(node* t, T add_value){    
        if(t==NULL) return;
        if(t->lazy){
            t->lazy_value = evaluate_lazy_and_lazy(t->lazy_value, add_value);
        }else{
            t->lazy_value = add_value;
        }
        t->lazy = true;
        t->value = default_value;   //fill
    }
    T lazy_to_value(node* t){
        if(t->lazy) return t->lazy_value * (t->ub - t->lb); //sum
        return default_lazy_value;
    }
    T get_value(node* t){
        if(t==NULL) return default_value;
        return evaluate_node_and_lazy(t->value , lazy_to_value(t));
    }
    vector<node> v;
    node* root;
    int size;
    node* constract(node* t, int pos, int lb, int ub){
        if(pos == 0){
            t->par = t;
        }
        t->lb = lb;
        t->ub = ub;
        if(pos<size-1){
            t->lch = constract(&v[(pos<<1) + 1], (pos<<1) + 1, lb, (ub+lb)>>1);
            t->lch->par = t;
            t->rch = constract(&v[(pos<<1) + 2], (pos<<1) + 2, (ub+lb)>>1, ub);
            t->rch->par = t;
        }
        return t;
    }
    void initialize(int size_){
        size = 1;
        while(size < size_) size <<= 1;
        v = vector<node>(size<<1, node(default_value, default_lazy_value));
        root = constract(&v[0], 0, 0, size);
    }
    //propagate lazy value of node t to its children
    void push(node* t){
        if(t==NULL) return;
        if(t->lazy){
            if(t->lch != NULL){ //has child
                new_lazy(t->lch, t->lazy_value);
                new_lazy(t->rch, t->lazy_value);
                t->value = evaluate( get_value(t->lch), get_value(t->rch) );
            }else{
                t->value = get_value(t);
            }
            t->lazy_value = default_lazy_value;
            t->lazy = false;
        }
    }
    void range_add(int left, int right, T add_value, node* t){
        if(t==NULL) return;
        if(t->ub <= left || right <= t->lb){
            return;
        }
        push(t);
        if(left <= t->lb && t->ub <= right){
            new_lazy(t, add_value);
            return;
        }
        //partialy covered
        range_add(left, right, add_value, t->lch);
        range_add(left, right, add_value, t->rch);
        
        t->value = evaluate( get_value(t->lch), get_value(t->rch) );
    }
    //get value of [left,right)
    T get_range_value(int left, int right, node* t){
        if(t==NULL) return default_value;
        if(t->ub <= left || right <= t->lb){
            return default_value;
        }
        push(t);
        if(left <= t->lb && t->ub <= right){
            return get_value(t);
        }
        T L = get_range_value(left, right, t->lch);
        T R = get_range_value(left, right, t->rch);
        return evaluate(L, R);
    }
    void lazy_update(node* t){
        if(t->par != root){
            lazy_update(t->par);
        }
        push(t);
    }
public:
    //default node value must be set
    // sum : 0
    // max : MIN_INF
    // min : MAX_INF
    // gcd : 1
    Segment_Tree_Lazy(int size_, T default_value__ = 0, T default_lazy_value__ = 0) : 
        default_value(default_value__), default_lazy_value(default_lazy_value__){
        initialize(size_);
    }
    //node[pos] <= new_value
    void update(int pos, T new_value){
        node* t = &v[pos + size-1];
        
        lazy_update(t);
        t->value = new_value;
        while(t != root){
            t = t->par;
            t->value = evaluate( get_value(t->lch), get_value(t->rch) );
        }
    }
    //[l,r) += add_value
    void range_add(int left, int right, T add_value){
        range_add(left, right, add_value, root);
    }
    //get value [left,right)
    T get_range_value(int left, int right){
        return get_range_value(left, right, root);
    }
    void dbg(){
        for(int i=0; i<v.size(); i++){
            cerr << v[i].value << " ";
        }
        for(int i=0; i<v.size(); i++){
            cerr << v[i].lazy_value << " ";
        }
        cerr << endl;
    }
};
int main(){
    int n,q;
    cin >> n >> q;
    Segment_Tree_Lazy<int> a(n);
    Segment_Tree_Lazy<int> b(n);
    long long ans_a = 0;
    long long ans_b = 0;
    for(int i=0; i<q; i++){
        int x,l,r;
        cin >> x >> l >> r;
        if(x==0){
            int cnt_a = a.get_range_value(l,r+1);
            int cnt_b = b.get_range_value(l,r+1);
            if(cnt_a == cnt_b) continue;
            (cnt_a>cnt_b?ans_a:ans_b) += max(cnt_a, cnt_b);
        }else{
            a.range_add(l,r+1, x==1?1:0);
            b.range_add(l,r+1, x==1?0:1);
        }
    }
    int cnt_a = a.get_range_value(0,n);
    int cnt_b = b.get_range_value(0,n);
    ans_a += cnt_a;
    ans_b += cnt_b;
    cout << ans_a << " " << ans_b << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0