Ural 2062：Ambitious Experiment（树状数组 || 分块）

http://acm.timus.ru/problem.aspx?space=1&num=2062

题意：有n个数，有一个值，q个询问，有单点询问操作，也有对于区间[l,r]的每个数i，使得num[i] + w, num[i*2] + w, num[i*3] + w……

思路：有树状数组和分块两种做法，对比后分块的速度比较快（暴力的艺术）。线段树会超时（可能写法不好）。

1、树状数组用到的是单点询问区间修改，我要注意一下其写法...修改为：Add(l, w), Add(r + 1, -w); 查询为：Sum(w);

bit[]维护增加的值，每次询问的时候只要去查询该位置的所有因子的位置增加的值，还有加上本来的数字就可以了。

2、分块的做法也是类似，因为单点修改的时候增加的值不能直接加在原来的num上，所以要多开一个every数组来记录单点修改。

查询的时候每个位置就是every[i] + block[belong[i]]。

也要注意一下分块的写法= =。

先判断是否在同一块，如果在同一块就暴力扫而不是直接block+w，因为L和R不一定在边界。。。

分块：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 300010
 4 typedef long long LL;
 5 LL cnt, sz, block[N], every[N], l[N], r[N], belong[N], num[N], n, q;
 6 
 7 void Build() {
 8     sz = sqrt(n);
 9     cnt = n / sz; if(n % sz) cnt++;
10     for(int i = 1; i <= cnt; i++)
11         l[i] = (i - 1) * sz + 1, r[i] = i * sz;
12     r[cnt] = n;
13     for(int i = 1; i <= n; i++)
14         belong[i] = (i - 1) / sz + 1;
15 }
16 
17 void Update(int L, int R, int w) {
18     if(belong[L] == belong[R])
19         for(int i = L; i <= R; i++) every[i] += w;
20     else {
21         for(int i = L; i <= r[belong[L]]; i++) every[i] += w;
22         for(int i = belong[L] + 1; i <= belong[R] - 1; i++) block[i] += w;
23         for(int i = l[belong[R]]; i <= R; i++) every[i] += w;
24     }
25 }
26 
27 LL solve(int n) {
28     int tmp = sqrt(n); LL ans = 0;
29     for(int i = 1; i <= tmp; i++) {
30         if(n % i == 0) {
31             ans += block[belong[i]] + every[i];
32             if(i != n / i) ans += block[belong[n/i]] + every[n/i];
33         }
34     }
35     return ans;
36 }
37 
38 int main() {
39     ios::sync_with_stdio(false);
40     cin >> n;
41     for(int i = 1; i <= n; i++) cin >> num[i];
42     Build();
43     cin >> q;
44     while(q--) {
45         int l, r, w, kind;
46         cin >> kind;
47         if(kind == 1) {
48             cin >> w;
49             cout << solve(w) + num[w] << '
';
50             cout.flush();
51         } else {
52             cin >> l >> r >> w;
53             Update(l, r, w);
54         }
55     }
56 }

树状数组：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 300010
 4 typedef long long LL;
 5 LL bit[N], num[N];
 6 int n, q;
 7 // 区间更新,单点查询
 8 int lowbit(int x) { return x & (-x); }
 9 void Add(int x, int w) { for(int i = x; i <= n; i += lowbit(i)) bit[i] += w; }
10 LL Sum(int x) { LL ans = 0; for(int i = x; i; i -= lowbit(i)) ans += bit[i]; return ans; }
11 LL solve(int n) {
12     int tmp = sqrt(n); LL ans = 0;
13     for(int i = 1; i <= tmp; i++) {
14         if(n % i == 0) {
15             ans += Sum(i);
16             if(i != n / i) ans += Sum(n / i);
17         }
18     }
19     return ans;
20 }
21 
22 int main() {
23     ios::sync_with_stdio(false);
24     cin >> n;
25     for(int i = 1; i <= n; i++) cin >> num[i];
26     cin >> q;
27     while(q--) {
28         int kind, l, r, w;
29         cin >> kind;
30         if(kind == 1) {
31             cin >> w;
32             cout << solve(w) + num[w] << '
';
33             cout.flush();
34         } else {
35             cin >> l >> r >> w;
36             Add(l, w); Add(r + 1, -w);
37         }
38     }
39     return 0;
40 }