网络赛牡丹江赛区E ZOJ3813（线段树）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5345

给定序列P，定义序列S为P反复重复得到的一个无穷长的序列：

if P = 3423537, then S = 3423537342353734235373423537...

再定义G(l, r) = S_l - S_l+1 + S_l+2 - ... + (-1)^r-lS_r

给两种操作：

1 x d：将序列P的第x想改为d（d是一个简单数字0~9）

2 l r ：求sum of G(i, j) that l <= i <= j <= r.

比赛时看到这个题，以为是求G(l, r)，然后就高高兴兴用线段树开始敲了，快敲完才知道是求对任意的l <= i <= j <= r，求G（i, j）的和

比赛快完了才想到思路，没时间敲了，今天花了大半天时间终于A掉。

按照题目要求，求sum of G(i, j) ，所以先把它化简，找下规律，很容易可以得到以下规律：

Sum{ G(i, j) } = (r - l + 1) * S[l] + (r - l - 1) * S[l + 2] + (r - l - 3) * S[l + 4] + ... ... + S[r] (R-l+1)为奇数
+ 2 * S[r-1] (R-l+1)为偶数

注意上面相邻两项之间下标差都是2，由于不知道是需要用2*S[i] + 4*S[i-2]... 还是要用S[i] + 3*S[i-2]...，所以都保存起来

然后我们定义F[i][0] = S[i] + 3 * S[i-2] + 5 * S[i-4] + ... ...

F[i][1] = 2 * S[i] + 4 * F[i-2] + 6 * F[i-4] + ... ...

再定义P[i] = S[i] + S[i - 2] + S[i - 4] + ... ...

经过简单计算可以得出：最后题目要求的Sum{ G(l, r) } = F[r] - F[l - 2] - k * P[l - 2] (这里的F的第二维取决于（r-l+1）是奇还是偶，通过计算可以得到令 len = (r - l + 1) , 那么 k = len + len % 2) )

然后定义线段树节点：

1 struct Node
2 {
3     int l, r;
4     LL P[2], F[2][2];
5 }t[MAXN<<2];

其中:
P[0] = S[r] + S[r - 2] + S[r - 4] + ... ... + S[k] (k >= l)
P[0] = S[r-1] + S[r - 3] + S[r - 5] + ... ... + S[k] (k >= l)

F[0][0] = S[r] + 3 * S[r - 2] + 5 * S[r - 4] + ... ... + x * S[k] (k >= l)
F[0][1] = 2*S[r] + 4*S[r - 2] + 6*S[r - 4] + ... ... + x * S[k] (k >= l)
F[1][0] = S[r-1] + 3 * S[r - 3] + 5 * S[r - 5] + ... ... + x * S[k] (k >= l)
F[1][1] = 2*S[r-1] + 4*S[r - 3] + 6*S[r - 5] + ... ... + x * S[k] (k >= l)

然后做线段树的单电修改，修改某个叶子节点后往上更新， rc和lc对应于当前节点k的右子节点和左子节点, len是rc节点的区间长度

1     rep(i, 0, 1) {
2         rep(j, 0, 1) {
3             t[k].F[i][j] = ( t[rc].F[i][j] + t[lc].F[(len-i) & 1][j]
4                             + t[lc].P[(len-i) & 1] * (len-i + (len-i)%2) ) % MOD;
5         }
6         t[k].P[i] = (t[rc].P[i] + t[lc].P[(len - i) & 1]) % MOD;
7     }

接下来写两个查询，分别是查询[1, p]的P值，和查询[1,p]的F值， flag用来标注是2,4,6,8... ... 还是 1, 3, 5, 7 ... ...增长

 1 LL query_pre(int k, int p)
 2 {
 3     if(t[k].l == t[k].r) return t[k].P[0];
 4 
 5     int mid = (t[k].l + t[k].r) >> 1;
 6 
 7     if(p <= mid) return query_pre(k<<1, p);
 8 
 9     int re = (p - mid);
10     return (t[k<<1].P[re&1] + query_pre(k<<1|1, p)) % MOD;
11 }
12 
13 LL query_F(int k, int p, int flag)
14 {
15     if(t[k].l == t[k].r) return t[k].F[0][flag];
16 
17     int mid = (t[k].l + t[k].r) >> 1;
18 
19     if(p <= mid) return query_F(k<<1, p, flag);
20 
21     int re = p - mid;
22 
23     return (t[k<<1].F[re&1][flag] + t[k<<1].P[re&1] * (re + re%2) + query_F(k<<1|1, p, flag)) % MOD;
24 }

这样，在不考虑 l 和 r 大于给定序列长度n的情况下，原题已经可解，答案就是：

query_F(1, r) - query_F(1, l - 2) - query_Pre(1, l - 2) * (len + len % 2) (其中len = r - l + 1)

然后再考虑l 和 r比较大的情况，由于虽然l 和 r 比较大，但是给定序列的长度是小于1e5的，所以说显然中间过程是可以直接推算出来的，事实上，设原序列长度为n， len = (r - l + 1), 那么最初给出的序列会出现 k = (len - 1) / n 次，而这 k 次序列可以看做是出现了k次F[n],以及出现了 a * P[n], (a + n) * P[n], (a + 2 n) * P[n]... ...(a + (k-1)*n) * P[n]

这正好是一个等差数列，所以计算新的F[r] (r >> n)时， F[n] = query(r) + k * F[n] + P[n] * (a + (a + d) + (a + 2 * d) + ... ... + (a + (k-1) * d) ).

注意，上面的等差数列首项a还未确定，公差d也还未确定，也就是说，只要计算出a 和 d，就计算出了我们的要求的答案。

注意到如果n（原序列长度）是偶数，又因为增量是2，所以可以计算出公差 d = n,而首项 a = p + p % 2 , 其中p = (r - 1) % n + 1,也就是最后一个剩下序列的长度

如果n是奇数，会出现有时我们需要的是F[n], 有时需要的又是F[n-1]，这是只要理解为两个等差数列就可以了，其中公差都是d = 2 * n, 但是首项不同

代码还有很多需要注意的小细节，很多地方需要反复计算（比如那两个等差数列），反正就是比较麻烦

  1 #include <map>
  2 #include <set>
  3 #include <stack>
  4 #include <queue>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <vector>
  8 #include <cstdio>
  9 #include <cctype>
 10 #include <cstring>
 11 #include <cstdlib>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 #define INF 1e9
 16 #define inf (-((LL)1<<40))
 17 #define lson k<<1, L, mid
 18 #define rson k<<1|1, mid+1, R
 19 #define mem0(a) memset(a,0,sizeof(a))
 20 #define mem1(a) memset(a,-1,sizeof(a))
 21 #define mem(a, b) memset(a, b, sizeof(a))
 22 #define FOPENIN(IN) freopen(IN, "r", stdin)
 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
 24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
 25 template<class T> T CMP_MIN(T a, T b) { return a < b; }
 26 template<class T> T CMP_MAX(T a, T b) { return a > b; }
 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
 31 
 32 //typedef __int64 LL;
 33 typedef long long LL;
 34 const int MAXN = 110000;
 35 const int MAXM = 1000006;
 36 const double eps = 1e-10;
 37 const LL MOD = 1000000007;
 38 
 39 struct Node
 40 {            // P[0] = S[r] + S[r-2] + S[r-4]...    P[1] = S[r-1] + S[r-3] + S[r-5] + ...
 41     int l, r;//F[0][0] = S[r] + 3 * S[r-2] + ...    F[0][1] = 2 * S[r] + 4 * S[r-2] + ...
 42     LL P[2], F[2][2];// F[1][0] = S[r-1] + 3 * S[r - 3] + ...  F[1][1] = 2 * S[r-1] + 4 * S[r-3] + ...
 43 }t[MAXN<<2];
 44 int n, cas, q;
 45 char str[110000];
 46 
 47 //建树
 48 void build(int k, int L, int R)
 49 {
 50     t[k].l = L;
 51     t[k].r = R;
 52     t[k].P[0] = t[k].P[1] = 0;//P和F统统初始化为0
 53     rep (i, 0, 1) rep(j, 0, 1)
 54         t[k].F[i][j] = 0;
 55     if(L == R) return ;
 56 
 57     int mid = (R + L) >> 1;
 58     build(k<<1, L, mid);
 59     build(k<<1|1, mid + 1, R);
 60 }
 61 
 62 //从子节点更新父节点
 63 void push_up(int k)
 64 {
 65     int lc = k<<1, rc = k<<1|1;
 66     int re = t[rc].r - t[rc].l + 1;//右侧节点长度
 67     rep(i, 0, 1) {
 68         rep(j, 0, 1) {
 69             if(re==1 && i==1) {//特殊处理右侧只有一个节点的情况
 70                 t[k].F[i][j] = t[lc].F[0][j];
 71                 continue;
 72             }
 73             t[k].F[i][j] = ( t[rc].F[i][j] + t[lc].F[(re-i) & 1][j]
 74                             + t[lc].P[(re-i) & 1] * (re-i + (re-i)%2) ) % MOD;
 75         }
 76         t[k].P[i] = (t[rc].P[i] + t[lc].P[(re - i) & 1]) % MOD;
 77     }
 78 }
 79 
 80 //将位置为p的节点更新为val
 81 void update(int k, int p, int val)
 82 {
 83     if(t[k].l == t[k].r) {
 84         t[k].P[0] = t[k].F[0][0] = val;
 85         t[k].F[0][1] = 2 * val;
 86         return;
 87     }
 88     int m = (t[k].l + t[k].r) >> 1;
 89 
 90     if(p <= m) update(k<<1, p, val);
 91 
 92     else update(k<<1|1, p, val);
 93 
 94     push_up(k);
 95 }
 96 
 97 LL query_pre(int k, int p)//询问S[p] + S[p-2] + ...
 98 {
 99     if(t[k].l == t[k].r) return t[k].P[0];
100 
101     int mid = (t[k].l + t[k].r) >> 1;
102 
103     if(p <= mid) return query_pre(k<<1, p);
104 
105     int re = (p - mid);
106     return (t[k<<1].P[re&1] + query_pre(k<<1|1, p)) % MOD;
107 }
108 
109 LL query_F(int k, int p, int flag)//询问F[p][flag] + F[p-2][flag] + ...
110 {
111     if(t[k].l == t[k].r) return t[k].F[0][flag];
112 
113     int mid = (t[k].l + t[k].r) >> 1;
114 
115     if(p <= mid) return query_F(k<<1, p, flag);
116 
117     int re = p - mid;
118 
119     return (t[k<<1].F[re&1][flag] + t[k<<1].P[re&1] * (re + re%2) + query_F(k<<1|1, p, flag)) % MOD;
120 }
121 
122 LL get_mul(LL fir, LL d, LL k)//计算首项为fir，公差为d，项数为k的等差数列和
123 {
124     LL tmp1 = (k % MOD) * (fir % MOD) % MOD;
125     LL tmp2 = k;
126     if( k % 2 == 0 )
127         tmp2 = k / 2 % MOD * ((k-1) % MOD) % MOD;
128     else
129         tmp2 = k % MOD * ((k-1) / 2 % MOD)  % MOD;
130     tmp2 = tmp2 * (d % MOD) % MOD;
131     return (tmp1 + tmp2) % MOD;
132 }
133 
134 //计算F[p][flag] + F[p-2][flag] + ... ...(这里p >> n)
135 LL get_F(LL p, LL flag)
136 {
137     LL k = (p - 1) / n;
138     p = (p - 1) % n + 1;
139     LL ans = query_F(1, p, flag);
140     if(n % 2 == 0 && k > 0) {//这里n是偶数，只有一个等差数列
141         ans = (ans + k % MOD * t[1].F[p&1][flag] ) % MOD;
142                     //首项为p + p%2, 公差为n， 项数为k
143         ans = (ans + get_mul(p + p % 2, n, k) * t[1].P[p&1] % MOD) % MOD;
144     }
145     else if(n % 2 == 1 && k > 0) {//n是奇数，会存在两个等差数列
146         LL tmp = p % 2 ? -1 : 1;
147 
148         ans = (ans + (k+1)/2 % MOD * t[1].F[p&1][flag]) % MOD;
149 
150         ans = (ans + k/2 % MOD * t[1].F[!(p&1)][flag]) % MOD;
151 
152         ans = (ans + get_mul(p + p%2, n*2, (k+1)/2) * t[1].P[p&1] % MOD) % MOD;
153 
154         ans = (ans + get_mul(p + p%2 + n + tmp, n*2, k/2) * t[1].P[!(p&1)] % MOD) % MOD;
155     }
156     return ans;
157 }
158 
159 //拿到P[p] + P[p-2] + P[p-4] + ... ... (p >> n)
160 LL get_P(LL p)
161 {
162     LL k = (p - 1) / n;
163     p = (p - 1) % n + 1;
164     LL ans = query_pre(1, p);
165     if(n % 2 == 0 && k > 0) {
166         ans = (ans + k % MOD * t[1].P[p&1]) % MOD;
167     }
168     else if(n % 2 == 1 && k > 0) {
169         ans = (ans + (k+1)/2 % MOD * t[1].P[p&1]) % MOD;
170 
171         ans = (ans + k/2 % MOD * t[1].P[!(p&1)]) % MOD;
172     }
173     return ans;
174 }
175 
176 int main()
177 {
178     freopen("in.txt", "r", stdin);
179     //freopen("out.txt", "w", stdout);
180     scanf("%d%*c", &cas);
181     while(cas--)
182     {
183         LL a, b, c;
184         gets(str);
185         build(1, 1, n=strlen(str));
186         for(int i =0 ; i < n; i ++)
187             update(1, i + 1, str[i] - '0');
188         scanf("%d", &q);
189         while(q--) {
190             scanf("%lld %lld %lld%*c", &a, &b, &c);
191             if(a == 1) update(1, (int)b, (int)c);
192             else {
193                 LL rf = 0, lf = 0, lp = 0;
194                 LL len = (c - b + 1), tmp = (len & 1 ^ 1);
195                 rf = get_F( c - tmp, tmp );
196                 if(b > 2) {
197                     lf = get_F( b-2, tmp );
198                     lp = get_P( b-2 );
199                 }
200                 //计算节结果
201                 LL ans = ((rf - lf - (len + len%2) % MOD * lp) % MOD + MOD) % MOD;
202                 printf("%lld
", ans);
203             }
204         }
205     }
206     return 0;
207 }