E. Enigmatic Device @ NEERC 2009 Northern Subregional.

neerc-09-north-E.cpp

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int MOD = 2010;
const int MAX = 50011;
const int ITER = 12;
const int OFFSET = 2;

int n, a[MAX], tree[MAX << 2][ITER], carry[MAX << 2], curr[MAX << 2];

int inc(int x, int y) {
    int r = x + y;
    while (r >= ITER) r -= ITER - OFFSET;
    return r;
}

void build(int v, int l, int r) {
    if (l == r) {
        tree[v][0] = a[l];
        for (int k = 1; k < ITER; ++k)
            tree[v][k] = (1LL * tree[v][k - 1] * tree[v][k - 1]) % MOD;
    } else {
        int lt = v << 1, rt = lt | 1, mid = (l + r) >> 1;
        build(lt, l, mid);
        build(rt, mid + 1, r);
        for (int k = 0; k < ITER; ++k)
            tree[v][k] = (tree[lt][k] + tree[rt][k]) % MOD;
    }
}

void push(int v, int lt, int rt) {
    carry[lt] = inc(carry[lt], carry[v]);
    carry[rt] = inc(carry[rt], carry[v]);
    curr[lt] = inc(curr[lt], carry[v]);
    curr[rt] = inc(curr[rt], carry[v]);
    carry[v] = 0;
}

int query(int v, int l, int r, int i, int j) {
    if (l > j || r < i) return 0;
    if (l >= i && r <= j) return tree[v][curr[v]];
    int lt = v << 1, rt = lt | 1, mid = (l + r) >> 1;
    push(v, lt, rt);
    int r1 = query(lt, l, mid, i, j),
        r2 = query(rt, mid + 1, r, i, j);
    return (r1 + r2) % MOD;
}

int sum(int i, int j) { return query(1, 1, n, i, j); }

void update(int v, int l, int r, int i, int j) {
    if (l > j || r < i) return;
    if (l >= i && r <= j) {
        curr[v] = inc(curr[v], 1);
        carry[v] = inc(carry[v], 1);
    } else {
        int lt = v << 1, rt = lt | 1, mid = (l + r) >> 1;
        push(v, lt, rt);
        update(lt, l, mid, i, j);
        update(rt, mid + 1 ,r, i, j);
        for (int k = 0; k < ITER; ++k)
            tree[v][k] = (tree[lt][inc(curr[lt], k)] + tree[rt][inc(curr[rt], k)]) % MOD;
        curr[v] = 0;
    }
}

void square(int i, int j) { update(1, 1, n, i, j); }

int main() {
    int m, k, l, r;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    build(1, 1, n);
    scanf("%d", &m);
    while (m-- > 0) {
        scanf("%d%d%d", &k, &l, &r);
        if (k == 1) square(l, r);
        else printf("%d\n", sum(l, r));
    }
    return 0;
}