Mudanjiang2014-First-Round-E.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <cassert>
#include <cctype>
using namespace std;

typedef long long LL;

const int N = 200005;
const LL Q = 1e9 + 7;
int n , m ;
char str[N];

struct stree {
    stree () {
        s[0] = f[0] = s[1] = f[1] = 0;
    }
    LL s[2];
    LL f[2];
}t[N << 1];

inline int id(int l , int r) { return l + r | l != r; }
#define MID int mid = l + r >> 1
#define Left l , mid
#define Right mid + 1 , r

inline void add(LL& A , LL B) {
    assert(A >= 0);
    assert(B >= 0);
    B %= Q;
    A += B;
    if (A >= Q)
        A -= Q;
}
int len;
stree operator + (const stree& A , const stree& B) {
    stree res = A;
    if (len & 1) {
        add(res.s[0] , B.s[1]);
        add(res.s[1] , B.s[0]);
        add(res.f[0] , B.f[1]);
        add(res.f[1] , B.f[0]);
        add(res.f[0] , B.s[1] * (len + 1 >> 1));
        add(res.f[1] , B.s[0] * (len >> 1));
    } else {
        add(res.s[0] , B.s[0]);
        add(res.s[1] , B.s[1]);
        add(res.f[0] , B.f[0]);
        add(res.f[1] , B.f[1]);
        add(res.f[0] , B.s[0] * (len + 1 >> 1));
        add(res.f[1] , B.s[1] * (len >> 1));
    }
    return res;
}

void Build(int l , int r) {
    int p = id(l , r);
    if (l == r) {
        t[p].s[0] = str[l] - '0';
        t[p].s[1] = t[p].f[0] = t[p].f[1] = 0;
    } else {
        MID; Build(Left); Build(Right);
        len = mid - l + 1;
        t[p] = t[id(Left)] + t[id(Right)];
    }
}

void update(int l , int r , int x , int w) {
    int p = id(l , r);
    if (l == r) {
        t[p].s[0] = w;
        t[p].s[1] = t[p].f[0] = t[p].f[1] = 0;
        return;
    } MID;
    if (x <= mid)
        update(Left , x , w);
    else
        update(Right , x , w);
    len = mid - l + 1;
    t[p] = t[id(Left)] + t[id(Right)];
}

stree query(int l , int r , int top , int bot) {
    int p = id(l , r);
    if (top <= l && r <= bot)
        return t[p];
    MID;
    if (bot <= mid)
        return query(Left , top , bot);
    if (top > mid)
        return query(Right , top , bot);
    stree L = query(Left , top , mid);
    stree R = query(Right , mid + 1 , bot);
    len = mid - top + 1;
    return L + R;
}

void work() {
    int i , j , x , y;
    LL l , r;
    scanf("%s" , str);
    n = strlen(str);
    for (i = n ; i < n + n ; ++ i)
        str[i] = str[i - n];
    str[n + n] = 0;
    n <<= 1;
    Build(0 , n - 1);
    scanf("%d",&m);
    while (m --) {
        scanf("%d",&j);
        if (j == 1) {
            scanf("%d%d",&i ,&x) , -- i;
            str[i] = x + '0';
            str[i + n / 2] = x + '0';
            update(0 , n - 1 , i , x);
            update(0 , n - 1 , i + n / 2 , x);
        } else {
            scanf("%lld%lld",&l,&r);
            -- l , -- r;

            LL Len = (r - l + 1) % Q;
            x = l / n , y = r / n;
            LL sum = 0 , tot = 0 , num = 0;
            if (x == y) {
                stree T = query(0 , n - 1 , l % n , r % n);
                sum = T.s[0];
                tot = T.f[0];
            } else {
                stree TL = query(0 , n - 1 , l % n , n - 1);
                add(sum , TL.s[0]);
                add(tot , TL.f[0]) , num += n - (l % n);

                stree TM = t[id(0 , n - 1)];
                LL c = r / n - l / n - 1;
                if (c & 1) {
                    if (num & 1) {
                        add(sum , TM.s[1]);
                        add(tot , TM.f[1]);
                        add(tot , TM.s[1] * ((num + 1 >> 1) % Q));
                    } else {
                        add(sum , TM.s[0]);
                        add(tot , TM.f[0]);
                        add(tot , TM.s[0] * ((num >> 1) % Q));
                    }
                    num += n;
                    -- c;
                }
                LL C = c % Q;
                C = C * (C + Q - 1) % Q;
                C = C * 500000004 % Q;

                if (num & 1) {
                    add(sum , TM.s[1] * (c % Q));
                    add(tot , TM.f[1] * (c % Q));
                    LL pa = ((num + 1 >> 1) % Q) * c % Q ;
                    pa += C * (n / 2) % Q , pa %= Q;
                    add(tot , pa * TM.s[1]);
                } else {
                    add(sum , TM.s[0] * (c % Q));
                    add(tot , TM.f[0] * (c % Q));
                    LL pa = ((num >> 1) % Q) * c % Q;
                    pa += C * (n / 2) % Q , pa %= Q;
                    add(tot , pa * TM.s[0]);
                }
                num += n * c;

                stree TR = query(0 , n - 1 , 0 , r % n);
                if (num & 1) {
                    add(sum , TR.s[1]);
                    add(tot , TR.f[1]);
                    add(tot , TR.s[1] * ((num + 1 >> 1) % Q));
                } else {
                    add(sum , TR.s[0]);
                    add(tot , TR.f[0]);
                    add(tot , TR.s[0] * ((num + 1 >> 1) % Q));
                }
                num += r % n + 1;
                assert(num == r - l + 1);
            }
            LL res = (Q - tot * 2 % Q) % Q;
            add(res , sum * Len);
            printf("%d\n" , (int) res);
        }
    }
}

int main() {
    int _; scanf("%d",&_); while (_--)
        work();
    return 0;
}