hdu-3333 Turing Tree 离线区间+树状数组（区间不同数的和）

时间：2022-05-07 11:30:05

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3333

题目大意：

给出一数组，以及m个查询区间，每次查询该区间不同数字的和。相同数字只加一次。

解题思路：

离线区间，按照区间右端点进行排序。

这样可以从左到右扫一遍，用尺取法一个一个将数字放入树状数组中。

如果这个数字已经在树状数组里面，记录之前的下标，再从树状数组中删去之前下标的这个数字，在当前下标添加该数字。这样可以保证每一步操作，都会使得树状数组中没有重复元素。这样可以直接用树状数组求不同数字的和。

求区间种类数也是这样做。

 #include<bits/stdc++.h>

 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Mem(a) memset(a, 0, sizeof(a))

 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))

 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 typedef long long ll;

 const int maxn =  + ;

 const int MOD = ;//const引用更快，宏定义也更快

 ll a[maxn];//树状数组

 ll c[maxn];//原数组

 map<ll, int>Last;//记录上一次出现该值的下标

 int n;

 int lowbit(int x)

 {

     return x & (-x);

 }

 //向后修改某一点的值

 void add(int x, ll d)

 {

     //cout<<x<<" "<<d<<endl;

     while(x <= n)

     {

         a[x] += d;

         x += lowbit(x);

     }

 }

 //向前统计[1, x]的区间和

 ll sum(int x)

 {

     ll ret = ;

     while(x > )

     {

         ret += a[x];

         x -= lowbit(x);

     }

     return ret;

 }

 struct node

 {

     int l, r;

     int id;

     node(){}

     bool operator < (const node& a)const

     {

         return r < a.r;

     }

 }cnt[maxn];//离线区间

 ll ans[maxn];

 int main()

 {

     int T, cases = ;

     scanf("%d", &T);

     while(T--)

     {

         Last.clear();

         Mem(a);

         int m;

         scanf("%d", &n);

         for(int i = ; i <= n; i++)scanf("%lld", &c[i]);

         scanf("%d", &m);

         for(int i = ; i <= m; i++)scanf("%d%d", &cnt[i].l, &cnt[i].r), cnt[i].id = i;

         sort(cnt + , cnt +  + m);

         int pre = ;

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

         {

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

             {

                 if(Last[c[j]])//之前出现过

                 {

                     add(Last[c[j]], -c[j]);

                 }

                 add(j, c[j]);

                 Last[c[j]] = j;

             }

             pre = cnt[i].r + ;

             ans[cnt[i].id] = sum(cnt[i].r) - sum(cnt[i].l - );

         }

         for(int i = ; i <= m; i++)printf("%lld\n", ans[i]);

     }

     return ;

 }

相关文章