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));
}
}
}