#include <bits/stdc++.h>
#include "jngen.h"
using namespace std;
#define forn(i, n) for (int i = 0; i < n; ++i)

const int N = 100000;
bitset<N> a;

int count0(int l, int r) {
    int s = 0;
    for (int i = l; i < r; ++i) {
        s += a.test(i);
    }
    return s;
}

int count1(int l, int r) {
    return (a >> l).count() - (a >> r).count();
}

int count2(int l, int r) {
    int s = 0;
    const unsigned char* c = reinterpret_cast<const unsigned char*>(&a);
    if (l/8 == r/8) {
        return __builtin_popcount((c[l/8] & ((1 << (r%8)) - 1)) >> l%8);
    }
    s += __builtin_popcount(c[l/8] >> (l % 8));
    for (int i = l/8 + 1; i < r/8; ++i) {
        s += __builtin_popcount(c[i]);
    }
    s += __builtin_popcount((c[r/8] << (8 - r % 8)) & 0xff);
    return s;
}

int count3(int l, int r) {
    int s = 0;
    const unsigned int* c = reinterpret_cast<const unsigned int*>(&a);
    if (l/32 == r/32) {
        return __builtin_popcount((c[l/32] & ((1 << (r%32)) - 1)) >> l%32);
    }
    s += __builtin_popcount(c[l/32] >> (l % 32));
    for (int i = l/32 + 1; i < r/32; ++i) {
        s += __builtin_popcount(c[i]);
    }
    if (r%32 != 0) {
        s += __builtin_popcount((c[r/32] << (32 - r % 32)));
    }
    return s;
}

int main() {
    registerGen(0, nullptr);
    forn(i, N) a[i] = rnd.next(2);

    auto q = Arrayp::random(100000, 0, N, odpair);

    long long s1 = 0;
    {
        ContextTimer timer("naive");
        for (auto lr: q) s1 += count0(lr.first, lr.second);
    }

    long long s2 = 0;
    {
        ContextTimer timer("count");
        for (auto lr: q) s2 += count1(lr.first, lr.second);
    }

    long long s3 = 0;
    {
        ContextTimer timer("manual");
        for (auto lr: q) s3 += count2(lr.first, lr.second);
    }

    long long s4 = 0;
    {
        ContextTimer timer("manual_int");
        for (auto lr: q) s4 += count3(lr.first, lr.second);
    }

    assert(s1 == s2);
    assert(s2 == s3);
    assert(s2 == s4);
}