首页 > 代码库 > zoj 3813 Alternating Sum（2014ACMICPC Regional 牡丹江站网络赛 E）
zoj 3813 Alternating Sum（2014ACMICPC Regional 牡丹江站网络赛 E）
There is a digit string S with infinite length. In addition, S is periodic and it can be formed by concatenating infinite repetitions of a base string P. For example, if P = 3423537, then S = 3423537342353734235373423537...
Let‘s define the alternating sum on substrings of S. Assume Sl..r is a substring of S from index l to index r (all indexes are 1-based), then the alternating sum of Sl..r is:
For example, S2..10 = 423537342, then G(2, 10) = 4 - 2 + 3 - 5 + 3 - 7 + 3 - 4 + 2 = -3.
Now, you are given the base string P and you have to do many operations. There are only two kinds of operations:
- 1 x d: set Px to d, d is a single digit.
- 2 l r: find the sum of G(i, j) that l <= i <= j <= r.
For each second operation, you should output the sum modulo 109 + 7.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains a digit string P (1 <= length(P) <= 100000).
The second line contains an integer Q (1 <= Q <= 100000) indicating the number of operations. Each of the following Q lines is an operation in such format:
- 1 x d (1 <= x <= length(P), 0 <= d <= 9)
- 2 l r (1 <= l <= r <= 1018)
Output
For each "2 l r" operation, output an integer, indicating the sum modulo 109 + 7.
Sample Input
2 324242 4 2 1 1 2 1 4 1 3 7 2 3 4 324242 6 2 1 1 1 3 7 2 2 4 1 3 4 2 7 10 2 1 30
Sample Output
3 20 14 3 8 20 870
Author: LIN, Xi
Source: The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3813
思路：题目意思很清楚了，这里只说思路。
设区间[L,R]，区间长度为len=（R-L+1）,设F[i]表示G(i,i)+G(i,i+1)+......G(i,R)。那么对于区间[L,R],询问的答案即为Ans[L,R]=F[L]+F[L+1]+......+F[R]。容易得到G[i,j]=Si-G(i+1,j),所以F[i]=(R-i+1)*Si-F[i+1]。即F[i]+F[i+1]=(R-i+1)*Si。
那么Ans[L,R]=len*SL+(len-2)*S(i+2)+.....SR(len为奇数)或
len*SL+(len-2)*(L+2)+......+2*S(R-1)(len为偶数)。
那么对于给定区间[L,R]的答案可以用线段树维护，我的线段树维护4个值，sum[0]表示区间中偶数位数的和，sum[1]表示区间中奇数位置的和，tsum[0]表示Ans[L+1,R],tsum[1]表示Ans[L,R]。
如区间[3,7]={2,3,4,5,6},那么sum[0]=3+5=8,sum[1]=2+4+6=12,tsum[0]=4*3+2*5=22,tsum[1]=5*2+3*4+1*6=28。对于区间长度为偶数的类似。
现在考虑合并两个区间，对于区间p，其左儿子为lson，右儿子为rson。sum[0],sum[1]很好合并，只需要考虑左儿子长度的奇偶性，既可以完成合并。对于tsum[0]，其左部分（由左儿子的信息得到的部分）为左儿子的tsum[0]加上左儿子的sum[0]乘以右儿子的长度（自己推推就能知道）。右部分要根据左儿子长度的奇偶性来决定是右儿子的tsum[0]还是tsum[1]。对于tsum[1]也类似。
那么线段树部分就结束了。注意到题目中的数字区间是一个模式串重复无数次的一个无限长的串，那么所给的区间可能会横跨很多个模式串S，我们的线段树只是对于模式串S的线段树，那么对于超出一个模式串的部分不能只用线段树来解决。如果区间[L,R]横跨多个模式串，那么将区间L,R分成三部分，前缀pre，中间部分mid，后缀suf，前缀表示区间[L,R]第一个不完整的模式串（可为空），后缀表示最后一个不完整的模式串（可为空），中间部分为中间横跨的多个完整的模式串（可为空）。那么pre，suf可以用线段树求出，类似于区间合并的方法，这里不再赘述。设mid包括n个完整的模式串，suf的长度为Len。还是按照区间合并的思想，不过这里n可能很大，不能直接一个一个地合并，事实上可以推出来，具体公式请自己推吧，本人很懒。。。。
这里还有一个问题，如果模式串为奇数，那么合并的时候很烦人，要间隔地考虑，这里我将模式串扩大两倍，保证模式串为偶数，那么在求mid的值得时候就不需要考虑奇偶性了。但是如果将模式串扩大两倍的话，在修改操作的时候，一定要记住要修改两个位置（这里忘了WA了10+发。。。。。。）。恩，大概就是这样，下面是代码：（内存耗得飞起。。。。时间也比较慢~~）
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 200010
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
#define ll long long
#define mod 1000000007
using namespace std;
char st[maxn];
struct tree
{
ll l,r;
ll sum[2],tsum[2];
}t[maxn<<2];
void pushup(int p)
{
ll l=t[ls].r-t[ls].l+1;
ll r=t[rs].r-t[rs].l+1;
if(l%2)
{
t[p].sum[0]=(t[ls].sum[0]+t[rs].sum[1])%mod;
t[p].sum[1]=(t[ls].sum[1]+t[rs].sum[0])%mod;
t[p].tsum[0]=(t[ls].tsum[0]+r*t[ls].sum[0]%mod+t[rs].tsum[1])%mod;
t[p].tsum[1]=(t[ls].tsum[1]+r*t[ls].sum[1]%mod+t[rs].tsum[0])%mod;
}
else
{
t[p].sum[0]=(t[ls].sum[0]+t[rs].sum[0])%mod;
t[p].sum[1]=(t[ls].sum[1]+t[rs].sum[1])%mod;
t[p].tsum[0]=(t[ls].tsum[0]+r*t[ls].sum[0]%mod+t[rs].tsum[0])%mod;
t[p].tsum[1]=(t[ls].tsum[1]+r*t[ls].sum[1]%mod+t[rs].tsum[1])%mod;
}
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
t[p].sum[0]=t[p].sum[1]=t[p].tsum[0]=t[p].tsum[1]=0;
if(l==r)
{
t[p].sum[0]=t[p].tsum[0]=0;
t[p].sum[1]=t[p].tsum[1]=st[l]-'0';
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void modify(int p,int po,ll d)
{
if(t[p].l==t[p].r)
{
t[p].sum[1]=t[p].tsum[1]=d;
return;
}
if(po>mid)
modify(rs,po,d);
else
modify(ls,po,d);
pushup(p);
}
tree query(int p,ll l,ll r)
{
tree tmp;
if(t[p].l==l&&t[p].r==r)
{
return t[p];
}
if(l>mid)
return query(rs,l,r);
else if(r<=mid)
return query(ls,l,r);
else
{
tree t1=query(ls,l,mid);
tree t2=query(rs,mid+1,r);
tmp.l=t1.l,tmp.r=t2.r;
ll l=t1.r-t1.l+1;
ll r=t2.r-t2.l+1;
if(l%2){
tmp.sum[0]=(t1.sum[0]+t2.sum[1])%mod;
tmp.sum[1]=(t1.sum[1]+t2.sum[0])%mod;
tmp.tsum[0]=(t1.tsum[0]+r*t1.sum[0]%mod+t2.tsum[1])%mod;
tmp.tsum[1]=(t1.tsum[1]+r*t1.sum[1]%mod+t2.tsum[0])%mod;
}
else{
tmp.sum[0]=(t1.sum[0]+t2.sum[0])%mod;
tmp.sum[1]=(t1.sum[1]+t2.sum[1])%mod;
tmp.tsum[0]=(t1.tsum[0]+r*t1.sum[0]%mod+t2.tsum[0])%mod;
tmp.tsum[1]=(t1.tsum[1]+r*t1.sum[1]%mod+t2.tsum[1])%mod;
}
return tmp;
}
}
ll getsum(ll num,ll len,ll left,int typ)
{
if(num==0)
return 0;
ll sum=0;
sum=num%mod*t[1].tsum[typ]%mod;
ll tt;
if(num%2)
tt=((num-1)/2)%mod*(num%mod);
else
tt=((num-1)%mod)*((num/2)%mod);
tt%=mod;
ll tmp=(num%mod*left%mod+tt*len%mod)%mod;
sum=(sum+tmp*t[1].sum[typ]%mod)%mod;
return sum;
}
int main()
{
// freopen("dd.txt","r",stdin);
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%s",st);
int len=strlen(st);
for(int i=0;i<len;i++)
{
st[i+len]=st[i];
}
len*=2;
build(1,0,len-1);
int q;
scanf("%d",&q);
while(q--){
int typ;
ll ans=0,l,r;
scanf("%d",&typ);
if(typ==1)
{
int x,d;
scanf("%d%d",&x,&d);
modify(1,x-1,d);
modify(1,x-1+(len/2),d);
}
else
{
scanf("%lld%lld",&l,&r);
l--,r--;
ll lpo=l/len,rpo=r/len;
ll L=l%len,R=r%len;
if(lpo==rpo)
{
ans=query(1,L,R).tsum[1];
}
else
{
ll Len=((r-l+1)-(len-L))%mod;
tree t1=query(1,L,len-1);
tree t2=query(1,0,R);
ans=(ans+t1.tsum[1]+Len*t1.sum[1]%mod)%mod;
if((len-L)%2)
ans=(ans+t2.tsum[0])%mod;
else
ans=(ans+t2.tsum[1])%mod;
if((len-L)%2)
ans=(ans+getsum(rpo-lpo-1,len,R+1,0))%mod;
else
ans=(ans+getsum(rpo-lpo-1,len,R+1,1))%mod;
}
printf("%lld\n",ans);
}
}
}
return 0;
}zoj 3813 Alternating Sum（2014ACMICPC Regional 牡丹江站网络赛 E）