HDU 6562 Lovers

发表于 | 分类于 |

CCPC 的神仙题……
显然可以想到维护位数，但是注意到下推标记的时候会有点问题，所以应该直接维护 \(10\) 的位数次幂之和。

似乎只维护一位的标记的话在合并标记的时候比较麻烦，所以标记应该是一个串和其反串。
把位数也维护成 \(10\) 的次幂的形式了。

即使这样还是很难写……
注意取模和细节。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 1e5;
const int mod = 1e9 + 7;
int T,n,m,pw[N + 5];
struct node
{
    int sum,pw;
    int tag_len,tag[2];
} seg[(N << 2) + 10];
void build(int p,int tl,int tr)
{
    seg[p].sum = 0,seg[p].tag_len = 1,seg[p].tag[0] = seg[p].tag[1] = 0;
    if(tl == tr)
    {
        seg[p].pw = 1;
        return ;
    }
    int mid = tl + tr >> 1;
    build(ls,tl,mid),build(rs,mid + 1,tr);
    seg[p].pw = (seg[ls].pw + seg[rs].pw) % mod;
}
inline void push(int p,int tl,int tr)
{
    if(seg[p].tag_len ^ 1)
    {
        int mid = tl + tr >> 1;
        seg[ls].pw = (long long)seg[ls].pw * seg[p].tag_len % mod,seg[ls].sum = ((long long)seg[ls].sum * seg[p].tag_len % mod + (long long)(mid - tl + 1) * seg[p].tag[1] % mod + (long long)seg[p].tag[0] * seg[ls].pw % mod) % mod,seg[ls].pw = (long long)seg[ls].pw * seg[p].tag_len % mod;
        seg[ls].tag[0] = (seg[ls].tag[0] + (long long)seg[p].tag[0] * seg[ls].tag_len % mod) % mod,seg[ls].tag[1] = ((long long)seg[ls].tag[1] * seg[p].tag_len % mod + seg[p].tag[1]) % mod,seg[ls].tag_len = (long long)seg[ls].tag_len * seg[p].tag_len % mod;
        seg[rs].pw = (long long)seg[rs].pw * seg[p].tag_len % mod,seg[rs].sum = ((long long)seg[rs].sum * seg[p].tag_len % mod + (long long)(tr - mid) * seg[p].tag[1] % mod + (long long)seg[p].tag[0] * seg[rs].pw % mod) % mod,seg[rs].pw = (long long)seg[rs].pw * seg[p].tag_len % mod;
        seg[rs].tag[0] = (seg[rs].tag[0] + (long long)seg[p].tag[0] * seg[rs].tag_len % mod) % mod,seg[rs].tag[1] = ((long long)seg[rs].tag[1] * seg[p].tag_len % mod + seg[p].tag[1]) % mod,seg[rs].tag_len = (long long)seg[rs].tag_len * seg[p].tag_len % mod;
        seg[p].tag_len = 1,seg[p].tag[0] = seg[p].tag[1] = 0;
    }
}
void update(int l,int r,int k,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        seg[p].pw = seg[p].pw * 10LL % mod,seg[p].sum = (seg[p].sum * 10LL % mod + (long long)(tr - tl + 1) * k % mod + (long long)seg[p].pw * k % mod) % mod,seg[p].pw = seg[p].pw * 10LL % mod;
        seg[p].tag[0] = (seg[p].tag[0] + (long long)seg[p].tag_len * k % mod) % mod,seg[p].tag[1] = (seg[p].tag[1] * 10LL % mod + k) % mod,seg[p].tag_len = seg[p].tag_len * 10LL % mod;
        return ;
    }
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,ls,tl,mid),1);
    r > mid && (update(l,r,k,rs,mid + 1,tr),1);
    seg[p].sum = (seg[ls].sum + seg[rs].sum) % mod,seg[p].pw = (seg[ls].pw + seg[rs].pw) % mod;
}
int query(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return seg[p].sum;
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    int ret = 0;
    l <= mid && (ret = (ret + query(l,r,ls,tl,mid)) % mod);
    r > mid && (ret = (ret + query(l,r,rs,mid + 1,tr)) % mod);
    return ret;
}
int main()
{
    scanf("%d",&T);
    for(register int cas = 0;T;--T)
    {
        printf("Case %d:\n",++cas),scanf("%d%d",&n,&m);
        build(1,1,n);
        char op[10];
        int l,r,d;
        for(;m;--m)
        {
            scanf("%s%d%d",op + 1,&l,&r);
            if(op[1] == 'w')
                scanf("%d",&d),update(l,r,d,1,1,n);
            else
                printf("%d\n",query(l,r,1,1,n));
        }
    }
}