首页 > 代码库 > HDU 3333 Turing Tree (树状数组)
HDU 3333 Turing Tree (树状数组)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3333
题意就是询问区间不同数字的和。
比较经典的树状数组应用。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e5 + 5;17 struct query {18 int l, r, pos;19 bool operator <(const query &cmp) const {20 return r < cmp.r;21 }22 }q[N];23 int a[30005];24 LL bit[30005], ans[N];25 map <int, int> mp;26 27 void update(int i, LL val) {28 for( ; i <= 30000; i += (i&-i))29 bit[i] += val;30 }31 32 LL sum(int i) {33 LL s = 0;34 for( ; i >= 1; i -= (i&-i))35 s += (LL)bit[i];36 return s;37 }38 39 int main()40 {41 int t, n, m;42 scanf("%d", &t);43 while(t--) {44 memset(bit, 0, sizeof(bit));45 mp.clear();46 scanf("%d", &n);47 for(int i = 1; i <= n; ++i) {48 scanf("%d", a + i);49 }50 scanf("%d", &m);51 for(int i = 1; i <= m; ++i) {52 scanf("%d %d", &q[i].l, &q[i].r);53 q[i].pos = i;54 }55 sort(q + 1, q + m + 1);56 int index = 1;57 for(int i = 1; i <= n; ++i) {58 if(mp.find(a[i]) != mp.end()) { //a[i]曾经出现过59 update(mp[a[i]], (LL)-a[i]);60 }61 mp[a[i]] = i;62 update(i, a[i]);63 while(q[index].r == i && index <= m) {64 ans[q[index].pos] = sum(q[index].r) - sum(q[index].l - 1);65 ++index;66 }67 }68 for(int i = 1; i <= m; ++i) {69 printf("%lld\n", ans[i]);70 }71 }72 return 0;73 }
HDU 3333 Turing Tree (树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。