Note: This article is available in Chinese only. 本文暂无英文版本。
View original
树状数组，更新区间，查询单点，区别是加了一个a%k==0的条件限制…. 我们观察到k很小，于是按照k分类…. 每一类再按照余数分类，一共55棵树（1+2+3+…+10）
然后写完交上去，竟然MLE了。。。 13×1350007 我一开始也想到了是开大了。。。然后改成了111150004，结果还是mle.. 然后我就把代码贴到群里问了。。。。 然后就被打脸了。。。 被这顿嘲讽啊。。。 由于我的vim不知道什么原因，要复制两次才能复制上去。。。 就是说，改成了111150004的代码并没有提交上去，第二次mle还是1313*50007。。 不过也算一个经验：对于低维度（一维）数组，稍微开大点对空间影响不会很大… 但是高维，稍微开大一点，就会极大的影响空间….因为是乘起来的。 因为之前很少遇到高维，而且数组比较大的情况，所以没有太注意。 也说明把数组开大一点就好，一点点。
代码是按照hdu 4267 写的 poj 3468和这个差不多，就是读入顺序和op的写法不太一样。 另：某博客看到的tips，虽然我也知道这个，但我觉得他表达得比较清楚… Tips：
树状数组的优势是方便动态求值和更新..
可惜树状数组是单点更新
倒是有个方法可以快速成段更新
就是在区间【a, b】内更新+x就在a的位置+x 然后在b+1的位置-x
求某点a的值就是求数组中1~a的和..
可惜这道题还不是成段更新..而是隔开几个数来更新..
所以就可以多建几棵树..然后就可以转换为成段更新了~~
代码实现
1
2/****....*********************************************************************
3 > File Name: code/hdu/4267.cpp
4 > Author: 111qqz
5 > Email: rkz2013@126.com
6 > Created Time: 2015年08月07日 星期五 14时27分58秒
7 ************************************************************************/
8
9#include<iostream>
10#include<iomanip>
11#include<cstdio>
12#include<algorithm>
13#include<cmath>
14#include<cstring>
15#include<string>
16#include<map>
17#include<set>
18#include<queue>
19#include<vector>
20#include<stack>
21#define y0 abc111qqz
22#define y1 hust111qqz
23#define yn hez111qqz
24#define j1 cute111qqz
25#define tm crazy111qqz
26#define lr dying111qqz
27using namespace std;
28#define REP(i, n) for (int i=0;i<int(n);++i)
29typedef long long LL;
30typedef unsigned long long ULL;
31const int inf = 0x7fffffff;
32const int N=5E4+3;
33int c[N][11][11];
34int a[N];
35int n,m,k,del,x,q,y;
36bool flag;
37int lowbit( int x)
38{
39 return x&(-x);
40}
41void update ( int a,int b,int x, int delta)
42{
43 for ( int i = x; i <= n ; i = i + lowbit (i))
44 {
45 c[i][a][b] += delta;
46 }
47}
48int sum ( int a,int b,int x)
49{
50 int res = 0;
51 for ( int i = x; i >= 1; i = i - lowbit (i))
52 {
53 res = res + c[i][a][b];
54 }
55 return res;
56}
57int main()
58{
59 while (scanf("%d",&n)!=EOF)
60 {
61 memset(c,0,sizeof(c));
62 flag = true;
63
64 for ( int i = 1 ;i <= n ; i++ )
65 {
66 scanf("%d",&a[i]);
67 }
68 scanf("%d",&q);
69 flag = false;
70 int op;
71 for ( int i = 1 ; i <= q ; i ++)
72 {
73 scanf("%d",&op);
74 if (op==1)
75 {
76 scanf("%d %d %d %d",&x,&y,&k,&del);
77 update (k,x%k,x,del);
78 update(k,x%k,y+1,-del);
79 }
80 else
81 {
82 scanf("%d",&x);
83 int ans = a[x];
84 for ( int i = 1 ; i <= 10 ; i++)
85 {
86 ans = ans +sum(i,x%i,x);
87 }
88 cout<<ans<<endl;
89 }
90 }
91 }
92 return 0;
93}