CodeChef FNCS (分块+树状数组)

题目:https://www.codechef.com/problems/FNCS

题解:

  我们知道要求区间和的时候,我们用前缀和去优化。这里也是一样,我们要求第 l 个函数到第 r 个函数 [l, r] 的函数和,那么我们可以用 sum[r] - sum[l-1] 来求得。

  由于这个数据量有点大,所以我们将函数分块。

  例如样例:

    1 3    有5个函数,那么我们分成3块。{ [1 3] , [2 5] }, { [4 5], [3 5] }, { [1 2] }。每一块对应都有一个sum ,这时如果我们要求前3个函数的和,就可以 (第一块的sum + 第3个函数的和)
    2 5    在一个块内暴力的复杂度是O(sqrt(n))
    4 5
    3 5    还有就是在处理块内函数总sum 记录下每一个a[i] 对应的权值。比如在第一块中 1 2 2 1 1 分别是a1~a5对这一块sum 的贡献。 
    1 2

  更新的时候就维护一下就可以了

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <vector>
  8 #include <queue>
  9 #include <map>
 10 #include <stack>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 typedef unsigned long long uLL;
 15 #define ms(a, b) memset(a, b, sizeof(a))
 16 #define pb push_back
 17 #define mp make_pair
 18 const LL INF = 0x7fffffff;
 19 const int inf = 0x3f3f3f3f;
 20 const int mod = 1e9+7;
 21 const int maxn = 100000+10;
 22 const int maxm = 1000000+10;
 23 int a[maxn], l[maxn], r[maxn], Add[maxn];
 24 int unit, num, n;
 25 int cnt[1000][maxn];//记录在第i块,j值的权
 26 uLL sum[1000];//块的sum
 27 uLL BIT_SUM[maxn];
 28 int low_bit(int x)
 29 {
 30     return x&-x;
 31 }
 32 uLL BIT_sum(int x)
 33 {
 34     uLL ret = 0;
 35     while(x>0){
 36         ret += 1uLL*BIT_SUM[x]; x -= low_bit(x);
 37     }
 38     return ret;
 39 }
 40 void add(int x, int d)
 41 {
 42     while(x<=n){
 43         BIT_SUM[x] += d; x+=low_bit(x);
 44     }
 45 }
 46 uLL query(int x)
 47 {
 48     return 1uLL*BIT_sum(x);
 49 }
 50 uLL Query(int x)
 51 {
 52     int end_unit = x/unit + 1;
 53     LL ans = 0;
 54     for(int i = 1;i<end_unit;i++)
 55         ans += sum[i];
 56     for(int i = (end_unit-1)*unit+1;i<=x;i++)
 57         ans += query(r[i]) - query(l[i]-1);
 58     return ans;
 59 }
 60 void init()
 61 {
 62     ms(BIT_SUM, 0);
 63     ms(sum, 0);
 64     ms(cnt, 0);
 65 }
 66 int main() {
 67 #ifdef LOCAL
 68     freopen("input.txt", "r", stdin);
 69 //        freopen("output.txt", "w", stdout);
 70 #endif
 71 //    ios::sync_with_stdio(0);
 72 //    cin.tie(0);
 73     init();
 74     scanf("%d", &n);
 75     for(int i = 1;i<=n;i++){
 76         scanf("%d", &a[i]);
 77         add(i, a[i]);
 78     }
 79     for(int i = 1;i<=n;i++)  scanf("%d%d", &l[i], &r[i]);
 80     unit = (int)sqrt(n);//块的大小
 81     num = (n-1)/unit+1;//块的数量
 82     for(int i = 1;i<=num;i++){
 83         int begin_f = (i-1)*unit+1;//这一块的开始函数
 84         int end_f = begin_f + unit - 1;//结束函数
 85         ms(Add,0);
 86         for(int j = begin_f;j<=end_f&&j<=n;j++){
 87             Add[l[j]]++;Add[r[j]+1]--;
 88         }
 89         int add = 0;
 90         for(int j = 1;j<=n;j++){
 91             add += Add[j];
 92             cnt[i][j] += add;
 93         }
 94         for(int j = 1;j<=n;j++)
 95             sum[i] += 1uLL * a[j] * cnt[i][j];
 96 //        for(int j = 1;j<=n;j++)
 97 //            cout << cnt[i][j] <<" ";cout << endl;
 98 //        cout << sum[i] << endl;
 99     }
100     int q;scanf("%d", &q);
101     while(q--){
102         int op;scanf("%d", &op);
103         if(op==1){
104             int x, y;scanf("%d%d", &x, &y);
105             for(int i = 1;i<=num;i++)
106                 sum[i] -= 1uLL * a[x] * cnt[i][x];
107             add(x, y-a[x]);
108             a[x] = y;
109             for(int i = 1;i<=num;i++)
110                 sum[i] += 1uLL * a[x] * cnt[i][x];
111         }else{
112             int x, y;
113             scanf("%d%d", &x, &y);
114             uLL ans = Query(y) - Query(x-1);
115             printf("%llu\n", ans);
116         }
117     }
118     return 0;
119 }

时间: 07-23

CodeChef FNCS (分块+树状数组)的相关文章

【bzoj3744】Gty的妹子序列 分块+树状数组+主席树

题目描述 我早已习惯你不在身边, 人间四月天 寂寞断了弦. 回望身后蓝天, 跟再见说再见…… 某天,蒟蒻Autumn发现了从 Gty的妹子树(bzoj3720) 上掉落下来了许多妹子,他发现 她们排成了一个序列,每个妹子有一个美丽度. Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间 [l,r]中妹子们美丽度的逆序对数吗?" 蒟蒻Autumn只会离线乱搞啊……但是Bakser神犇说道:"强制在线." 请你帮助一下Autumn吧.

【BZOJ4167】永远的竹笋采摘 分块+树状数组

[BZOJ4167]永远的竹笋采摘 题解:我们考虑有多少点对(a,b)满足a与b的差值是[a,b]中最小的.以为是随机数据,这样的点对数目可能很少,实测是O(n)级别的,那么我们已知了有这么多可能对答案造成贡献的点对,如何将它们求出来呢? 考虑分块,因为所有数大小在[1,n]中,我们可以对于每个块,预处理出整个块到所有数的最小差值.然后从右往左枚举每一个点,再枚举右面所有的块,如果这个块到当前数的差值比之前的要小,那就暴力进入块中扫一遍.与此同时,我们需要知道是否已经存在这样的点对,被当前的点对

hdu5057 分块处理,当数值大于数据范围时树状数组 真是巧 将大数据分为小数据来处理

这题说的给了100000个数有100000次操作 询问 L和R 区间内 在D位上为P的个数,用树状数组存 要开[10][10][100000]的int 开不了但是能开 这么大的unsign short 这样我们将这个树状数组一分为二 50000 个位前面 50000 为后面 我们知道unshort 范围在60000多显然这样是可以开的了 #include <iostream> #include <cstdio> #include <string.h> using nam

BZOJ 3289: Mato的文件管理[莫队算法 树状数组]

3289: Mato的文件管理 Time Limit: 40 Sec  Memory Limit: 128 MBSubmit: 2399  Solved: 988[Submit][Status][Discuss] Description Mato同学从各路神犇以各种方式(你们懂的)收集了许多资料,这些资料一共有n份,每份有一个大小和一个编号.为了防止他人偷拷,这些资料都是加密过的,只能用Mato自己写的程序才能访问.Mato每天随机选一个区间[l,r],他今天就看编号在此区间内的这些资料.Mat

BZOJ3295 动态逆序对 树套树, 树状数组套线段树(主席树)

Orz黄学长,蒟蒻在黄学长的带领下,通过阅读黄学长的代码!终于会了这道题! 首先我想先说一下这道题的思路(准确来说是黄学长的). 很明显,树状数组应该不用讲吧!关键是内存怎么开,维护一些什么样的数据? 其实我们通过观察,很快可以发现,你维护被删的数比维护所有的数轻松多了(不管是空间上,还是时间上).所以我们就可以从这方面想!(其实我一开始的思路,因为这道题我已经看过很久了,一直想写,毕竟是白书里面的一道例题嘛!一开始,蒟蒻的我是打算这样的用树状数组套权值线段树,并且是维护所有的数,我发现空间不够

【转】关于LIS和一类可以用树状数组优化的DP 预备知识

原文链接 http://www.cnblogs.com/liu-runda/p/6193690.html 预备知识 DP(Dynamic Programming):一种以无后效性的状态转移为基础的算法,我们可以将其不严谨地先理解为递推.例如斐波那契数列的递推求法可以不严谨地认为是DP.当然DP的状态也可以是二维/三维的,某一维的含义也不仅仅是指某个数列的第几项. 树状数组(BIT or fenwick tree):一种高效地动态维护一个序列并动态求取前缀和的数据结构.修改某个元素/求一次前缀和的

[noip科普]关于LIS和一类可以用树状数组优化的DP

预备知识 DP(Dynamic Programming):一种以无后效性的状态转移为基础的算法,我们可以将其不严谨地先理解为递推.例如斐波那契数列的递推求法可以不严谨地认为是DP.当然DP的状态也可以是二维/三维的,某一维的含义也不仅仅是指某个数列的第几项. 树状数组(BIT or fenwick tree):一种高效地动态维护一个序列并动态求取前缀和的数据结构.修改某个元素/求一次前缀和的时间复杂度均为O(logn) 2 LIS 好了现在假设你们都会打树状数组了(如果不会的话,baidu一发吧

HDU 5542 The Battle of Chibi dp+树状数组

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5542 题意:给你n个数,求其中上升子序列长度为m的个数 可以考虑用dp[i][j]表示以a[i]结尾的长度为j的上升子序列有多少 裸的dp是o(n2m) 所以需要优化 我们可以发现dp的第3维是找比它小的数,那么就可以用树状数组来找 这样就可以降低复杂度 #include<iostream> #include<cstdio> #include<cstring> #include

(POJ 3067) Japan (慢慢熟悉的树状数组)

Japan Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 29295   Accepted: 7902 Description Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coas