ConanKIDの小窝

根号分治 学习笔记

posted on 2021-10-04 15:32:01 | under 学习笔记 |

for (int i = y; i <= n; i += x)
ans += a[i];

for (int j = 1; j <= n; j++)
cnt[j][x % j] -= (a[x] - y);
a[x] = y;

#include<bits/stdc++.h>
using namespace std;
const int maxn = 150005, maxb = sqrt(150000) + 5;
int n, m, block;
int a[150005];
int cnt[maxb][maxb];
int main() {
cin >> n >> m; block = sqrt(n);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= block; i++)
for (int j = 1; j <= n; j++)
cnt[i][j % i] += a[j];//预处理出cnt
for (int i = 1; i <= m; i++) {
char p; int x, y; cin >> p >> x >> y;
if (p == 'A') {
if (x <= block) cout << cnt[x][y] << endl;
else {
int ans = 0;
for (int j = y; j <= n; j += x)
ans += a[j];
cout << ans << endl;
}//分情况采用不同方法统计答案
} else {
for (int j = 1; j <= block; j++)
cnt[j][x % j] -= (a[x] - y);
a[x] = y;//维护cnt
}
}
return 0;
}

1. 设置指针$i$，首先指向$lim+1$；
2. dfs求出$ans_i$，同时在$i$的右边二分，找出最后一个与$i$答案相同的点，并把这一段的答案都更新为$ans_i$；
3. 重复以上过程，直至求解完毕。

#include<bits/stdc++.h>
using namespace std;
int n, block;
vector<int> a[100005];
int dfn[100005], cnt;
int f[100005], s[100005];
int ans[100005];
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
void dfs(int fa, int x) {
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if (y == fa) continue;
f[y] = x; dfs(x, y);
}
dfn[++cnt] = x;
}//预处理
int check(int k) {//求出ans[k]
int ans = 0;
for (int i = 1; i <= n; i++)
s[i] = 1;
for (int i = 1; i <= n; i++) {
int u = dfn[i];
if (f[u] && s[u] != -1 && s[f[u]] != -1)
if (s[f[u]] + s[u] >= k) ans++, s[f[u]] = -1;//能拼就拼
else s[f[u]] = max(s[f[u]], s[u] + 1);
}
return ans;
}
int main() {
n = read(); block = sqrt(n * log2(n));
for (int i = 1; i < n; i++) {
a[x].push_back(y); a[y].push_back(x);
}
dfs(0, 1);
printf("%d\n", n);
for (int i = 2; i <= block; i++)
printf("%d\n", check(i));
for (int i = block + 1; i <= n; i++) {
int x = check(i), l = i, r = n + 1;
while (l + 1 < r) {
int mid = l + r >> 1;
if (check(mid) == x) l = mid;
else r = mid;
}//二分
for (; i <= l; i++) printf("%d\n", x);
i--;
}
return 0;
}