Spoj MULTQ3 Solution

Multiples of 3 : Solution

#include<bits/stdc++.h>

#define s start

#define e end

#define mx 100010

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

struct str

{

    int prop, zero, one, two;

};

int a[mx];

str tree[mx*3];

void swaps(int node)

{

    int value = tree[node].zero;

    tree[node].zero = tree[node].two;

    tree[node].two = tree[node].one;

    tree[node].one = value;

}

void initialize(int node, int s, int e)

{

    if(s == e)

    {

        tree[node].zero = 1;

        return;

    }

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    initialize(left, s, mid);

    initialize(right, mid+1, e);

    tree[node].zero = tree[left].zero + tree[right].zero;

}

void update(int node, int s, int e, int i, int j)

{

    if(i>e || j<s)

        return;

    if(s >= i && e <= j)

    {

        tree[node].prop += 1;

        tree[node].prop = tree[node].prop % 3;

        swaps(node);

        return;

    }

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    update(left, s, mid, i, j);

    update(right, mid+1, e, i, j);

    tree[node].zero = tree[left].zero + tree[right].zero;

    tree[node].one = tree[left].one + tree[right].one;

    tree[node].two = tree[left].two + tree[right].two;

    int cnt = tree[node].prop;

    while(cnt--)

        swaps(node);

}

int query(int node, int s, int e, int i, int j, int c=0)

{

    if(i>e || j<s)

        return 0;

    if(s >= i && e <= j)

    {

        if(c == 0)

            return tree[node].zero;

        else if(c == 1)

            return tree[node].two;

        else

            return tree[node].one;

    }

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    int r1 = query(left, s, mid, i, j, (c + tree[node].prop)%3);

    int r2 = query(right, mid+1, e, i, j, (c + tree[node].prop)%3);

    return (r1 + r2);

}

int main()

{

    fast

    int n, q, i, j, c;

    cin >> n >> q;

    initialize(1, 1, n);

    while(q--)

    {

        cin >> c >> i >> j;

        i++, j++;

        if(c == 0)

            update(1, 1, n, i, j);

        else

            cout << query(1, 1, n, i, j) << "\n";

    }

    return 0;

}