洛谷P1972 HH的项链【树状数组】

题目：https://www.luogu.org/problemnew/show/P1972

题意：给定一个长度为n的序列，数字表示珠子的种类。m次查询每次询问给定区间内珠子的种类数。

思路：可以说是运用了前缀和的思想吧。从前到后的去处理查询，而对于某一个查询区间，如果某一个种类出现了多次的话我们只需要计算最后一次出现。

用query(x)表示1~x区间内的种类数，其中对每个种类我们只标记最后一次出现。也就是说顺序遍历的时候如果又出现了就把前面的清空，标记当前位置。

如果查询的区间是l~r那么答案就是query(r) - query(l - 1)。

所以首先需要把查询按照右端点从小到大排序。每次只需要更新上一次右端点到这一次右端点这一段区间，同时要标记每一个种类最近一次出现的位置，用于清空。

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n, m;

 const int maxn = 5e5 + ;

 struct node{

     int l, r, id, ans;

 }q[maxn];

 int neck[maxn];

 int sum[maxn << ];

 const int maxnum = 1e6 + ;

 int pos[maxnum];

 bool cmp(node a, node b)

 {

     return a.r < b.r;

 }

 bool cmp1(node a, node b)

 {

     return a.id < b.id;

 }

 void add(int rt, int val)

 {

     while(rt <= n){

         sum[rt] += val;

         rt += (rt & -rt);

     }

 }

 int query(int rt)

 {

     int ans = ;

     while(rt){

         ans += sum[rt];

         rt -= (rt & -rt);

     }

     return ans;

 }

 int main()

 {

     scanf("%d", &n);

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

         scanf("%d", &neck[i]);

     }

     scanf("%d", &m);

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

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

         q[i].id = i;

     }

     sort(q, q + m, cmp);

     int nxt = ;

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

         int r = q[i].r;

         for(int j = nxt; j <= r; j++){

             if(pos[neck[j]]){

                 add(pos[neck[j]], -);

             }

             add(j, );

             pos[neck[j]] = j;

         }

         nxt = r + ;

         q[i].ans = query(q[i].r) - query(q[i].l - );

     }

     sort(q, q + m, cmp1);

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

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

     }

     return ;

 }

巴特西

洛谷P1972 HH的项链【树状数组】

最新文章

热门文章