codechef STRBIT - How to Repaint a Fence | http://www.codechef.com/problems/STRBIT

strbit.cc

#include <bits/stdc++.h>
using namespace std;
void print(const char* format, ...);
template <class number>
void input(number *ptr);

class SegmentTree
{
private:
    int _calc_size(int n) {
        int x = 1;
        while ((1 << x) < n)
            x++;
        return x;
    }
    void _rangeadd(int lo, int hi, int idx, int par){
        if(lo >= hi)
            return;
        tree[idx] += par;
        if (ra_hi <= lo or ra_lo >= hi)
            return;
        if (ra_lo <= lo and hi <= ra_hi) {
            tree[idx] += prop_val;
            return;
        }
        int mid = lo + ((hi - lo) / 2);
        _rangeadd(lo, mid, 2*idx + 1, tree[idx]);
        _rangeadd(mid, hi, 2*idx + 2, tree[idx]);
        tree[idx] = 0;
    }
    void _push_prop(int lo, int hi, int idx, int par) {
        if (lo >= hi)
            return;
        if (hi - lo == 1)  {
            tree[idx] += par;
            arr[lo] = tree[idx];
            tree[idx] = 0;
            return;
        }
        int mid = lo + ((hi - lo) / 2);
        _push_prop(lo, mid, 2*idx + 1, tree[idx] + par);
        _push_prop(mid, hi, 2*idx + 2, tree[idx] + par);
        tree[idx] = 0;
    }
    void _find(int lo, int hi, int idx, int par){
        if(lo >= hi)
            return;
        tree[idx] += par;
        if(hi <= query or lo > query)
            return;
        if(hi - lo == 1){
            arr[lo] += tree[idx];
            tree[idx] = 0;
            return;
        }
        int mid = lo + ((hi - lo) / 2);
        _find(lo, mid, 2*idx + 1, tree[idx]);
        _find(mid, hi, 2*idx + 2, tree[idx]);
        tree[idx] = 0;
    }
    vector<int> tree;
    int ra_lo;
    int prop_val;
    int ra_hi;
    int query;
public:
    vector<int> arr;
    SegmentTree(size_t n) {
        arr.resize(n);
        tree.resize((1 << (_calc_size(n) + 1)) + 1);
    }
    void rangeadd(int a, int b) {
        if(a == b)
            return;
        ra_lo = a;
        ra_hi = b;
        prop_val = 1;
        _rangeadd(0, arr.size(), 0, 0);
    }
    void push_prop() {
        _push_prop(0, arr.size(), 0, 0);
    }
    int find(int q) {
        query = q;
        _find(0, arr.size(), 0, 0);
        return arr[q];
    }
};

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        SegmentTree segt(n);
        int count = 0;
        for (int i = 0; i < n; ++i)
        {
            int tmp = 0;
            if (s[i] == 'R')
                tmp = 1;
            if(((tmp + segt.find(i)) % 2) == 0)
                continue;
            segt.rangeadd(i + 1, min(n, i + k));
            count += 1;
        }
        cout << count << '\n';
    }
    return 0;
}

strbit.py

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin
from math import log, ceil
import sys

class SegmentTree(object):
    def __init__(self, n):
        self.arr = [0] * n
        self.tree = [0] * (2*(pow(2, int(ceil(log(n, 2))))) - 1)

    def addrange(self, ra_lo, ra_hi, val):
        if ra_hi - ra_lo == 0:
            return
        tree = self.tree
        def _addrange(lo, hi, idx, par):
            if lo >= hi:
                return
            tree[idx] += par
            if ra_hi <= lo or ra_lo >= hi:
                return
            if ra_lo <= lo and hi <= ra_hi:
                tree[idx] += val
                return
            mid = lo + ((hi - lo) // 2)
            _addrange(lo, mid, 2*idx + 1, tree[idx])
            _addrange(mid, hi, 2*idx + 2, tree[idx])
            tree[idx] = 0
            return

        return _addrange(0, len(self.arr), 0, 0)

    def find(self, query):
        tree = self.tree
        arr = self.arr
        def _find(lo, hi, idx, par):
            if lo >= hi:
                return
            tree[idx] += par
            if hi <= query or lo > query:
                return
            if hi - lo == 1:
                arr[lo] += tree[idx]
                tree[idx] = 0
                return
            mid = lo + ((hi - lo) // 2)
            _find(lo, mid, 2*idx + 1, tree[idx])
            _find(mid, hi, 2*idx + 2, tree[idx])
            tree[idx] = 0
            return
        _find(0, len(arr), 0, 0)
        return arr[query]

def main():
    dstream = iter(sys.stdin.read().split())
    for _ in xrange(int(next(dstream))):
        n, k = int(next(dstream)), int(next(dstream))
        s = next(dstream)
        segt = SegmentTree(n)
        count = 0
        for i, chx in enumerate(s):
            if ((chx == 'R') + segt.find(i)) % 2 == 0:
                continue
            segt.addrange(i + 1, min(n, i + k), 1)
            count += 1
            # print i
        print count

main()

strbit.v2.py

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin
import sys

def main():
    dstream = iter(sys.stdin.read().split())
    for _ in xrange(int(next(dstream))):
        n, k = int(next(dstream)), int(next(dstream))
        s = next(dstream)
        updates = [0]*(n + 1)
        val, count = 0, 0
        for i, chx in enumerate(s):
            val += updates[i]
            if ((chx == 'R') + val) % 2 == 0:
                continue
            updates[min(n, i + k)] -= 1
            val += 1
            count += 1
        print count

main()