結果

問題 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;
}
0