hdu7107 GCD on Sequence

题意:给你一个排列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²。

hdu7107 GCD on Sequence
  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代码

 

上一篇:C/C++内联函数


下一篇:【学术】对于代码常系数影响因素的考察——以快读为例