Better and Faster!

You wake up with a pounding headache and only a hazy memory of a program your boss asked you to write. After you log in, you find the main routine you wrote yesterday:

unsigned int checksum (char str[], int len) {
    unsigned int r = 0;
    for (int k=0; k<8*len; k++) {               // iterate over the bits of str
        if ((r & (1<<31)) != 0) r = (r << 1) ^ 0x04c11db7;
                           else r = (r << 1);   // do some magic
        if (str[k/8] & 1<<(7-k%8))              // if the k-th bit of str is set,
            r ^= 1;                             // flip the last bit of r
    }
    return r;
}

You are proud of your comments, yet the "do some magic" part is still a little hard to follow. Even so, the function is named checksum, and — sure enough — it really does compute a kind of checksum of a given string, processing it one bit at a time.

Your task was to compute this checksum for a given string, and then for several slightly modified versions of it. The rest of your program looks reasonable too:

#include <stdio.h>

int main() {
    char str[1000001],c;
    int TESTS,n,changes,p;
    for (scanf ("%d", &TESTS); TESTS>0; TESTS--) {
        scanf ("%d %s", &n, str);               // read the input
        printf ("%u\n", checksum(str, n));      // checksum of the original string
        for (scanf ("%d", &changes); changes>0; changes--) {
            scanf ("%d %c", &p, &c);            // apply the change
            str[p-1] = c;
            printf ("%u\n", checksum(str, n));  // checksum of the modified string
        }
    }
}

The program is correct, but painfully slow, and you must make it run much faster. You even wrote an equivalent Java version (shown in the Hint), which somehow runs even slower.

The input contains several test cases. The first line contains a positive integer $Z \le 20$, the number of test cases. Then $Z$ test cases follow.

Here, a character means a single lowercase letter, uppercase letter, or digit.

The first line of each test case contains a natural number $n$ ($1 \le n \le 10^6$) and a string $s$, separated by a single space; $s$ consists of exactly $n$ characters. The next line contains an integer $t$ ($0 \le t \le 10^5$), the number of changes to apply to $s$. Each of the following $t$ lines contains a natural number $p \in [1, n]$ and a character $c$, separated by a single space, meaning that the $p$-th character of $s$ must be replaced by $c$.

Produce the same output the program above would. In other words, output $t + 1$ lines, each containing one checksum. The first checksum is computed for the original string $s$; each remaining checksum is computed after the corresponding change has been applied to $s$.

An equivalent Java version of the program (which runs even slower):

import java.util.Scanner;

public class Compute {

    static long checksum (byte[] str, int len) {
        int r = 0;
        for (int k=0; k<8*len; k++) {                  // iterate over the bits of str
            if ((r & (1<<31)) != 0) r = (r << 1) ^ 0x04c11db7;
            else r = (r << 1);                         // do some magic
            if ((str[k/8] & 1<<(7-k%8)) != 0)          // if the k-th bit of str is set,
                r ^= 1;                                // flip the last bit of r
        }
        long rr = (r<0 ? r+0x100000000L : r);          // Java has no unsigned int
        return rr;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int TESTS = in.nextInt(); TESTS>0; TESTS--) {
            int n = in.nextInt();                      // read the input
            byte[] str = in.next().getBytes();         // checksum of the
            System.out.println (checksum(str,n));      // original string
            for (int changes = in.nextInt(); changes>0; changes--) {
                int p = in.nextInt();                  // apply the change
                byte c = in.next().getBytes()[0];
                str[p-1] = c;
                System.out.println (checksum(str,n));  // checksum of the
            } // modified string
        }
    }
}