首页 > 代码库 > 网络赛牡丹江赛区E ZOJ3813（线段树）
网络赛牡丹江赛区E ZOJ3813（线段树）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5345
给定序列P，定义序列S为P反复重复得到的一个无穷长的序列：
if P = 3423537, then S = 3423537342353734235373423537...
再定义G(l, r) = Sl - Sl+1 + Sl+2 - ... + (-1)r-lSr
给两种操作：
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 Node2 {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 else129 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， 项数为k143 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\n", ans);203 }204 }205 }206 return 0;207 }
网络赛牡丹江赛区E ZOJ3813（线段树）