首页 > 代码库 > FJoi2017 1月20日模拟赛 交错和(等差数列+rmq)

FJoi2017 1月20日模拟赛 交错和(等差数列+rmq)

<style></style>

【题目描述】


无限循环数字串S由长度为n的循环节s构成。设s12345(n=5),则数字串S123451234512345…

SiS的第i位数字,在上面的例子中,S1=1S2=2S6=1

S的一个子串S[l,r]的交错和为sum(l,r)

sum(l,r)= Sl- S1+1+ Sl+2- Sl+3+ … + (-1)r-lSr

sum(2,7)= 2 - 3 + 4 - 5 + 1 - 2 = -3


现给定循环节s,要求支持两种操作:

1pos digit

修改循环节s上的某一位,即将spos改为digit

2 lr

S[l,r]内所有子串的交错和的和,即

技术分享

输出ans109+7的模。


【输入格式】


第一行一个整数n,表示循环节s的长度。

第二行一个长度为n的数字串,表示循环节s

第三行一个整数m,表示操作次数。

以下m行,每行3个整数。

若第一个数为1,表示是修改操作1pos digit

若第一个数为2,表示是询问操作2l r


【输出格式】


对于每个询问操作输出一行,表示答案。


【样例输入】

5

12345

5

21 5

26 10

13 5

21 5

21 6

【样例输出】

19

19

25

36

【数据范围】

 

对于10%的数据点,n,m <= 50

对于20%的数据点,n,m <= 1000

对于40%的数据点,1<= l <= r <= n

对于100%的数据点,n,m <= 2000001<= l <= r <= 10181<= pos <= n0<= digit <= 9

 

Solution

毒性强烈的一道题

题解:此时询问区间[l,r]可能横跨多个循环节。借助类似于分段算法的思想,
将整个询问区间拆成三份:前缀、中间和后缀。其中前缀是询问区间[l,r]
中第一小段不完整的部分(可为空);中间部分是询问区间[l,r]中横跨的所
有完整的循环节;后缀是询问区间[l,r]中最后一小段不完整的部分(可为
空)。前缀和后缀部分的答案按照 60%的数据点中的做法查询线段树即可。而
中间部分的答案需要计算出横跨过的完整的循环节个数,并根据 n 与循环节
个数的奇偶性的不同辅以不同的计算公式,其推导比较简单但有不少细节,
可参见代码。
此外,本题可以通过将循环节延长一倍使得 n 必定为偶数,这样做就可
以避免 n 为奇数时还需使用不同的计算公式。不过这么做的话,线段树的规
模扩大一倍,而且一个修改操作需要修改 2 次线段树。算法常数更大,选手
可以通过快速 I/O 等手段改善程序性能。
时间复杂度:O(mlogn)

这里附上标解(from 福三zzq)

 

#include <iostream>#include <stdlib.h>#include <stdio.h>#include <string.h>using namespace std;#define SZ 812345typedef long long ll;int n,s[SZ];ll MOD=1e9+7;char tmp[SZ];struct BB{private:ll s_[SZ];public:ll sum(int x){    ll ans=0;    for(++x;x>=1;x-=x&-x)        ans+=s_[x], ans%=MOD;    return ans;}ll sum(int l,int r){    ll ans=sum(r)-sum(l-1);    return ans%MOD;}void add(int x,ll y){    for(++x,y%=MOD;x<=n;x+=x&-x)        s_[x]=(s_[x]+y)%MOD;}}b1[2],b2[2];void edt(int i,int p){    b1[i&1].add(i,s[i]*p);    b2[i&1].add(i,(ll)i*s[i]*p);}ll qp(ll a,ll b){    a%=MOD; ll aa=1;    while(b)    {        if(b&1) aa=aa*a%MOD;        a=a*a%MOD; b>>=1;     }    return aa;}#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}int main(){    FO(sum)    ll inv2=qp(2,MOD-2);    scanf("%d%s",&n,tmp);    for(int i=0;i<n;i++)    s[i]=s[i+n]=tmp[i]-48;    n+=n;    for(int i=0;i<n;i++)        edt(i,1);    int q; scanf("%d",&q);    while(q--)    {        int o; ll l,r;        scanf("%d%I64d%I64d",&o,&l,&r);        if(o==1)        {            --l;            edt(l,-1); edt(l+n/2,-1);            s[l]=s[l+n/2]=r;            edt(l,1); edt(l+n/2,1);            continue;        }        --l, --r;        {ll bk=l/n*n; l-=bk, r-=bk;}        if(r<n)        {            ll ans=b1[l&1].sum(l,r)*(r+1)-b2[l&1].sum(l,r);            ans=(ans%MOD+MOD)%MOD;            printf("%d\n",int(ans));        }        else        {            ll zj=r/n-1;            ll s1[3]={b1[l&1].sum(l,n-1),b1[l&1].sum(0,r%n),            b1[l&1].sum(0,n-1)};            ll s2[3]={b2[l&1].sum(l,n-1),b2[l&1].sum(0,r%n),            b2[l&1].sum(0,n-1)};            ll a1=s1[0]+s1[1]+s1[2]*(zj%MOD)%MOD; a1%=MOD;            ll a2=s2[0]+s2[1]+s1[1]*((r/n*n)%MOD)%MOD; a2%=MOD;            a2+=s2[2]*(zj%MOD)%MOD            +s1[2]*n%MOD*((zj+1)%MOD*(zj%MOD)%MOD*inv2%MOD)%MOD; a2%=MOD;            ll ans=a1*((r+1)%MOD)%MOD-a2;            ans=(ans%MOD+MOD)%MOD;            printf("%d\n",int(ans));        }    }}

 

FJoi2017 1月20日模拟赛 交错和(等差数列+rmq)