[线段树]交错和查询

交错和查询

Time Limit: 10 Sec Memory Limit: 256 MB

Description

无限循环数字串S由长度为n的循环节s构成。设s为12345(n=5)，则数字串S为123451234512345…
　　设Si为S的第i位数字，在上面的例子中，S1=1，S2=2，S6=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，要求支持两种操作：
　　1 pos digit：修改循环节s上的某一位，即将spos改为digit。
　　2 l r：求S[l,r]内所有子串的交错和的和，即输出ans对10^9+7的模。

Input

第一行一个整数n，表示循环节s的长度。
　　第二行一个长度为n的数字串，表示循环节s。
　　第三行一个整数m，表示操作次数。
　　以下m行，每行3个整数。
　　若第一个数为1，表示是修改操作1 pos digit。
　　若第一个数为2，表示是询问操作2 l r。

Output

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

Sample Input

5
　　12345
　　5
　　2 1 5
　　2 6 10
　　1 3 5
　　2 1 5
　　2 1 6

Sample Output

19
　　19
　　25
　　36

HINT

对于10%的数据点，n, m <= 50；
　　对于20%的数据点，n, m <=1000；
　　对于40%的数据点，1 <= l<= r <= n；
　　对于100%的数据点，n, m <=200000；1 <= l <= r <= 1018；1 <= pos <= n；0 <= digit <= 9；

Main idea

给定两种操作：1.修改循环节上的某一位；2.询问[l,r]的所有子串和。

Solution

首先轻易地找到了规律，发现对于区间[l,r]，只有奇数位置上的值会对答案产生影响，并且：，然后我们拆开式子得到：。现在考虑如何用一个数据结构来维护这个Ans，这里采用线段树。

我们分几步来实现：

第一步：
　　我们先考虑l,r在一个循环节内的情况。显然对于线段树上的每个节点维护五个信息：len, odd.val, odd.val_i, eve.val, eve.val_i分别表示区间长度、奇数位置的和、奇数位置*i的和、偶数位置的和、偶数位置*i的和，那么我们上传合并线段树的时候判断一下区间长度的奇偶即可。举个例子：比如现在左区间长度为3，要更新奇数位置的值，就是左区间的奇数位置和 加上 右区间的偶数位置和，我们重载运算符判断一下即可。这样操作我们就可以得到Σai以及Σai*i。

第二步：
　　(1) 我们再来考虑一下l,r不在一个循环节内的情况。显然我们可以将区间拆成三部分：左段、中段、右段，其中中段是包含所有的1-n的整体，而左段和右段则是**~n或者1~的一部分**。

(2) 然后我们显然可以很轻易地通过计算一下x,y的间隔块数以及若干信息来算出Σai。

(3) 那么式子后面的Σai*i怎么办呢？我们发现：我们将序列分为若干段，显然每一段增加的值是一样的，那么我们就可以将Σaii(这里的i是实际位置)拆成：Σaii (在一个循环节中的位置) + Σai*(所在块数-1)*n。

(4) 然后我们中段块数一定不为1，要怎么办呢？举个例子，比如循环节长度为10，我们要求2~4段的Σ，那么显然就是Σain(i+1+2)，惊讶地发现中间的一个等差数列，那么我们要乘的就是一个等差数列的和了。

(5) 然后三段中到底是统计奇数位置的和还是统计偶数位置的和呢？发现较难处理，于是我们可以将原序列*2（拓展一倍），发现如果x是奇数，那么就加上左段的奇数位置，中段右段的奇数位置，否则加上左段的奇数位置，以及中段右段的偶数位置。

这样我们就解决了问题，具体问题还是参见代码啦。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE=200001;
const s64 Niyu=5e8+4;
const int MOD=1e9+7;

int n,T;
int a[ONE*2];
char ch[ONE];
int Q;
s64 x,y;
s64 x_orig,y_orig,x_bloc,y_bloc,diff;
s64 A,A_i;

struct power
{
    int len;

    struct point
    {
        s64 val,val_i;
        friend point operator +(point a,point b)
        {
            a.val=(a.val + b.val)%MOD;
            a.val_i=(a.val_i + b.val_i) % MOD;
            return a;
        }
    }odd,eve;

    friend power operator +(power a,power b)
    {
        power c;
        c.len = a.len+b.len;
        if(a.len%2)
        {
            c.odd = a.odd+b.eve;
            c.eve = a.eve+b.odd;
        }
        else
        {
            c.odd = a.odd+b.odd;
            c.eve = a.eve+b.eve;
        }
        return c;
    }
}Node[ONE*10],ZERO;

s64 get()
{
    s64 res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Build(int i,int l,int r)
{
    if(l==r)
    {
        Node[i].len = 1;
        Node[i].odd.val = a[l];
        Node[i].odd.val_i = a[l]*l % MOD;
        return;
    }

    int mid=(l+r)/2;
    Build(i*2,l,mid); Build(i*2+1,mid+1,r);

    Node[i] = Node[i*2] + Node[i*2+1];
}

void Update(int i,int l,int r,int L,int x)
{
    if(L==l && l==r)
    {
        Node[i].odd.val = x;
        Node[i].odd.val_i = x*l % MOD;
        Node[i].eve.val = Node[i].eve.val_i = 0;
        return;
    }

    int mid=(l+r)/2;
    if(L<=mid) Update(i*2,l,mid,L,x);
    else Update(i*2+1,mid+1,r,L,x);

    Node[i] = Node[i*2] + Node[i*2+1];
}

power Query(int i,int l,int r,int L,int R)
{
    if(L>R) return ZERO;
    if(L<=l && r<=R) return Node[i];

    int mid=(l+r)/2;
    if(R<=mid) return Query(i*2,l,mid,L,R);
    if(mid+1<=L) return Query(i*2+1,mid+1,r,L,R);
    return Query(i*2,l,mid,L,R) + Query(i*2+1,mid+1,r,L,R);
}

s64 HE(s64 a,s64 b)
{
    a--;    b--;
    if(a==b) return 1;
    if(a>b) return 0;
    s64 x=(b-a+1) % MOD;
    return (s64)(a+b)%MOD*x%MOD * Niyu % MOD;
}

int main()
{
    ZERO.len=1; ZERO.odd.val=ZERO.odd.val_i=ZERO.eve.val=ZERO.eve.val_i=0;

    n=get();
    scanf("%s",ch+1);
    for(int i=1;i<=n;i++) a[i]=ch[i]-'0';
    for(int i=1;i<=n;i++) a[i+n]=a[i];
    n*=2;    Build(1,1,n);

    T=get();
    while(T--)
    {
        Q=get();
        if(Q==1)
        {
            x=get();    y=get();
            Update(1,1,n,x,y);
            Update(1,1,n,x+n/2,y);
        }
        else
        {
            x=get();    y=get();
            x_orig=(x-1)%n+1;    y_orig=(y-1)%n+1;
            x_bloc=(x-1)/n+1;    y_bloc=(y-1)/n+1;

            diff = y_bloc-x_bloc-1;    diff%=MOD;
            if(diff!=-1)
            {
                if(x%2)
                {
                    power res_l = Query(1,1,n, x_orig,n);
                    power res_r = Query(1,1,n, 1,y_orig);
                    power res_mid = Query(1,1,n, 1,n);

                    A =( res_l.odd.val + res_r.odd.val + res_mid.odd.val * diff % MOD ) % MOD;
                    A_i=0;

                    A_i += (res_l.odd.val_i + (s64)res_l.odd.val * (x_bloc-1)%MOD * n % MOD)%MOD; A_i%=MOD;
                    A_i += (res_r.odd.val_i + (s64)res_r.odd.val * (y_bloc-1)%MOD * n % MOD)%MOD; A_i%=MOD;

                    A_i += (diff*res_mid.odd.val_i%MOD + (s64)res_mid.odd.val * n % MOD * HE(x_bloc+1,y_bloc-1)%MOD)%MOD;
                    A_i%=MOD;
                }
                else
                {
                    power res_l = Query(1,1,n, x_orig,n);
                    power res_r = Query(1,1,n, 2,y_orig);
                    power res_mid = Query(1,1,n, 2,n);

                    A =( res_l.odd.val + res_r.odd.val + res_mid.odd.val * diff % MOD ) % MOD;
                    A_i=0;

                    A_i += (res_l.odd.val_i + (s64)res_l.odd.val * (x_bloc-1)%MOD * n % MOD)%MOD; A_i%=MOD;
                    A_i += (res_r.odd.val_i + (s64)res_r.odd.val * (y_bloc-1)%MOD * n % MOD)%MOD; A_i%=MOD;

                    A_i += (diff*res_mid.odd.val_i%MOD + (s64)res_mid.odd.val * n % MOD * HE(x_bloc+1,y_bloc-1)%MOD)%MOD;
                    A_i%=MOD;
                }
            }
            else
            {
                power res = Query(1,1,n, x_orig,y_orig);
                A = res.odd.val;
                A_i=0;
                A_i += (s64)(res.odd.val_i + A * (x_bloc-1)%MOD * n % MOD) % MOD; A_i%=MOD;
            }
            printf("%lld\n", (s64)(A * (y%MOD+1) % MOD - A_i + MOD) % MOD);
        }
    }

}