srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

Codeforces #197 Div2 D Xenia and Bit Operations

問題

問題概要

奇数回目に数列を左から隣同士を見て, ORを計算し, 偶数回目に数列を左から見て, XORを計算する. それぞれのステップで数列の要素数は半分になる. 数列の要素数が1になるまでこれを繰り返す.
はじめの数列がm回変化するので, m個の数列に対して要素数が1になるときの値を求める.

解法

奇数回目の計算はORで, 偶数回目はXORで計算しなければならないので, updata()関数で場合分けをして計算しなければならない. また, ORとXORの単位元は0なので, 初期値を0にして更新する. さらに, ORとXORは結合法則を満たすのでsegment treeのデータ構造を用いても問題ない. 以上のこと以外は, 通常のsegtreeと同じようにやればよい.

ミス

nは数列の数でないので注意.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define OUT(x) cout << #x << " = " << x << endl; 
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

template <class T> //T : dat[]の中身の型
class segtree{
public:
    int n;
    vector<T> dat;
    segtree(int n_): n(n_){ //n_要素数
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, 0); //(1) 単位元
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        k += n - 1; //葉の節点
        dat[k] = val;
        int cnt = 0;
        while(k > 0){
            k = (k - 1) / 2;
            if(cnt % 2)dat[k] = dat[k * 2 + 1] ^ dat[k * 2 + 2];
            else dat[k] = dat[k * 2 + 1] | dat[k * 2 + 2];
            cnt++;
        }
    }
};

int n, m;

int main(void){
    cin >> n >> m;
    segtree<int> seg(pow(2, n)); //大きさに注意
    rep(i, pow(2, n)){
        int a; cin >> a;
        seg.update(i, a);
    }
    
    rep(i, m){
        int p, b; cin >> p >> b;
        p--;
        seg.update(p, b);
        printf("%d\n", seg.dat[0]);
    }

    return 0;
}