SPOJ3267--D-query （树状数组离线操作）

题意查询区间 [l,r]内有多少个不同的数字

先把所有询问按 右端点进行排序，然后离线操作。如果该位置的数字 已经出现过那么把前一个位置-1，当前位置+1。扫一遍输出。

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxq = 2e5+;

 const int maxn = 3e4+;

 int last[];

 int n,m,c[maxn],ans[];

 struct Node

 {

     int l,r,ans,idx;

     bool operator < (const Node &rhs)const

     {

         return r < rhs.r || (r == rhs.r && l < rhs.l);

     }

 }Q[maxq];

 int lowbit(int x)

 {

     return x & -x;

 }

 void add(int x,int d)

 {

     while (x <= maxn)

     {

         c[x] += d;

         x += lowbit(x);

     }

 }

 int sum(int x)

 {

     int ans = ;

     while (x)

     {

         ans += c[x];

         x -= lowbit(x);

     }

     return ans;

 }

 int a[maxq];

 int main(void)

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt","r",stdin);

     #endif

     while (~scanf ("%d",&n))

     {

         memset(c,,sizeof(c));

         memset(last,-,sizeof(last));

         for (int i = ; i <= n+; i++)

             scanf ("%d",a+i);

         scanf ("%d",&m);

         for (int i = ; i < m; i++)

         {

             Q[i].idx = i;

             scanf ("%d%d",&Q[i].l,&Q[i].r);

             Q[i].l++,Q[i].r++;

         }

         sort(Q,Q+m);

         int pre = ;

         for (int i = ; i < m; i++)

         {

             for(int j =  pre; j <= Q[i].r; j++)

             {

                 if (~last[a[j]])

                 {

                     add(last[a[j]],-);

                     add(j,);

                 }

                 else

                 {

                     add(j,);

                 }

                 last[a[j]] = j;

             }

             ans[Q[i].idx] = sum(Q[i].r) - sum(Q[i].l - );

             pre = Q[i].r+;

         }

         for (int i = ; i < m; i++)

             printf("%d\n",ans[i]);

     }

     return ;

 }

此题主席树也可以做。