admin 管理员组文章数量: 1087819
2018CCPC吉林赛区 H Lovers(线段树)
题意：
有n个字符串，一开始都是空串，两种操作：
操作一：wrap l r d（d为0~9的数字）： 把区间 [l, r] 的每个字符串Si 变成字符串d Si d, 也就是在每个字符串的头尾都加上数字d。
操作二：query l r ：把每个字符串都看成一个数字，求区间[l, r]的和。
题解：
对于一个长度为t的字符串，假设它原本的值为v，那么它进行完操作一之后，它的值会变为 d * 10^(t + 1) + v*10 + d。这样可以简单的维护区间和。这个公式是在d为一位数的情况下推的，但是我们要用线段树懒标记去维护d，也就是说d会积累，所以对于单个字符串，公式变成：v = (d的镜像) *10^(t+len[d]) + v * len[d] + d。
区间统计的时候，只要统计区间内 (10^t)的和 和 v的和 就可以更新当前区间的信息。
又因为d的累加在字符串的前面和后面，所以分别统计d和d的镜像（后缀和前缀）。
所以有五个信息要统计：
- 10^t的和
- 当前积累的d的长度len[d]
- 前缀d的值
- 后缀d的值
- 当前区间字符串的值的总和。
2，3，4都是懒标记
这题的难点是要想清楚如何更新当前区间的各个信息，并把它们建立联系。
题目链接
ac代码：
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define ll long long
using namespace std;
const int maxn = 1e5 + 50;
const ll mod = 1e9 + 7;
ll sum[maxn<<2], pos[maxn<<2], len[maxn<<2], head[maxn<<2], tail[maxn<<2];
int n, m;
void up(int rt)
{sum[rt] = (sum[rt<<1] + sum[rt<<1|1])%mod;pos[rt] = (pos[rt<<1] + pos[rt<<1|1])%mod;return;
}
void build(int rt, int l, int r)
{sum[rt] = head[rt] = tail[rt] = 0;len[rt] = pos[rt] = 1;if(l == r) return;build(lson);build(rson);up(rt);
}
void down(int rt, int l, int r)
{if(len[rt] == 1) return;sum[rt<<1] = head[rt]*pos[rt<<1] % mod * len[rt] % mod + sum[rt<<1] * len[rt]%mod + (mid - l + 1)*tail[rt]%mod;sum[rt<<1] %= mod;head[rt<<1] = (head[rt]*len[rt<<1] + head[rt<<1])%mod;tail[rt<<1] = (tail[rt<<1]*len[rt] + tail[rt]) % mod;len[rt<<1] = len[rt<<1] * len[rt] %mod;pos[rt<<1] = pos[rt<<1]*len[rt] % mod * len[rt] % mod;sum[rt<<1|1] = head[rt]*pos[rt<<1|1] % mod * len[rt] % mod + sum[rt<<1|1] * len[rt] %mod + (r-mid)*tail[rt]%mod;sum[rt<<1|1] %= mod;head[rt<<1|1] = (head[rt] * len[rt<<1|1] + head[rt<<1|1]) %mod;tail[rt<<1|1] = (tail[rt<<1|1]*len[rt] + tail[rt]) % mod;len[rt<<1|1] = len[rt<<1|1] * len[rt] % mod;pos[rt<<1|1] = pos[rt<<1|1] * len[rt] % mod * len[rt] % mod;head[rt] = tail[rt] = 0;len[rt] = 1;return;
}
void update(int rt, int l, int r, int L, int R, ll d)
{if(L <= l && r <= R){sum[rt] = d*pos[rt] % mod * 10 % mod + sum[rt] * 10 % mod + d*(r - l + 1) % mod;sum[rt] %= mod;head[rt] = (d * len[rt] + head[rt]) % mod;tail[rt] = (tail[rt] * 10 + d) % mod;len[rt] = len[rt]*10 % mod;pos[rt] = pos[rt] * 100 % mod;
// cout<<"l:"<<l<<" r:"<<r<<" sum:"<<sum[rt]<<endl;
// cout<<"pos:"<<pos[rt]<<" head:"<<head[rt]<<" tail:"<<tail[rt]<<" len:"<<len[rt]<<endl;return;}down(rt, l, r);if( L <= mid) update(lson, L, R, d);if( R > mid) update(rson, L, R, d);up(rt);return;
}
ll query(int rt, int l, int r, int L, int R){if(L <= l && r <= R){return sum[rt];}down(rt, l , r);ll ans = 0;if(L <= mid) ans += query(lson, L, R);if(R > mid) ans += query(rson, L, R);ans %= mod;return ans;
}
int ca = 0;
void init()
{scanf("%d%d", &n, &m);build(1, 1, n);
}
void sol()
{printf("Case %d:\n", ++ca);while(m--){char cmd[10];scanf("%s", cmd);if(cmd[0] == 'w'){int l, r;ll d;scanf("%d%d%lld", &l, &r, &d);update(1, 1, n, l, r, d);}else {int l, r;scanf("%d%d", &l, &r);ll ans = query(1, 1, n, l, r);ans = (ans + mod)%mod;printf("%lld\n",ans);}}
}
int main()
{int T;cin>>T;while(T--){init();sol();}
}本文标签： 2018CCPC吉林赛区 H Lovers(线段树)
版权声明：本文标题：2018CCPC吉林赛区 H Lovers(线段树) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1699085998a327351.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论