首页 > 代码库 > （预处理+莫队算法）HDU - 5381 The sum of gcd
（预处理+莫队算法）HDU - 5381 The sum of gcd
题意：
一个长度为n的数列，m次查询L到R之间所有连续子序列的gcd之和。
分析：
很明显的莫队算法。
很明显发现了gcd是单调递减的，并且最多存在32个的性质。
想了很久，脑补了许多种方法来拉伸L和R，但是都有漏洞。
实际上，这道题还是比较复杂的。。
在思考的过程中，我没有充分利用gcd的递减性质。
这题其实这题有共通之处，至少在我的做法上是这样的。
可以发现，在R向右拉伸的过程中，增加的和只是从L到R+1中的每一个后缀的和。
向左则为减，L的移动同理。
那么我们只要提前预处理每个位置的前缀所包含的所有数，以为成段会有相等的值，所以用pair存值和数量。
同理，后缀也要预处理。
那么我们就可以在将L和R拉伸时，用log的复杂度进行增减。
而预处理的复杂度仅为n*logn*logn。
查询的总复杂度为n*sqrt(n)*logn。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <set> 7 #include <vector> 8 #include <queue> 9 #include <map> 10 #include <list> 11 #include <bitset> 12 #include <string> 13 #include <cctype> 14 #include <cstdlib> 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef unsigned long long ull; 20 #define inf (0x3f3f3f3f) 21 #define lnf (0x3f3f3f3f3f3f3f3f) 22 #define eps (1e-8) 23 #define fi first 24 #define se second 25 typedef pair<ll, ll> pll; 26 27 int sgn(double a) { 28 return a < -eps ? -1 : a < eps ? 0 : 1; 29 } 30 31 const int maxn = 50010; 32 struct Q { 33 int l, r, index; 34 }; 35 Q query[maxn]; 36 int t, n, q; 37 int a[maxn]; 38 int b[maxn]; 39 const int bk = 250; 40 long long res; 41 long long ans[maxn]; 42 int f[maxn][20]; 43 44 void rmq_init() { 45 for(int i = 1; i <= n; i++) 46 f[i][0] = a[i]; 47 int k = floor(log((double)n) / log(2.0)); 48 for(int j = 1; j <= k; j++) 49 for(int i = n; i >= 1; i--) { 50 if(i + (1 << (j - 1)) <= n) 51 f[i][j] = __gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); 52 } 53 } 54 55 int rmq(int i, int j) { 56 int k = floor(log((double)(j - i + 1)) / log(2.0)); 57 return __gcd(f[i][k], f[j - (1 << k) + 1][k]); 58 } 59 60 bool cmp (Q a, Q b) { 61 if(a.l / bk == b.l / bk)return a.r < b.r; 62 else return a.l / bk < b.l / bk; 63 } 64 65 66 vector<pll> pre[maxn]; 67 vector<pll> suf[maxn]; 68 69 70 int search2(int zl, int l, int b) { 71 int left = l, right = n; 72 int w = l + 1; 73 while(left <= right) { 74 int mid = (left + right) >> 1; 75 int pp = rmq(zl, mid); 76 if(pp == b) { 77 left = mid + 1; 78 w = mid; 79 } else { 80 right = mid - 1; 81 } 82 } 83 return w; 84 } 85 86 int search3(int zl, int l, int b) { 87 int left = l, right = n; 88 int w = l + 1; 89 while(left <= right) { 90 int mid = (left + right) >> 1; 91 int pp = rmq(n - mid + 1, n - zl + 1); 92 if(pp == b) { 93 left = mid + 1; 94 w = mid; 95 } else { 96 right = mid - 1; 97 } 98 } 99 return w;100 }101 102 void Pfinit() {103 for(int i = 1; i <= n; i++) {104 pre[i].clear();105 for(int s = i - 1; s < n;) {106 int d = search2(i, s + 1, rmq(i, s + 1));107 pre[i].push_back(make_pair(d - s, rmq(i, s + 1)));108 s = d;109 }110 }111 for(int i = 1; i <= n; i++) {112 b[i] = a[n - i + 1];113 }114 for(int i = 1; i <= n; i++) {115 suf[n - i + 1].clear();116 for(int s = i - 1; s < n;) {117 int d = search3(i, s + 1, rmq(n - s, n - i + 1));118 suf[n - i + 1].push_back(make_pair(d - s, rmq(n - s, n - i + 1)));119 s = d;120 }121 }122 123 }124 125 126 void add_left( int s, int x, int v) {127 int num = s - x + 1;128 for(int i = 0; i < pre[x].size(); i++) {129 if(pre[x][i].fi >= num) {130 res += num * pre[x][i].se * v;131 break;132 } else {133 res += pre[x][i].fi * pre[x][i].se * v;134 num -= pre[x][i].fi;135 }136 }137 }138 139 140 void add_right(int s, int x, int v) {141 int num = x - s + 1;142 for(int i = 0; i < suf[x].size(); i++) {143 if(suf[x][i].fi >= num) {144 res += num * suf[x][i].se * v;145 break;146 } else {147 res += suf[x][i].fi * suf[x][i].se * v;148 num -= suf[x][i].fi;149 }150 }151 }152 153 int main() {154 scanf("%d", &t);155 while(t--) {156 res = 0;157 scanf("%d", &n);158 for(int i = 1; i <= n; i++) {159 scanf("%d", &a[i]);160 }161 rmq_init();162 Pfinit();163 scanf("%d", &q);164 for(int i = 0; i < q; i++) {165 scanf("%d%d", &query[i].l, &query[i].r);166 query[i].index = i;167 }168 sort(query, query + q, cmp);169 int pl = 1, pr = 0;170 for (int i = 0; i < q; i++) {171 int index = query[i].index;172 if (pr < query[i].r) {173 for (int j = pr + 1; j <= query[i].r; j++) {174 add_right(pl, j, 1);175 }176 177 } else {178 for (int j = pr; j > query[i].r; j--) {179 add_right(pl, j, -1);180 }181 }182 pr = query[i].r;183 if (pl < query[i].l) {184 for (int j = pl; j < query[i].l; j++) {185 add_left(pr, j, -1);186 }187 } else {188 for (int j = pl - 1; j >= query[i].l; j--) {189 add_left(pr, j, 1);190 }191 }192 pl = query[i].l;193 ans[index] = res;194 }195 for(int i = 0; i < q; i++) {196 printf("%lld\n", ans[i]);197 }198 }199 return 0;200 }
（预处理+莫队算法）HDU - 5381 The sum of gcd
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。