题意：给你一个排列a，定义v(l,r)表示a[l,r]中任意两者gcd的最大值。现问你在所有n*(n-1)/2对l，r中，有多少对满足v(l,r)=x，输出x=1~n的答案。
解：
对于某一个x，如果把x的所有倍数所在位置提出来，那么任意一对l，r，如果包含了其中某两个点，v就一定大于等于x。
于是我们考虑从大往小枚举x，同时考虑对于每个左端点，右端点可选的取值范围，使得这一个区间的v恰好等于x。
考虑维护一个数组b，其中每一个位置i存的是左端点为i时，右端点最右能选到b[i]，如果选到b[i]+1就会使v大于当前的x。
那么这个b数组有一个性质，就是它单调不减，很容易证明：当b[i]=k时，b[i-1]<=k。
考虑如何利用这个b，并且维护这个b。
对某个特定的x，x的倍数把序列分成了若干段。把每个提出来的位置和它前面那些数一起作为左端点考虑，那么它们的右端点必定不能小于下一个被提出来的数，同时右端点不能大于b数组。满足右端点的这两个限制的话，v就一定等于x。我们现在要求的就是左端点所在这一段中，(每个数的b[i]-下一个提出来的位置+1)，并且对0取max，再求和。这里由于b的单调性我们可以把max化掉，具体来说，找到开始大于等于(下一个位置)的地方，然后从这里到(当前这一个位置)，其中的每个数b[i]都大于等于(下一个位置)。这样就是b求个和，然后减去下一个位置*数量。
维护b时，对于1~当前位置，它们的右端点都不能到达下一个位置了，所以相当于对(下一个位置-1)取一个min。区间取min也可以利用b的单调性改成区间赋值操作，只要找到第一个大于等于要取min的数的位置，然后把它后面都赋值成要取min的数就OK了。注意：如果我们对某个x处理到一半，b仍旧满足单调性。
b需要做的操作是找到第一个大于k的位置，区间求和，区间赋值，显然线段树可以胜任，这题就做完了。
复杂度是首先枚举倍数有个调和级数，然后是线段树的log，一共log²。
1 /**
2 * There is no end though there is a start in space. ---Infinity.
3 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
4 * Only the person who was wisdom can read the most foolish one from the history.
5 * The fish that lives in the sea doesn't know the world in the land.
6 * It also ruins and goes if they have wisdom.
7 * It is funnier that man exceeds the speed of light than fish start living in the land.
8 * It can be said that this is an final ultimatum from the god to the people who can fight.
9 *
10 * Steins;Gate
11 **/
12
13 #include <bits/stdc++.h>
14 typedef long long LL;
15 typedef unsigned long long uLL;
16 typedef long double LD;
17 inline char gc() {
18 // return getchar();
19 static char buf[100000], *p1 = buf, *p2 = buf;
20 if(p1 == p2) {
21 p2 = (p1 = buf) + fread(buf, 1, 100000, stdin);
22 }
23 return (p1 == p2) ? EOF : *p1++;
24 }
25
26 template <typename T>
27 inline void read(T& x) {
28 x = 0;
29 char c(gc());
30 int f(1);
31 while(c < '0' || c > '9') {
32 if(c == '-') {
33 f = -1;
34 }
35 c = gc();
36 }
37 while(c >= '0' && c <= '9') {
38 x = x * 10 + c - '0';
39 c = gc();
40 }
41 x *= f;
42 }
43
44 template <typename T>
45 inline T Abs(T x) {
46 return x < 0 ? -x : x;
47 }
48 template <typename T>
49 inline T Max(T a, T b) {
50 return (a > b) ? a : b;
51 }
52 template <typename T>
53 inline T Min(T a, T b) {
54 return (a < b) ? a : b;
55 }
56
57 inline int read(char* s) {
58 char c(gc());
59 int top(0);
60 while(c == ' ' || c == '\n') {
61 c = gc();
62 }
63 while(c != ' ' && c != '\n' && c != EOF) {
64 s[top++] = c;
65 c = gc();
66 }
67 s[top] = 0;
68 return top;
69 }
70
71 inline LL read() {
72 LL x;
73 read(x);
74 return x;
75 }
76
77 const int N = 200010;
78
79 int n, a[N], pos[N], n2;
80 std::vector<int> v[N];
81 LL ans[N], sum[N * 4], tag[N * 4], large[N * 4];
82
83 inline void pushdown(int l, int r, int o) {
84 if(tag[o]) {
85 int mid = (l + r) >> 1;
86 tag[o << 1 | 1] = tag[o << 1] = tag[o];
87 large[o << 1] = large[o << 1 | 1] = tag[o];
88 sum[o << 1] = tag[o] * (mid - l + 1);
89 sum[o << 1 | 1] = tag[o] * (r - mid);
90 tag[o] = 0;
91 }
92 }
93
94 inline void pushup(int o) {
95 sum[o] = sum[o << 1] + sum[o << 1 | 1];
96 large[o] = Max(large[o << 1], large[o << 1 | 1]);
97 }
98
99 LL getSum(int L, int R, int l, int r, int o) {
100 if(L <= l && r <= R) {
101 return sum[o];
102 }
103 pushdown(l, r, o);
104 int mid = (l + r) >> 1;
105 LL ans = 0;
106 if(L <= mid)
107 ans = getSum(L, R, l, mid, o << 1);
108 if(mid < R)
109 ans += getSum(L, R, mid + 1, r, o << 1 | 1);
110 return ans;
111 }
112
113 void change(int L, int R, LL v, int l, int r, int o) {
114 if(L <= l && r <= R) {
115 sum[o] = v * (r - l + 1);
116 tag[o] = v;
117 large[o] = v;
118 return;
119 }
120 pushdown(l, r, o);
121 int mid = (l + r) >> 1;
122 if(L <= mid)
123 change(L, R, v, l, mid, o << 1);
124 if(mid < R)
125 change(L, R, v, mid + 1, r, o << 1 | 1);
126 pushup(o);
127 return;
128 }
129
130 int getPos(int k, int l, int r, int o) {
131 if(l == r) {
132 return (sum[o] >= k) ? r : (r + 1);
133 }
134 int mid = (l + r) >> 1;
135 pushdown(l, r, o);
136 if(large[o << 1] >= k)
137 return getPos(k, l, mid, o << 1);
138 else
139 return getPos(k, mid + 1, r, o << 1 | 1);
140 }
141
142 void build(int l, int r, int o) {
143 tag[o] = 0;
144 if(l == r) {
145 sum[o] = large[o] = n;
146 return;
147 }
148 int mid = (l + r) >> 1;
149 build(l, mid, o << 1);
150 build(mid + 1, r, o << 1 | 1);
151 pushup(o);
152 return;
153 }
154
155 inline void solve() {
156 read(n);
157 for(int i = 1; i <= n; i++) {
158 read(a[i]);
159 pos[a[i]] = i;
160 }
161 n2 = n >> 1;
162 for(int i = 2; i <= (n2); i++) {
163 for(int j = i; j <= (n); j += i) {
164 v[i].push_back(pos[j]);
165 }
166 std::sort(v[i].begin(), v[i].end());
167 }
168 build(1, n, 1);
169 ans[1] = n * 1ll * (n - 1) / 2;
170 for(int x = n2; x > 1; x--) {
171 // printf("x = %d siz = %d \n", x, v[x].size());
172 for(int i = 0; i < v[x].size() - 1; i++) {
173 int p = v[x][i], last = (i ? (v[x][i - 1] + 1) : 1), nex = v[x][i + 1];
174 // [last, p] [nex, ...]
175 int poi = getPos(nex, 1, n, 1);
176 // printf("getpos : %d -> %d \n", nex, poi);
177 poi = Max(poi, last);
178 if(poi <= p) {
179 // [poi, p]
180 ans[x] += getSum(poi, p, 1, n, 1) - 1ll * (p - poi + 1) * (nex - 1);
181 }
182 poi = getPos(nex - 1, 1, n, 1);
183 if(poi <= p) {
184 // [poi, p]
185 change(poi, p, nex - 1, 1, n, 1);
186 }
187 }
188 ans[1] -= ans[x];
189 }
190
191 for(int i = 1; i <= n; i++) {
192 printf("%lld\n", ans[i]);
193 }
194 return;
195 }
196
197 inline void clear() {
198 for(int i = 1; i <= n2; i++) {
199 v[i].clear();
200 v[i].resize(0);
201 ans[i] = 0;
202 }
203 for(int i = 1; i <= n; i++) {
204 pos[i] = a[i] = 0;
205 }
206 return;
207 }
208
209 int main() {
210 int T = read();
211 while(T--) {
212 solve();
213 if(T) {
214 clear();
215 }
216 }
217 return 0;
218 }
219 /*
220 1
221 5
222 1 4 3 5 2
223
224 */
AC代码