CF Round #197 Div.2 D. Xenia and Bit Operations

Codeforces Round #197 Div.2 D. Xenia and Bit Operations

Problem - D - Codeforces

2のn乗個の数列に対して、
奇数番目の数とその次の数同士のorをとって数列をつくる
奇数番目の数とその次の数同士のxorをとって数列をつくる
という操作を数が1個になるまで交互に繰り返す。p番目をbに変えていく、というクエリが与えられるのでそれを順次行なったあとの、最後に残る1個の数をクエリごとに答える問題。セグメントツリーの更新部分を少しいじって実装すればよい。すなわち、2つの子ノードのorまたはxorをとったものを親ノードとして更新する、という操作を繰り返していけば良い。セグメントツリーの問題を解いたのは初めてだったので、「セグメントツリー」でググって見つけたライブラリみたいなものをコピペして、てきとーにごにょごにょ書き換えたら15分ほどであっさり通せた。使いやすい自分なりのライブラリを作りたい。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.14159265358979;

//#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; scanf("%d", &_x); return _x; }
long long lin() {long long _x; scanf("%lld", &_x); return _x; };

#define MAX (2 << 17)

struct Segtree {
        int N, dat[2 * MAX];
        Segtree(int n) {
                N = 1;
                while (N < n) N *= 2;
                for (int i = 0; i < 2 * N - 1; i++) dat[i] = INF;
        }
        void update(int k, int a) {
                bool f = true;//最初はorをとる
                k += N - 1;
                dat[k] = a;
                while (k > 0) {
                        k = (k - 1) / 2;
                        if (f) dat[k] = dat[k * 2 + 1] | dat[k * 2 + 2];
                        else dat[k] = dat[k * 2 + 1] ^ dat[k * 2 + 2];
                        f ^= 1;//交互に操作する
                }
        }
};

signed main() { 
        int n, q;
        cin >> n >> q;
        Segtree tree(1 << n);
        rep(i, 1 << n) {
                int a;
                cin >> a;
                tree.update(i, a);
        }           
        while (q --) {
                int p, b;
                cin >> p >> b;
                tree.update(p - 1, b);
                cout << tree.dat[0] << endl;
        }
        return 0;
}               

セグメントツリーの問題をこれからじわじわ解いていく。