給出q個詢問，詢問一段區間里面的不同元素的個數有多少個。

離線做，用樹狀數組。

設樹狀數組的意義是：1--pos這個段區間的不用元素的種類數。怎么做？就是add(pos,1);在這個位置中+1，就是說這個位置上元素種類+1。

然后先把詢問按R遞增的順序排序。因為這里是最優的，我每次盡量往R靠，使得查詢不重不漏。

什么意思呢？

就是假如有：2、1、3、5、1、7的話。

一開始的[1,4]這段數字全部壓進樹狀數組，用個數組book[val]，表示val這個元素出現的最右的位置，因為我們需要刪除重復的，也是要盡量往右靠。到達pos=5這個位置的時候，注意了，因為1是出現過的book[1] = 2，所以我們要做的是把2這個位置出現元素的種類數-1，就是add(book[1],-1)。然后把第五個位置出現的元素種類數+1，就是add(5,1)。為什么呢？因為你盡量把種類往右靠，因為我們的R是遞增的，這樣，你使得查詢[4,6]成為可能，因為我那個1加入來了，而不是一直用pos=2那個位置的1，再者，查詢[4,7]的話，一樣的意思，因為中間的1進來了。所以我們因為盡量往右靠，畢竟我們都把query按R排序了。

還有這個只能離線，一直預處理ans[i]表示第i個詢問的ans。更新到[4,7]后，查詢[1,2]已經不可能了，因為很明顯，pos=2這個位置已經被刪除了。

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1e6+20; int book[maxn]; int c[maxn];//樹狀數組，多case的記得要清空 int n; //我只需記錄這個位置是不是新元素，不用離散 int lowbit (int x)//得到x二進制末尾0的個數的2次方 2^num {return x&(-x); } void add (int pos,int val)//在第pos位加上val這個值 {while (pos<=n) //n是元素的個數 {c[pos] += val; pos += lowbit(pos);}return ; } int get_sum (int pos) //求解：1--pos的總和 {int ans = 0;while (pos){ans += c[pos]; pos -= lowbit(pos);}return ans; } int a[maxn]; struct node {int L,R,id;bool operator < (const struct node &rhs) const{if (R != rhs.R) return R < rhs.R;else return L < rhs.L;} }query[maxn]; int ans[maxn]; void work () {scanf("%d",&n);for (int i=1;i<=n;++i) scanf("%d",&a[i]);//樹狀數組含義：1--pos間的不同元素種類數int q; scanf("%d",&q);for (int i=1;i<=q;++i){scanf("%d%d",&query[i].L,&query[i].R);query[i].id = i; //記錄ans }sort(query+1,query+1+q);int cur = 1;//book[val]的含義，val這個元素出現的最右邊的位置for (int i=1;i<=q;++i){for (int j=cur;j<=query[i].R;++j){if (book[a[j]]) //這個元素在之前位置出現過，我們盡量往右，所以先刪除那個位置的種類數，更新現在這個位置的種類數。因為這樣的話，使得查詢[4,5]是可能的add(book[a[j]],-1); //del 這個位置book[a[j]]=j; //更新這個位置的最右值add(j,1); //這個位置出現了新元素 }cur = query[i].R+1;ans[query[i].id] = get_sum(query[i].R) - get_sum(query[i].L-1);}for (int i=1;i<=q;++i)printf ("%d\n",ans[i]); }int main() { #ifdef localfreopen("data.txt","r",stdin); #endifwork();return 0; } View Code

?

HDU 3333?Turing Tree

一樣的，只不過是求元素的和。。把add那里的val改成a[i]即可，幻想它出現了val次，一統計，就是了。

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 30000 + 20; LL c[maxn];//樹狀數組，多case的記得要清空 int n; LL a[maxn]; struct node {int L,R,id;bool operator < (const struct node &rhs) const{return R < rhs.R;} }query[2*100000]; LL ans[2*100000]; map<LL,int>book; int lowbit (int x)//得到x二進制末尾0的個數的2次方 2^num {return x&(-x); } void add (int pos,LL val)//在第pos位加上val這個值 {while (pos<=n) //n是元素的個數 {c[pos] += val; pos += lowbit(pos);}return ; } LL get_sum (int pos) //求解：1--pos的總和 {LL ans = 0;while (pos){ans += c[pos]; pos -= lowbit(pos);}return ans; } void init () {memset(c,0,sizeof c);book.clear();return ; } void work () {init();scanf("%d",&n);for (int i=1;i<=n;++i) scanf("%I64d",&a[i]);int q;scanf ("%d",&q);for (int i=1;i<=q;++i){scanf("%d%d",&query[i].L,&query[i].R);query[i].id = i;}sort(query+1,query+1+q);int cur=1;for (int i=1;i<=q;++i){for (int j=cur;j<=query[i].R;++j){int t = book[a[j]];if (t){add(t,-a[j]);}book[a[j]]=j;add(j,a[j]);}cur = query[i].R+1;ans[query[i].id] = get_sum(query[i].R) - get_sum(query[i].L-1);}for (int i=1;i<=q;++i){printf ("%I64d\n",ans[i]);} }int main() { #ifdef localfreopen("data.txt","r",stdin); #endifint t;scanf ("%d",&t);while (t--) work();return 0; } View Code

?

轉載于:https://www.cnblogs.com/liuweimingcprogram/p/5805076.html

總結

以上是生活随笔為你收集整理的SPOJ 3267: DQUERY 树状数组，离线算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。