H Lovers HDU 6565

题意： n 个字符串，m个操作，wrap操作在区间[l,r]的字符串前后各加一个数字,如3加入2112变成321123，一开始是个空字符串，值为0。query 查询[l,r]之间所有字符串的值的和模1e9+7。
题解： 把字符串分成三段 前缀+原本的值+后缀，前缀和后缀就是一个相反的，我直接把他处理成数字，然后记录长度，原本的值也是一样，保存值和长度。
然后线段树随便搞，lazy数组保存字符串加在前面的贡献，lazy2 后缀贡献,dat区间内添加一个数影响的总贡献，val区间和.
每次更新值：
val[k] =lazy[k]*dat[k] + val[k] * lenth(lazy[k]) + lazy2[k]
dat[k] = dat[k] * lenth(lazy[k])

具体见代码add()

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;
#define mid (l + r) / 2
#define chl 2 * k + 1
#define chr 2 * k + 2
#define lson l, mid, chl
#define rson mid + 1, r, chr
#define pb push_back
#define mem(a, b) memset(a, b, sizeof(a));


const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 1e6 + 5;
const int INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;
#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}


LL dat[maxn << 2], lazy[maxn << 2], val[maxn << 2], lazy2[maxn << 2];
LL p10[maxn];
int len[maxn << 2];

void up(int l, int r, int k) {
    val[k] = (val[chl] + val[chr]) % mod;
    dat[k] = (dat[chl] + dat[chr]) % mod;
    len[k] = 0;
    lazy2[k] = lazy[k] = 0;
}


void build(int l, int r, int k) {
    if (r == l) {
        dat[k] = 1;
        lazy2[k] = lazy[k] = 0;
        len[k] = 0;
        val[k] = 0;
    } else {
        build(lson);
        build(rson);
        up(l, r, k);
    }
}

LL re(LL x) {
    LL res = 0;
    while (x > 0) {
        res = res * 10 + x % 10 % mod;
        x /= 10;
    }
    return res;
}

void add(int l, int r, int k, LL x, LL y, int lenx) {
    if (r == l) {
        lazy2[k] = lazy[k] = 0;
        val[k] = (1LL * y % mod + val[k] * p10[lenx] % mod + dat[k] * p10[lenx] % mod * x % mod) % mod;
        dat[k] = dat[k] * p10[2 * lenx] % mod;
        return;
    }
    lazy[k] = (lazy[k] + x * p10[len[k]] % mod) % mod;
    lazy2[k] = (lazy2[k] * p10[lenx] % mod + y) % mod;
    len[k] += lenx;
    val[k] = (1LL * y * (r - l + 1) % mod + val[k] * p10[lenx] % mod + dat[k] * p10[lenx] % mod * x % mod) % mod;
    dat[k] = dat[k] * p10[2 * lenx] % mod;
}

void pushdown(int l, int r, int k) {
    if (len[k] == 0) {
        return;
    } else {
        add(lson, lazy[k], lazy2[k], len[k]);
        add(rson, lazy[k], lazy2[k], len[k]);
        up(l, r, k);
    }
}

int t;
int n, m;


void update(int a, int b, int l, int r, int k, int x) {
    pushdown(l, r, k);
    if (r < a || l > b)return;
    else if (a <= l && r <= b) {
        add(l, r, k, x, x, 1LL);
    } else {
        update(a, b, lson, x);
        update(a, b, rson, x);
        up(l, r, k);
    }
}

LL querry(int a, int b, int l, int r, int k) {
    pushdown(l, r, k);
    if (r < a || l > b)return 0;
    else if (a <= l && r <= b) {

// debug(val[k]);

        return val[k];

    } else {
        return (querry(a, b, lson) + querry(a, b, rson)) % mod;
    }
}

int main() {
    f();
    p10[0] = 1;
    for (int i = 1; i <= 400000; i++) {
        p10[i] = p10[i - 1] * 10 % mod;
    }
    int cas = 1;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        build(1, n, 0);
        printf("Case %d:\n", cas++);
        while (m--) {
            char s[10];
            int l, r;
            scanf("%s%d%d", s, &l, &r);
            if (s[0] == 'q') {
                LL ans = querry(l, r, 1, n, 0);
                printf("%lld\n", ans % mod);
            } else {
                int x;
                scanf("%d", &x);
                update(l, r, 1, n, 0, x);
// for (int i = 1; i <= n; i++) {
// printf("%lld ", querry(i, i, 1, n, 0));
// }
// puts("");
            }
        }
    }
    return 0;
}