首页 > 代码库 > 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 (树状数组)