[BZOJ3343]教主的魔法 题解
题目地址:洛谷:【P2801】教主的魔法 – 洛谷、BZOJ:Problem …
May all the beauty be blessed.
题目地址:洛谷:【P2709】小B的询问 – 洛谷、BZOJ:Problem 3781. — 小B的询问
小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
输入格式:
第一行,三个整数N、M、K。
第二行,N个整数,表示小B的序列。
接下来的M行,每行两个整数L、R。
输出格式:
M行,每行一个整数,其中第i行的整数表示第i个询问的答案。
输入样例#1:
6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6
输出样例#1:
6 9 5 2
对于全部的数据,1<=N、M、K<=50000
其实K没用。这个题本质跟[国家集训队]小Z的袜子一样,就是答案变成了上面这个题维护的分子,直接从这个题程序改过来就好。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 50005;
int n, m, k, block, col[MAXN], ccnt[MAXN];
LL ans[MAXN], now;
inline int bid(int pos) {
return pos / block + 1;
}
inline void apply(int pos, int add) {
now -= 1ll * ccnt[col[pos]] * ccnt[col[pos]];
ccnt[col[pos]] += add;
now += 1ll * ccnt[col[pos]] * ccnt[col[pos]];
}
struct Query {
int l, r, id;
} qur[MAXN];
inline bool cmp(Query a, Query b) {
return bid(a.l) == bid(b.l) ? a.r < b.r : a.l < b.l;
}
int main() {
n = readint(); m = readint(); k = readint(); block = sqrt(n);
for(int i = 1; i <= n; i++) {
col[i] = readint();
}
for(int i = 1; i <= m; i++) {
qur[i].l = readint(); qur[i].r = readint(); qur[i].id = i;
}
std::sort(qur + 1, qur + m + 1, cmp);
int l = 1, r = 0;
for(int i = 1; i <= m; i++) {
for(; l < qur[i].l; l++) apply(l, -1);
for(; l > qur[i].l; l--) apply(l - 1, 1);
for(; r < qur[i].r; r++) apply(r + 1, 1);
for(; r > qur[i].r; r--) apply(r, -1);
ans[qur[i].id] = now;
}
for(int i = 1; i <= m; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
题目地址:洛谷:【P3327】[SDOI2015]约数个数和 – 洛谷、BZOJ:Problem 3994. — [SDOI2015]约数个数和
设d(x)为x的约数个数,给定N、M,求\sum^N_{i=1}\sum^M_{j=1} d(ij)。
输入格式:
输入文件包含多组测试数据。第一行,一个整数T,表示测试数据的组数。接下来的T行,每行两个整数N、M。
输出格式:
T行,每行一个整数,表示你所求的答案。
输入样例#1:
2 7 4 5 6
输出样例#1:
110 121
1<=N, M<=50000
1<=T<=50000
参考资料:BZOJ 3994 – [SDOI2015]约数个数和 | Sengxian’s Blog
首先我们要知道一个事,d(xy) = \sum_{i|x} \sum_{j|y} [\mathrm{gcd}(i, j) == 1]。有了它,我们就可以对要求的式子进行变形,首先是最开始的版本([表达式]表示表达式为真时值为1,否则值为0)
\sum^n_{i=1} \sum^m_{j=1} d(ij)
代换掉d函数
\sum^n_{i=1} \sum^m_{j=1} \sum_{a|i} \sum_{b|j} [\mathrm{gcd}(a, b) == 1]
我们知道有\sum_{x|n} \mu(x) = [n == 1],因此可以带进上面的条件
\sum^n_{i=1} \sum^m_{j=1} \sum_{a|i} \sum_{b|j} \sum_{x|\mathrm{gcd}(a, b)} \mu(x)
考虑枚举x统计每个\mu(x)的数量,上式可变换为
\sum^n_{i=1} \sum^m_{j=1} \sum_{x|i, x|j} \mu(x) d(\frac{i}{x}) d(\frac{j}{x})
把\mu(x)项放在前面
\sum^n_{i=1} \mu(x) \sum_{x|i} d(\frac{i}{x}) \sum_{x|j} d(\frac{j}{x})
后面两项换个元
\sum^n_{i=1} \mu(x) \sum_{i=1}^{\lfloor \frac{n}{x} \rfloor} d(i) \sum_{i=1}^{\lfloor \frac{m}{x} \rfloor} d(j)
我们如果能预处理出d(x), \mu(x),再用一波除法分块,就可以把原来O(n^2)的暴力求值变成现在的O(n \sqrt{n})优秀算法。而d(x)是一个积性函数,可以跟\mu(x)一起筛出来。
我们考虑如何筛d(x)。两两互质的情况可以直接乘起来,当遇到不互质的情况,prime[j]一定是i中最小的那个质因子,我们可以求出每个数最小质因子的次数,从而获取其他质因子的选择方案数之乘积,推得i*prime[j]这个数字的d值。这是由于如果能够将x表示为p_1^{c_1}p_2^{c_2} \cdots p_k^{c_k}的形式,则d(x) = \prod_{i=1}^n (c_i + 1)。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 50005;
bool notprime[MAXN];
int prime[MAXN], ptot, mu[MAXN], d[MAXN], cnt[MAXN];
inline void sieve() {
mu[1] = d[1] = 1; notprime[1] = true;
for(int i = 2; i < MAXN; i++) {
if(!notprime[i]) {
prime[++ptot] = i; mu[i] = -1; d[i] = 2; cnt[i] = 1;
}
for(int j = 1; j <= ptot && i * prime[j] < MAXN; j++) {
int t = i * prime[j];
notprime[t] = true;
if(i % prime[j]) {
mu[t] = -mu[i]; d[t] = d[i] * 2; cnt[t] = 1;
} else {
mu[t] = 0; cnt[t] = cnt[i] + 1; d[t] = d[i] / (cnt[i] + 1) * (cnt[t] + 1);
}
}
}
for(int i = 2; i < MAXN; i++) {
mu[i] += mu[i - 1];
d[i] += d[i - 1];
}
}
inline LL cal(int n, int m) {
if(n > m) std::swap(n, m);
LL res = 0;
for(int i = 1; i <= n;) {
int j = std::min(n / (n / i), m / (m / i));
res += 1ll * (mu[j] - mu[i - 1]) * d[n / i] * d[m / i];
i = j + 1;
}
return res;
}
int T, n, m;
int main() {
sieve();
T = readint();
while(T--) {
n = readint(); m = readint();
printf("%lld\n", cal(n, m));
}
return 0;
}
题目地址:洛谷:【P2664】树上游戏 – 洛谷
lrb有一棵树,树的每个节点有个颜色。给一个长度为n的颜色序列,定义s(i,j) 为i 到j 的颜色数量。以及
sum_i = \sum_{j=1}^n s(i, j)
现在他想让你求出所有的sum[i]
输入格式:
第一行为一个整数n,表示树节点的数量
第二行为n个整数,分别表示n个节点的颜色c[1],c[2]……c[n]
接下来n-1行,每行为两个整数x,y,表示x和y之间有一条边
输出格式:
输出n行,第i行为sum[i]
输入样例#1:
5 1 2 3 2 3 1 2 2 3 2 4 1 5
输出样例#1:
10 9 11 9 12
sum[1]=s(1,1)+s(1,2)+s(1,3)+s(1,4)+s(1,5)=1+2+3+2+2=10
sum[2]=s(2,1)+s(2,2)+s(2,3)+s(2,4)+s(2,5)=2+1+2+1+3=9
sum[3]=s(3,1)+s(3,2)+s(3,3)+s(3,4)+s(3,5)=3+2+1+2+3=11
sum[4]=s(4,1)+s(4,2)+s(4,3)+s(4,4)+s(4,5)=2+1+2+1+3=9
sum[5]=s(5,1)+s(5,2)+s(5,3)+s(5,4)+s(5,5)=2+3+3+3+1=12
对于40%的数据,n<=2000
对于100%的数据,1<=n,c[i]<=10^5
参考资料:题解 P2664 【树上游戏】 – Salamander 的博客 – 洛谷博客
超麻烦的点分治,说实话我在写这篇博文的时候自己都不是很懂。
对于每一个重心,我们先计算其子树内点对它答案的贡献,该贡献即为每种颜色在每条路径第一次出现的位置对应的子树大小之和。我们把子树中每种颜色在每条路径第一次出现的位置的子树大小记为cnt数组,该数组的意义实际上就是包含该种颜色的路径数,则子树内点对重心的贡献就是对cnt数组求和。
接着考虑计算经过重心的路径的贡献。对于每个单独的子树,我们可以求出类似上述cnt数组定义的ct数组。对于一个出现在重心到子树节点x的路上上的颜色col,它会与除了该子树以外的其他到重心路径上无该颜色的点组成一条没有被计算过的路径,因此该颜色会对该点的sum数组产生(siz[rt]-siz[v])-(cnt[col]-ct[col])这么多贡献,同时该颜色也会对该点的子树产生贡献,因此要把这个贡献给传递到子树中去。另外,还有可能在别的子树出现过的颜色对该点的贡献,实际上就是对cnt[col]-ct[col]求和。
总复杂度O(n \log n)。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 100005;
std::vector<int> gra[MAXN];
int n, c[MAXN];
int siz[MAXN], rt, rtsiz;
bool vis[MAXN];
inline void findrt(int u, int fa, int tot) {
siz[u] = 1; int mxsiz = 0;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(vis[v] || v == fa) continue;
findrt(v, u, tot);
siz[u] += siz[v];
mxsiz = std::max(mxsiz, siz[v]);
}
mxsiz = std::max(mxsiz, tot - siz[u]);
if(mxsiz < rtsiz) {
rt = u; rtsiz = mxsiz;
}
}
inline void calsiz(int u, int fa) {
siz[u] = 1;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(vis[v] || v == fa) continue;
calsiz(v, u);
siz[u] += siz[v];
}
}
int cnt[MAXN], cct[MAXN], ct[MAXN], col[MAXN], cl[MAXN], top, tp, tot, path;
LL sum[MAXN];
int has[MAXN];
bool exist[MAXN];
inline void dfs(int u, int fa, int *cnt) {
if(!exist[c[u]]) {
col[++top] = c[u]; exist[c[u]] = true;
}
if(++has[c[u]] == 1) cnt[c[u]] += siz[u];
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(vis[v] || v == fa) continue;
dfs(v, u, cnt);
}
has[c[u]]--;
}
inline void modify(int u, int fa, LL lst) {
LL tag = lst;
if(++has[c[u]] == 1) tag += path - cnt[c[u]];
sum[u] += tot + tag;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(vis[v] || v == fa) continue;
modify(v, u, tag);
}
has[c[u]]--;
}
inline void calc(int u) {
calsiz(u, 0);
top = tot = 0;
dfs(u, 0, cnt);
for(int i = 1; i <= top; i++) {
exist[col[i]] = false;
}
tp = top;
for(int i = 1; i <= top; i++) {
tot += cnt[cl[i] = col[i]];
cct[col[i]] = cnt[col[i]];
}
sum[u] += tot;
int temp = tot;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(vis[v]) continue;
has[c[u]] = true; top = 0;
dfs(v, u, ct);
has[c[u]] = false;
for(int j = 1; j <= top; j++) {
exist[col[j]] = false;
}
cnt[c[u]] -= siz[v];
tot -= siz[v];
for(int j = 1; j <= top; j++) {
cnt[col[j]] -= ct[col[j]];
tot -= ct[col[j]];
}
path = siz[u] - siz[v];
modify(v, u, 0);
cnt[c[u]] += siz[v];
tot = temp;
for(int j = 1; j <= top; j++) {
cnt[col[j]] = cct[col[j]];
ct[col[j]] = 0;
}
}
for(int i = 1; i <= tp; i++) {
cnt[cl[i]] = 0;
}
vis[u] = true;
}
inline void divide(int u) {
calc(u);
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(vis[v]) continue;
rt = 0; rtsiz = n; findrt(v, u, siz[v]);
divide(rt);
}
}
int main() {
n = readint();
for(int i = 1; i <= n; i++) {
c[i] = readint();
}
for(int i = 1, u, v; i < n; i++) {
u = readint(); v = readint();
gra[u].push_back(v); gra[v].push_back(u);
}
rt = 0; rtsiz = n; findrt(1, 0, n);
divide(rt);
for(int i = 1; i <= n; i++) {
printf("%lld\n", sum[i]);
}
return 0;
}