結果

問題 No.2080 Simple Nim Query
コンテスト
ユーザー AngrySadEight
提出日時 2022-09-03 13:35:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 456 ms / 3,000 ms
コード長 2,274 bytes
コンパイル時間 734 ms
コンパイル使用メモリ 75,128 KB
最終ジャッジ日時 2025-02-07 02:14:37
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

struct BIT{
    int N;
    vector<ll> vec;
    BIT(int N_): N(N_), vec(N + 1){
        for (int i = 0; i < N + 1; i++){
            vec[i] = 0;
        }
    }
    
    void add(int p, ll x){
        for (int i = p; i <= N; i += (i & -i)){
            vec[i] += x;
        }
    }

    ll sum(int p){
        ll sum = 0;
        for (int i = p; i > 0; i -= (i & -i)){
            sum += vec[i];
        }
        return sum;
    }
};

int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    BIT bit(N);
    for (int i = 0; i < N; i++){
        if (A[i] == 1) bit.add(i + 1, 1);
    }
    for (int i = 0; i < Q; i++){
        int T;
        cin >> T;
        if (T == 1){
            int X, Y;
            cin >> X >> Y;
            if (A[X - 1] == 1 && Y != 1){
                bit.add(X, -1);
            }
            else if (A[X - 1] != 1 && Y == 1){
                bit.add(X, 1);
            }
            A[X - 1] = Y;
        }
        else{
            int X, Y;
            cin >> X >> Y;
            ll sumY = bit.sum(Y);
            ll sumX = bit.sum(X - 1);
            if (Y - X + 1 == sumY - sumX){
                if ((sumY - sumX) % 2 == 0){
                    cout << "S" << endl;
                }
                else{
                    cout << "F" << endl;
                }
            }
            else if (A[Y - 1] != 1){
                cout << "F" << endl;
            }
            else{
                //どこまで1であるかを二分探索
                int left = X - 1;
                int right = Y;
                while(right - left > 1){
                    int center = (left + right) / 2;
                    ll sumC = bit.sum(center);
                    if (Y - center == sumY - sumC){
                        right = center;
                    }
                    else{
                        left = center;
                    }
                }
                if ((Y - right) % 2 == 0){
                    cout << "F" << endl;
                }
                else{
                    cout << "S" << endl;
                }
            }
        }
    }
}
0