解題思路：這道題和之前的題一樣，查找[l,r]區(qū)間內(nèi)不重復數(shù)字的和。可以利用離線算法，實際上離線算法為了解決在查找時出現(xiàn)的矛盾，因為每次詢問的區(qū)間大小不同，如果單獨處理的話可能會對之后的查詢有影響，所以離線算法幫助我們把要查詢的區(qū)間先按照右端點進行排序，因為在處理更靠右的區(qū)間時，比它小的區(qū)間肯定是已經(jīng)得到的不重復的數(shù)了，所以不會影響到后面的查找。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int M = 200005; const int N = 50005; struct Query {int l,r,id;bool operator < (Query a){return r < a.r;} }q[M]; int n,m,size; int tree[N<<1],arr[N],tmp[N],last[N],ans[M];int lowbit(int x) {return x & -x; }void update(int x,int d) {for(int i = x; i <= n; i += lowbit(i))tree[i] += d; }int getsum(int x) {int sum = 0;for(int i = x; i > 0; i -= lowbit(i))sum += tree[i];return sum; }int bisearch(int val) {int l = 1, r = size, mid;while(l <= r){mid = (l + r) >> 1;if(tmp[mid] == val) return mid;else if(tmp[mid] > val)r = mid - 1;else l = mid + 1;} }int main() {int t;cin >> t;while(t--){cin >> n;for(int i = 1; i <= n; i++){cin >> arr[i];tmp[i] = arr[i];}cin >> m;for(int i = 1; i <= m; i++){cin >> q[i].l >> q[i].r;q[i].id = i;}sort(tmp+1,tmp+1+n);sort(q+1,q+1+m);//離散化size = 1;for(int i = 2; i <= n; i++)if(tmp[i] != tmp[i-1])tmp[++size] = tmp[i];memset(tree,0,sizeof(tree));memset(last,0,sizeof(last));int idx = 1;for(int i = 1; i <= n; i++){int x = bisearch(arr[i]);if(last[x])update(last[x],-arr[i]);update(i,arr[i]);last[x] = i;while(q[idx].r == i && idx <= m){ans[q[idx].id] = getsum(q[idx].r) - getsum(q[idx].l - 1);idx++;}}for(int i = 1; i <= m; i++)cout << ans[i] << endl;}return 0; }

總結

以上是生活随笔為你收集整理的hdu 3874（树状数组+离线算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。