12365. Jupiter Atacks! @ UVa Online Judge. (with Segment Tree)

UVA-12365-ST.cpp

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
#define MAX 100011

LL  B, P, L, N, st[4 * MAX], M[MAX];

void update(int v, int l, int r, int idx, LL val) {
    if (idx < l || idx > r) return;
    if (l == r) st[v] = val;
    else {
        int nl = v << 1, nr = nl + 1, mid = (l + r) / 2;
        if (idx <= mid) update(nl, l, mid, idx, val);
        else update(nr, mid + 1, r, idx, val);
        st[v] = (((M[r - mid]) * st[nl]) % P + st[nr]) % P;
    }
}

void update(int idx, LL val) {
    update(1, 0, L, idx, val);
}

LL query(int v, int l, int r, int i, int j) {
    if (i > r || j < l) return 0;
    if (l >= i && r <= j) return st[v];
    int nl = v << 1, nr = nl + 1, mid = (l + r) / 2;
    LL r1 = query(nl, l, mid, i, j),
       r2 = query(nr, mid + 1, r, i, j);
    if (j <= mid) return r1;
    else if (i > mid) return r2;
    else return (((M[min(r, j) - mid]) * r1) % P + r2) % P;
}

LL query(int i, int j) {
    return query(1, 0, L, i, j);
}

int main() {
    M[0] = 1;
    while (cin >> B >> P >> L >> N && N > 0) {
        memset(st, 0, sizeof(st));
        for (int i = 1; i < MAX; i++) {
            M[i] = (B * M[i - 1]) % P;
        }
        for (int i = 0; i < N; i++) {
            char C;
            cin >> C;
            if (C == 'E') {
                int I, V;
                cin >> I >> V;
                update(I, V);
            } else {
                int I, J;
                cin >> I >> J;
                cout << query(I, J) << endl;
            }
        }
        cout << "-" << endl;
    }
    return 0;
}