結果

問題 No.879 Range Mod 2 Query
ユーザー vwxyzvwxyz
提出日時 2024-04-11 01:58:50
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 293 ms / 3,000 ms
コード長 1,962 bytes
コンパイル時間 3,024 ms
コンパイル使用メモリ 258,108 KB
実行使用メモリ 15,488 KB
最終ジャッジ日時 2024-10-02 21:10:18
合計ジャッジ時間 6,954 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 4 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 4 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 3 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 272 ms
14,848 KB
testcase_12 AC 170 ms
14,848 KB
testcase_13 AC 214 ms
14,848 KB
testcase_14 AC 200 ms
15,360 KB
testcase_15 AC 194 ms
9,856 KB
testcase_16 AC 276 ms
15,360 KB
testcase_17 AC 289 ms
15,488 KB
testcase_18 AC 293 ms
15,360 KB
testcase_19 AC 267 ms
15,488 KB
testcase_20 AC 270 ms
15,488 KB
testcase_21 AC 285 ms
15,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <atcoder/lazysegtree>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;


struct S {
    long long s;
    long long ce;
    long long co;
};

struct F {
    long long p;
    long long d;
    long long x;
};

S op(S l, S r) {
	return S{l.s+r.s, l.ce+r.ce, l.co+r.co};
}

S e() {
	return S{0ll, 0ll, 0ll};
}

F composition(F l, F r) {
	if (l.d){
        return F({(r.p+r.x+l.p)%2,1ll,l.x});
	}
	else if (r.d){
        return F({r.p,1ll,r.x+l.x});
	}
    else{
        return F({0ll,0ll,r.x+l.x});
    }
}

S mapping(F l, S r) {
    long long s,ce,co;
    if (l.d){
        if(l.p){
            ce=r.co;
            co=r.ce;
        }
        else{
            ce=r.ce;
            co=r.co;
        }
        s=co+l.x*(ce+co);
        if(l.x%2){
            swap(ce,co);
        }
    }
    else{
        s=r.s+l.x*(r.ce+r.co);
        if(l.x%2){
            ce=r.co;
            co=r.ce;
        }
        else{
            ce=r.ce;
            co=r.co;            
        }
    }
    return S({s,ce,co});
}

F id() {
	return F({0ll, 0ll, 0ll});
}

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    vector<S> a(N);
    for(int i=0;i<N;i++){
        if(A[i]%2){
            a[i]=S({A[i],0ll,1ll});
        }
        else{
            a[i]=S({A[i],1ll,0ll});
        }
    }
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    for(int q=0;q<Q;q++){
    	int t,l,r;
    	long long x;
    	cin>>t;
        if(t==1){
            cin>>l>>r;
            l-=1;
            seg.apply(l,r,F({0ll,1ll,0ll}));
        }
        else if(t==2){
            cin>>l>>r>>x;
            l-=1;
            seg.apply(l,r,F({0ll,0ll,x}));
        }
    	else if(t==3){
            cin>>l>>r;
            l-=1;
	    	long long ans=seg.prod(l,r).s;
	    	cout<<ans<<endl;
        }
    }
    return 0;
}
0