結果

問題 No.879 Range Mod 2 Query
ユーザー ningenMeningenMe
提出日時 2020-09-27 18:54:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 264 ms / 3,000 ms
コード長 8,028 bytes
コンパイル時間 2,209 ms
コンパイル使用メモリ 213,956 KB
実行使用メモリ 21,936 KB
最終ジャッジ日時 2024-06-30 12:51:34
合計ジャッジ時間 5,864 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 3 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 4 ms
6,944 KB
testcase_08 AC 4 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 249 ms
21,444 KB
testcase_12 AC 147 ms
21,452 KB
testcase_13 AC 191 ms
21,260 KB
testcase_14 AC 169 ms
21,768 KB
testcase_15 AC 177 ms
12,892 KB
testcase_16 AC 241 ms
21,788 KB
testcase_17 AC 254 ms
21,936 KB
testcase_18 AC 264 ms
21,700 KB
testcase_19 AC 239 ms
21,824 KB
testcase_20 AC 236 ms
21,828 KB
testcase_21 AC 257 ms
21,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

/*
 * @title LazySegmentTree - 非再帰抽象化遅延評価セグメント木
 * @docs md/segment/LazySegmentTree.md
 */
template<class Operator> class LazySegmentTree {
	using TypeNode = typename Operator::TypeNode;          
	using TypeLazy = typename Operator::TypeLazy;
	size_t num;      
	size_t length;                                   
	size_t height;                                   
	vector<TypeNode> node;                           
	vector<TypeLazy> lazy;                           
	vector<pair<size_t,size_t>> range;

	void propagate(int k) {
		if(lazy[k] == Operator::unit_lazy) return;
        node[k] = Operator::func_merge(node[k],lazy[k],range[k].first,range[k].second);
		if(k < length) lazy[2*k+0] = Operator::func_lazy(lazy[2*k+0],lazy[k]);
		if(k < length) lazy[2*k+1] = Operator::func_lazy(lazy[2*k+1],lazy[k]);
		lazy[k] = Operator::unit_lazy;
	}
public:

	//unitで初期化
	LazySegmentTree(const size_t num) : num(num) {
		for (length = 1,height = 0; length <= num; length *= 2, height++);
		node.resize(2 * length, Operator::unit_node);
		lazy.resize(2 * length, Operator::unit_lazy);
		for (int i = 0; i < num; ++i) node[i + length] = Operator::unit_node;
		for (int i = length - 1; i >= 0; --i) node[i] = Operator::func_node(node[(i<<1)+0],node[(i<<1)+1]);
		range.resize(2 * length);
		for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1);
		for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second);
	}

	// //同じinitで初期化
	LazySegmentTree(const size_t num, const TypeNode init) : num(num) {
		for (length = 1,height = 0; length <= num; length *= 2, height++);
		node.resize(2 * length, Operator::unit_node);
		lazy.resize(2 * length, Operator::unit_lazy);
		for (int i = 0; i < num; ++i) node[i + length] = init;
		for (int i = length - 1; i >= 0; --i) node[i] = Operator::func_node(node[(i<<1)+0],node[(i<<1)+1]);
		range.resize(2 * length);
		for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1);
		for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second);
	}

	//vectorで初期化
	LazySegmentTree(const vector<TypeNode>& vec) : num(vec.size()) {
		for (length = 1,height = 0; length <= vec.size(); length *= 2, height++);
		node.resize(2 * length, Operator::unit_node);
		lazy.resize(2 * length, Operator::unit_lazy);
		for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i];
		for (int i = length - 1; i >= 0; --i) node[i] = Operator::func_node(node[(i<<1)+0],node[(i<<1)+1]);
		range.resize(2 * length);
		for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1);
		for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second);
	}

	//update [a,b)
	void update(int a, int b, TypeLazy x) {
		int l = a + length, r = b + length - 1;
		for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i);
		for(r++; l < r; l >>=1, r >>=1) {
			if(l&1) lazy[l] = Operator::func_lazy(lazy[l],x), propagate(l),l++;
			if(r&1) --r,lazy[r] = Operator::func_lazy(lazy[r],x), propagate(r);
		}
		l = a + length, r = b + length - 1;
		while ((l>>=1),(r>>=1),l) {
            if(lazy[l] == Operator::unit_lazy) node[l] = Operator::func_node(Operator::func_merge(node[(l<<1)+0],lazy[(l<<1)+0],range[(l<<1)+0].first,range[(l<<1)+0].second),Operator::func_merge(node[(l<<1)+1],lazy[(l<<1)+1],range[(l<<1)+1].first,range[(l<<1)+1].second));
            if(lazy[r] == Operator::unit_lazy) node[r] = Operator::func_node(Operator::func_merge(node[(r<<1)+0],lazy[(r<<1)+0],range[(r<<1)+0].first,range[(r<<1)+0].second),Operator::func_merge(node[(r<<1)+1],lazy[(r<<1)+1],range[(r<<1)+1].first,range[(r<<1)+1].second));
  		}
	}

	//get [a,b)
	TypeNode get(int a, int b) {
		int l = a + length, r = b + length - 1;
		for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i);
		TypeNode vl = Operator::unit_node, vr = Operator::unit_node;
		for(r++; l < r; l >>=1, r >>=1) {
            if(l&1) vl = Operator::func_node(vl,Operator::func_merge(node[l],lazy[l],range[l].first,range[l].second)),l++;
            if(r&1) r--,vr = Operator::func_node(Operator::func_merge(node[r],lazy[r],range[r].first,range[r].second),vr);
 		}
		return Operator::func_node(vl,vr);
	}

	//return [0,length]
	int prefix_binary_search(TypeNode var) {
		int l = length, r = 2*length - 1;
		for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i);
		if(!Operator::func_check(node[1],var)) return num;
		TypeNode ret = Operator::unit_node;
		size_t idx = 2;
		for(; idx < 2*length; idx<<=1){
            if(!Operator::func_check(Operator::func_node(ret,Operator::func_merge(node[idx],lazy[idx],range[idx].first,range[idx].second)),var)) {
                ret = Operator::func_node(ret,Operator::func_merge(node[idx],lazy[idx],range[idx].first,range[idx].second));
                idx++;
            }
		}
		return min((idx>>1) - length,num);
	}

	//range[l,r) return [l,r]
	int binary_search(size_t l, size_t r, TypeNode var) {
		if (l < 0 || length <= l || r < 0 || length < r) return -1;
		for (int i = height; 0 < i; --i) propagate((l+length) >> i), propagate((r+length-1) >> i);
		TypeNode ret = Operator::unit_node;
		size_t off = l;
		for(size_t idx = l+length; idx < 2*length && off < r; ){
            if(range[idx].second<=r && !Operator::func_check(Operator::func_node(ret,Operator::func_merge(node[idx],lazy[idx],range[idx].first,range[idx].second)),var)) {
                ret = Operator::func_node(ret,Operator::func_merge(node[idx],lazy[idx],range[idx].first,range[idx].second));
                off = range[idx++].second;
                if(!(idx&1)) idx >>= 1;			
            }
            else{
				idx <<=1;
			}
		}
		return off;
	}

	void print(){
		// cout << "node" << endl;
		// for(int i = 1,j = 1; i < 2*length; ++i) {
		// 	cout << node[i][0] << ":" << node[i][1] << ":" << node[i][2] << ", ";
		// 	if(i==((1<<j)-1) && ++j) cout << endl;
		// }
		// cout << "lazy" << endl;
		// for(int i = 1,j = 1; i < 2*length; ++i) {
		// 	cout << lazy[i][0] << ":" << lazy[i][1] << ":" << lazy[i][2] << ", ";
		// 	if(i==((1<<j)-1) && ++j) cout << endl;
		// }
		// cout << "vector" << endl;
		cout << "{ " << get(0,1)[0] << ":" << get(0,1)[1] << ":" << get(0,1)[2];
		for(int i = 1; i < length; ++i) cout << ", " << get(i,i+1)[0] << ":" << get(i,i+1)[1] << ":" << get(i,i+1)[2];
		cout << " }" << endl;
	}
};

//node:総和　lazy:加算
template<class T, class U> struct NodeSumRangeMod2 {
	using TypeNode = T;
	using TypeLazy = U;
	inline static constexpr TypeNode unit_node = {0,0,0};
	inline static constexpr TypeLazy unit_lazy = {0,0,0};
	inline static constexpr TypeNode func_node(TypeNode l,TypeNode r){
        return {l[0]+r[0],l[1]+r[1],l[2]+r[2]};
    }
	inline static constexpr TypeLazy func_lazy(TypeLazy r,TypeLazy l){
		if (l[1] == 0) { r[2] += l[0] + l[2]; return r; }
		else           { l[0] += r[0] + r[2]; return l; }
    }
	inline static constexpr TypeNode func_merge(TypeNode r,TypeLazy l,int tl, int tr){
		if (l[0]&1) swap(r[1], r[2]);
		r = {r[0] + l[0]*(r[1] + r[2]),r[1],r[2]};
		if (l[1]) r[0]=r[1];
		if (l[2]&1) swap(r[1], r[2]);
		r = {r[0] + l[2]*(r[1] + r[2]),r[1],r[2]};
		return r;
    }
	inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var <= nodeVal;}
	// LazySegmentTree<NodeSumRangeUpdate<ll,ll>> Seg(N,0);
};

using t=array<ll,3>;
int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int N,Q; cin >> N >> Q;
    vector<t> s(N);
    for(int i=0;i<N;++i) {
		ll a; cin >> a;
		s[i]={a,(a&1),!(a&1)};
	}
    LazySegmentTree<NodeSumRangeMod2<t,t>> seg(s);
    while(Q--) {
        int q,l,r; cin >> q >> l >> r; l--;
        if(q==1) {
			t lazy={0,1,0};
			seg.update(l,r,lazy);
        }
		if(q==2) {
			ll x; cin >> x;
			t lazy={0,0,x};
			seg.update(l,r,lazy);
		}
		if(q==3) {
			cout << seg.get(l,r)[0] << endl;
		}
    }
    return 0;
}
0