静态区间查询,没有更新操作,瞬间就想起来了哪个O(n*sqrt(n))的做法。关键是区间转移的时候不会处理了,只能说数学拙计了……
对于此类问题的时间复杂度分析,详见:http://blog.csdn.net/yang_7_46/article/details/9618637
买一送一,之前一场多校的题目的题解给的是树状数组,其实也可以用这个算法水过,时间也挺快。
http://blog.csdn.net/yang_7_46/article/details/9734635
这道题目的数学分析,等我把整块数论的想明白了总结一下发上来。
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define N 20002
struct node {
int l, r, b, id;
} q[N];
int n, a[N], m, L, R, c[N], phi[N];
ll sum, ans[N];
vector<int> d[N];
bool cmp(const node &x, const node &y) {
if (x.b == y.b) return x.r < y.r;
return x.b < y.b;
}
ll add(int val) {
ll ret = 0;
for (int i=0; i<d[val].size(); i++)
ret += phi[d[val][i]]*(c[d[val][i]]++);
return ret;
}
ll del(int val) {
ll ret = 0;
for (int i=0; i<d[val].size(); i++)
ret += phi[d[val][i]]*(--c[d[val][i]]);
return ret;
}
void work(int l, int r, int x) {
if (x) {
for (int i=l; i<L; i++) sum += add(a[i]);
for (int i=R+1; i<=r; i++) sum += add(a[i]);
for (int i=L; i<l; i++) sum -= del(a[i]);
for (int i=r+1; i<=R; i++) sum -= del(a[i]);
} else {
sum = 0;
for (int i=l; i<=r; i++) sum += add(a[i]);
}
L = l, R = r;
}
int main() {
for (int i=1; i<N; i++) phi[i] = i;
for (int i=2; i<N; i++) if (phi[i] == i) {
for (int j=i; j<N; j+=i) phi[j] = phi[j]/i*(i-1);
}
for (int i=1; i<N; i++) for (int j=i; j<N; j+=i) d[j].push_back(i);
int T;
scanf("%d", &T);
for (int cas=1; cas<=T; cas++) {
memset(c, 0, sizeof(c));
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
int block_size = sqrt(n*1.0);
for (int i=0; i<m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].b = q[i].l / block_size;
q[i].id = i;
}
sort(q, q+m, cmp);
for (int i=0; i<m; i++) {
work(q[i].l, q[i].r, i);
ans[q[i].id] = sum;
}
printf("Case #%d:\n", cas);
for (int i=0; i<m; i++)
cout << ans[i] << endl;
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
严格遵守数据结构设计课程内容要求,内含停车场管理问题和校园导航咨询系统,均通过导师验收并满分。内包含实验报告文档。
杭电acm1297 #include<stdio.h> #include<string.h> #define m 1002 int f[m][70]={{1,1},{1,1},{1,2},{1,4}} void add(int p[],int q[],int sum[]) ...=10000){sum[i]-=10000 sum[i+1]++ } }
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
2019 Multi-University Training Contest 4(2019hdu多校第五场数据与标程),欢迎大家下载
约瑟夫环 数据结构 约瑟夫环 数据结构 约瑟夫环 数据结构 约瑟夫环 数据结构
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
Least Common Multiple ...先利用gcd算法求两个数的最大公约数,再考虑最小公倍数=两数乘积/最大公约数,即可求得最小公倍数。 注意:要考虑到输入的输入的n个数中的0,有0的要去掉0求其他数的最小公倍数。 代码:
杭电ACMhdu1163
HDU1059的代码
2017hdu多校联合训练第一场标程及数据
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241