本文共 1527 字，大约阅读时间需要 5 分钟。
题目链接：
题意就是询问区间不同数字的和。
比较经典的树状数组应用。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std;14 typedef long long LL;15 typedef pair 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 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 }
转载于:https://www.cnblogs.com/Recoder/p/5910570.html