首页 > 代码库 > 【HDU4991】树状数组
【HDU4991】树状数组
http://acm.hdu.edu.cn/showproblem.php?pid=4991
用f[i][j] 表示 前i个数以第i个数结尾的合法子序列的个数，则递推式不难写出：
f[i][j] = sum(f[k][j - 1]); 其中 k < i, 且a[k] < a[i]; 边界：f[i][1] = 1; 显然需要用数据结构来优化查询
如果不考虑离散的话，用一个数据结构，记录节点为a[i]的f值，同时维护一个区间f值之和，那么f[i][j] = query(0, a[i] - 1)；然后考虑特定的顺序用f值更新数据结构中的信息
具体见代码（树状数组）：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 #include <stack> 8 #include <string> 9 #define mem0(a) memset(a, 0, sizeof(a))10 #define mem(a, b) memset(a, b, sizeof(a))11 #define lson l, m, rt << 112 #define rson m + 1, r, rt << 1 | 113 #define lr rt << 114 #define rr rt << 1 | 115 #define eps 0.000116 #define lowbit(x) ((x) & -(x))17 #define memc(a, b) memcpy(a, b, sizeof(b))18 typedef char Str[120];19 using namespace std;20 #define LL long long21 #define DL double22 23 map<int, int> Hash;24 int mol = 123456789;25 int a[12000], f[12000][120], b[12000], R[12000], c[120000], N, n, m;26 27 void init()28 {29 sort(a + 1, a + 1 + n);30 N = 0;31 for(int i = 1; i <= n; i++) {32 if(a[i] == a[i - 1] && i > 1) continue;33 Hash[a[i]] = ++N;34 }35 }36 int query(int p)37 {38 int ans = 0;39 while(p) {40 ans += c[p];41 if(ans >= mol) ans -= mol;42 p -= lowbit(p);43 }44 return ans;45 }46 void update(int p, int x)47 {48 while(p <= N) {49 c[p] += x;50 if(c[p] >= mol) c[p] -= mol;51 p += lowbit(p);52 }53 }54 int main()55 {56 //freopen("input.txt", "r", stdin);57 //freopen("output.txt", "w", stdout);58 while(~scanf("%d%d", &n, &m)) {59 for(int i = 1; i <= n; i++) {60 scanf("%d", a + i);61 }62 memc(b, a);63 init();64 mem0(f);65 //puts("d");66 for(int i = 1; i <= n; i++) f[i][1] = 1;67 for(int i = 1; i <= n; i++) R[i] = Hash[b[i]];68 for(int j = 2; j <= m; j++) {69 mem0(c);70 for(int i = 1; i <= n; i++) {71 f[i][j] = query(R[i] - 1);72 update(R[i], f[i][j - 1]);73 //cout<< i<< " "<< j<< " "<< f[i][j]<< endl;74 }75 }76 int ans = 0;77 for(int i = m; i <= n; i++) {78 ans += f[i][m];79 if(ans >= mol) ans -= mol;80 }81 cout<< ans<< endl;82 }83 return 0;84 }
另外用线段树写了一下， 不过超时（2000+ms）了，线段树才不到500ms，由此可见能用树状数组决不用线段树，递归线段树常数太大了
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 #include <stack> 8 #include <string> 9 #define mem0(a) memset(a, 0, sizeof(a)) 10 #define mem(a, b) memset(a, b, sizeof(a)) 11 #define lson l, m, rt << 1 12 #define rson m + 1, r, rt << 1 | 1 13 #define lr rt << 1 14 #define rr rt << 1 | 1 15 #define eps 0.0001 16 #define lowbit(x) ((x) & -(x)) 17 #define memc(a, b) memcpy(a, b, sizeof(b)) 18 typedef char Str[120]; 19 using namespace std; 20 #define LL long long 21 #define DL double 22 struct seg{ 23 int sum; 24 }tree[12000 << 2]; 25 map<int, int> Hash; 26 int mol = 123456789; 27 int a[12000], f[12000][120], b[12000], R[12000], N, n, m; 28 29 void init() 30 { 31 sort(a + 1, a + 1 + n); 32 N = 0; 33 for(int i = 1; i <= n; i++) { 34 if(a[i] == a[i - 1] && i > 1) continue; 35 Hash[a[i]] = ++N; 36 } 37 } 38 void build(int l, int r, int rt) 39 { 40 tree[rt].sum = 0; 41 if(l == r) return; 42 int m = (l + r) >> 1; 43 build(lson); 44 build(rson); 45 } 46 void pushUP(int rt) 47 { 48 tree[rt].sum = tree[rt << 1].sum + tree[rt<< 1 | 1].sum; 49 if(tree[rt].sum >= mol) tree[rt].sum -= mol; 50 } 51 void update(int p, int x, int l, int r, int rt) 52 { 53 if(l == r) { 54 tree[rt].sum += x; 55 if(tree[rt].sum >= mol) tree[rt].sum -= mol; 56 return; 57 } 58 int m = (l + r) >> 1; 59 if(p <= m) update(p, x, lson); 60 else update(p, x, rson); 61 pushUP(rt); 62 } 63 int query(int L, int R, int l, int r, int rt) 64 { 65 if(L <= l && r <= R) { 66 return tree[rt].sum; 67 } 68 int m = (l + r) >> 1, res = 0; 69 if(L <= m) res+= query(L, R, lson); 70 if(R > m) res += query(L, R, rson); 71 if(res >= mol) res -= mol; 72 return res; 73 } 74 int main() 75 { 76 //freopen("input.txt", "r", stdin); 77 //freopen("output.txt", "w", stdout); 78 while(~scanf("%d%d", &n, &m)) { 79 for(int i = 1; i <= n; i++) { 80 scanf("%d", a + i); 81 } 82 memc(b, a); 83 init(); 84 mem0(f); 85 //puts("d"); 86 for(int i = 1; i <= n; i++) f[i][1] = 1; 87 for(int i = 1; i <= n; i++) R[i] = Hash[b[i]]; 88 for(int j = 2; j <= m; j++) { 89 build(1, N, 1); 90 for(int i = 1; i <= n; i++) { 91 if(R[i] > 1) f[i][j] = query(1, R[i] - 1, 1, N, 1); 92 update(R[i], f[i][j - 1], 1, N, 1); 93 } 94 } 95 int ans = 0; 96 for(int i = m; i <= n; i++) { 97 ans += f[i][m]; 98 if(ans >= mol) ans -= mol; 99 }100 cout<< ans<< endl;101 }102 return 0;103 }
【HDU4991】树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。