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

<!--
p { margin-bottom: 0.1in; direction: ltr; line-height: 120%; text-align: justify; }
-->

【题目描述】

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

设S_i为S的第i位数字，在上面的例子中，S₁=1，S₂=2，S₆=1。

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

sum(l,r)
= S_l
- S₁₊₁
+ S_l+2
- S_l+3
+ … + (-1)^r-lS_r

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

现给定循环节s，要求支持两种操作：

1
pos digit：

修改循环节s上的某一位，即将s_pos改为digit。

2 l
r：

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

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAIgAAAAhCAIAAACNy3QjAAAKPUlEQVR4nO1ae1xM6xpec5+pqahGNzXpqgtNF0Tap5It2SG2kKQj5SCXQhKSk/t2ZHccEjsUyY/IFrknNlK6SaUyyRQjKk1TzUwzs9ZZpo7m1m7mmGr6/fbz15r1vev5vvU97/t+7/etQUMQBPwF5QN6qAcgFeySaDv7fdWCawQag0ZImkA8Lk/gUraHaoo2mmGGnFnBUE5h8JSYawnP7Nc9ZAOkhWklqQv0pYwT6qy7tXfxovMfGHwAkHX6FMMMthTerjX+0UkLJc9bSQGr5tZzvIebIVaiRTmFgSdw7JpLmRVOXonv0hfPsTF9uM1BVdy5ESrGM2PP7Sk70MYbXOau2gtHXzpGOn6vKjAIJuOZ+04WbljtSBQbhLIKAwBI7Rnx2UcqHTbkvtgxM9SqJGW+nuRMoA1nzLdqknOV/D5m/ofMw+Vue5fg5eu0D6D0Z8znr099M36VuWhoKq8wMPBWay9dqXDyTqKlLZxjXZATbS/h3FjzwHDzwWTuqklLJ8w+py50qy13pZ1PYfDTJ9ttcf32zCnbNdklxflGyTFXtZ5+Zo2LSy4O2jORIGyn1MLAzk2a+Wt2/GvH8EcF22eutCo+O0+Kcw8mM7fuxh1VzxAV4XtY7bEOE/im6jKNDKluSpngYKnVGx9ogylmJenlrIlOwsoouTAw8NZrL1+pcPQ+WX9+4VybggdRFAnnHjxmiFGSw7GfI6ILgLcJz7gva6cYckDy/QDR58mO2PwndJ6TiZAaksKArQVJUTGXG/AqnPdv6Gy09Z7c9MnFsf6L4u6NTS2Nrtm6Lv5GDdp1b87trXYEsPnRvuCIzDaSNtj4hjEh8eGJaRqyDlFmoGDnvnX4tUPE4/xo79VWRclzdRUUNnIzcxqKP2pMIfW6O49+59D6kK2XSCdoz0MN+xkW/3NuQuS6LWda1xVWHXLoXaTweuSOjDo2YELstRUTBmL8EfXDvGcBt7OP2xO7ymNtx58ba6yC1HYPC7Lce//96V05IQfy63f8c5zzibSqcLuxlQeX7WmKpT5apodsvbv5qEZ32df+YJH+tItM6XMx/XrznZ/kVY9gve5yRoXTT6fqU4IjA91TFCe/fMy8lnqutoawY+t5BnrpbrtvZaXZv7OgSH8LCbDcea7RyVBkMUKpjwLoHzshQKg0ExWGVbg78FfEprJw+68mnW/y6jFmTqNhEhYt/y1fa9rGxH3e2kh2MRqJUhtFRAG81oYvLHr5WyakpzFi+i/be2iIHultUHq/45QLqFHe+4/6Ziznx8f9oNiglIcZZDNBPFYk4bHf5b8DyEFkmao03qeyqg4dN1PR4hiJVUVzGGwQHsu3eyLCtOcfTa6zil1gIghVDu15ddfoABM4oULtb4obVV0DXLWR8I+Ot0V0gsU4HQygOnFz1FSXrS5ji7cmJsXMHoNXUPaXAn5jVuSWupDMnKVkBe/F5WOG31CkhgYZ1aVNGrbWsu012bQCGoI8wUi8epMsy4WF4X7Iy28Z4TR+lOAmLMbzBqy5kwFOwPcWJM/q9gpOQwGVb/gPY/gHQpUSlVP3w4nNoRvm2r5IKr8RYjwwJxisioTF4Z833T0+VUPB2svHjMSrIdlc4Wnk0PLrIPIScv+FMgx+S2Ulk+RspoYUuQ12dfJwJLzITWFhQBaDDXw702S/fVLNNVzeHTDUQjrBkqIrmPVOasEHnIWdLgZkUKmgsTlpyprkBzqfjP1+y20ONtaF6dtz/A09LrRKHRvWK+tT9iy5khHYdHuj31nKqZy/j5E8uvguyM2M0TLCNjOEzgPAtuqSz2rWNtoylbdw2qMBRmuNxNIev+0ToDtJRcQxhPmwBo6WuNas+IuvLNxbrh3ceqoB6yJYYdj1cMAYeZEFdTan/kUtz2gFHDDMB3vjWAfO+mojIF4nG9CyJBO7RSe6p32B0mR60/7BqU4MCKsLy77qNhLZv/UAM2NHO+gzaj5zAY2ezMB5VwAHjJ+xyFSzi7c5TT6me/hF9mpT4QzCb6161apJsRgh1h2b/o5gJ5behIVBaM86kuDnEx5sZ+8S9stGZ+3EpzVp58s9V+vCAYO3oOgJOumoLagHm/MuZNWuGkmiR3q6JurhGA0tpE3nD7oSAQUDbMnZsiDR4vjDULO+cgXUVnKtzMDHhSRfCf3/MSPUKR6Ea1QW0HPoDDHfFNPBxnvHkydGrZis2TPhSDUDA1zrw+uvWaLCcOAVBjAKEU97HFoRi+Jl8GdHMnjL0IvVoRd7fi2F/tVz9fODrp//Z6Ppe/dbkt1/9+X+fibge9BVezpoZUXI9euemn26NLc2dft5/ZS5g8SMMfKeyfmtsnPGJMEmEzHK/zHoL/4k1iz0xN50/w5zkUMWOO3VlLWMGG81UtSFeO+fvrZZECm6aVXinT+8pdrhd8QgIWe1ZR8uDXHoeacjAyJezX2qIt1iAJgxpgv9eceK2iZNVZf66NdAKz0Tszvf7/gxsXNJNvURFT1urYWoXF3Umy9dQ4JVxViUVRgu7dwyn4OFDIKfyXnpFhC3vZ0tCF0XB0OZaiLFMCN1vNfZxf9e5RRgKX3rAiE1JkacCTLqPd/hlCcdZfqvRl99wJt2wIMkHKN8+r1MdOgaS4naQzmF4VQc8l12rRW+YjGlHyAIQWecqfjHjIFlxhjNDbV7+LrFnCI1DyKJxjaii21XY96Z8NQMBOB9Mt1XR/gZVl25ekCwvZRelFMYrHnYncYVoEy2CAxxpOyZTDHMyBHjPCgy9wmoeSSXlUptIZh6TpX+jHIKg8CoaZHUhhezgqGcwvyFIRSG3/J4h/taXFr+Thtpu25OWaxbpElGVqB+3/sTLvXI9OXQqXvhQ/VXlgHE0AmDUlHl4cynjhZWBWyvzk57prsw0FEDZxt95zJSDSW9tXuxxJisyboBqGL+zGa4YuiEgZjVZSj75T1FPdhWeSMlo6iT/GPgYnhOeR+zwtx329z8Y+0YtGRr9yP85twYz/Xo1Oe7BJ/axWxYr/8zZ84dtxWWpTnE6Csxdor578TgYeiEYdflN5Fn6MMBw/uQGbnhrs2WuCgfzZ7xoNW10ERLWxJaams3UERNNMFUcJgnxQavpQUhRlovjQtbwsTJsc1RFgyZMGBb1Sus46qvAYPW99kezT1z7d8J1NlB8+y/Ti3YVlOFowhOYaW09qCzthSw81ORbsOhFTIdlkzTxakBw1CWIRQGDpgvxrO7PyQAKE3KgggKv7UsMznud/U54cFWtCKGsU/3hyHJVgf1r9mMU1/YqD/RACvVZrkRtRw1fsVwS2C9GCphQEZlKQPpTO+E1FR4764eTnr+hd/dgiVwQZBJffWFZ1/fDloT+RKtkOA7ItBRW4qgLBLsALkSNmxaYZO+m+7wrdaGShikXlBudVD3NYbsu2WPr2j74ns1i3sspbRCPA6fW5fXauNlhO2L4UD+pQEY96BheG4wGY92xtxsYS+KcFb4FyBlwfAUZoTH/gSPoR7EwOK//MHIe15zuRIAAAAASUVORK5CYII=" alt="" align="absmiddle" hspace="8" />

输出ans对10⁹+7的模。

【输入格式】

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

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

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

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

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

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

【输出格式】

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

【样例输入】

5

12345

5

2
1 5

2
6 10

1
3 5

2
1 5

2
1 6

【样例输出】

19

19

25

36

【数据范围】

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

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

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

对于100%的数据点，n,
m <= 200000；1
<= l <= r <= 10¹⁸；1
<= pos <= n；0
<= 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 812345

typedef long long ll;

int n,s[SZ];

ll MOD=1e9+;

char tmp[SZ];

struct BB

{

private:

ll s_[SZ];

public:

ll sum(int x)

{

    ll ans=;

    for(++x;x>=;x-=x&-x)

        ans+=s_[x], ans%=MOD;

    return ans;

}

ll sum(int l,int r)

{

    ll ans=sum(r)-sum(l-);

    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[],b2[];

void edt(int i,int p)

{

    b1[i&].add(i,s[i]*p);

    b2[i&].add(i,(ll)i*s[i]*p);

}

ll qp(ll a,ll b)

{

    a%=MOD; ll aa=;

    while(b)

    {

        if(b&) aa=aa*a%MOD;

        a=a*a%MOD; b>>=;

    }

    return aa;

}

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

int main()

{

    FO(sum)

    ll inv2=qp(,MOD-);

    scanf("%d%s",&n,tmp);

    for(int i=;i<n;i++)

    s[i]=s[i+n]=tmp[i]-;

    n+=n;

    for(int i=;i<n;i++)

        edt(i,);

    int q; scanf("%d",&q);

    while(q--)

    {

        int o; ll l,r;

        scanf("%d%I64d%I64d",&o,&l,&r);

        if(o==)

        {

            --l;

            edt(l,-); edt(l+n/,-);

            s[l]=s[l+n/]=r;

            edt(l,); edt(l+n/,);

            continue;

        }

        --l, --r;

        {ll bk=l/n*n; l-=bk, r-=bk;}

        if(r<n)

        {

            ll ans=b1[l&].sum(l,r)*(r+)-b2[l&].sum(l,r);

            ans=(ans%MOD+MOD)%MOD;

            printf("%d\n",int(ans));

        }

        else

        {

            ll zj=r/n-;

            ll s1[]={b1[l&].sum(l,n-),b1[l&].sum(,r%n),

            b1[l&].sum(,n-)};

            ll s2[]={b2[l&].sum(l,n-),b2[l&].sum(,r%n),

            b2[l&].sum(,n-)};

            ll a1=s1[]+s1[]+s1[]*(zj%MOD)%MOD; a1%=MOD;

            ll a2=s2[]+s2[]+s1[]*((r/n*n)%MOD)%MOD; a2%=MOD;

            a2+=s2[]*(zj%MOD)%MOD

            +s1[]*n%MOD*((zj+)%MOD*(zj%MOD)%MOD*inv2%MOD)%MOD; a2%=MOD;

            ll ans=a1*((r+)%MOD)%MOD-a2;

            ans=(ans%MOD+MOD)%MOD;

            printf("%d\n",int(ans));

        }

    }

}

FJoi2017 1月20日模拟赛 交错和(等差数列+rmq)的相关教程结束。