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不一定在边界。。。

分块：

 #include <bits/stdc++.h>

 using namespace std;

 #define N 300010

 typedef long long LL;

 LL cnt, sz, block[N], every[N], l[N], r[N], belong[N], num[N], n, q;

 void Build() {

     sz = sqrt(n);

     cnt = n / sz; if(n % sz) cnt++;

     for(int i = ; i <= cnt; i++)

         l[i] = (i - ) * sz + , r[i] = i * sz;

     r[cnt] = n;

     for(int i = ; i <= n; i++)

         belong[i] = (i - ) / sz + ;

 }

 void Update(int L, int R, int w) {

     if(belong[L] == belong[R])

         for(int i = L; i <= R; i++) every[i] += w;

     else {

         for(int i = L; i <= r[belong[L]]; i++) every[i] += w;

         for(int i = belong[L] + ; i <= belong[R] - ; i++) block[i] += w;

         for(int i = l[belong[R]]; i <= R; i++) every[i] += w;

     }

 }

 LL solve(int n) {

     int tmp = sqrt(n); LL ans = ;

     for(int i = ; i <= tmp; i++) {

         if(n % i == ) {

             ans += block[belong[i]] + every[i];

             if(i != n / i) ans += block[belong[n/i]] + every[n/i];

         }

     }

     return ans;

 }

 int main() {

     ios::sync_with_stdio(false);

     cin >> n;

     for(int i = ; i <= n; i++) cin >> num[i];

     Build();

     cin >> q;

     while(q--) {

         int l, r, w, kind;

         cin >> kind;

         if(kind == ) {

             cin >> w;

             cout << solve(w) + num[w] << '\n';

             cout.flush();

         } else {

             cin >> l >> r >> w;

             Update(l, r, w);

         }

     }

 }

树状数组：

 #include <bits/stdc++.h>

 using namespace std;

 #define N 300010

 typedef long long LL;

 LL bit[N], num[N];

 int n, q;

 // 区间更新,单点查询

 int lowbit(int x) { return x & (-x); }

 void Add(int x, int w) { for(int i = x; i <= n; i += lowbit(i)) bit[i] += w; }

 LL Sum(int x) { LL ans = ; for(int i = x; i; i -= lowbit(i)) ans += bit[i]; return ans; }

 LL solve(int n) {

     int tmp = sqrt(n); LL ans = ;

     for(int i = ; i <= tmp; i++) {

         if(n % i == ) {

             ans += Sum(i);

             if(i != n / i) ans += Sum(n / i);

         }

     }

     return ans;

 }

 int main() {

     ios::sync_with_stdio(false);

     cin >> n;

     for(int i = ; i <= n; i++) cin >> num[i];

     cin >> q;

     while(q--) {

         int kind, l, r, w;

         cin >> kind;

         if(kind == ) {

             cin >> w;

             cout << solve(w) + num[w] << '\n';

             cout.flush();

         } else {

             cin >> l >> r >> w;

             Add(l, w); Add(r + , -w);

         }

     }

     return ;

 }

巴特西

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

最新文章

热门文章