[SDOI2009]HH的项链和 [HEOI2012]采花两题树状数组解法对比分析

本文主要是介绍[SDOI2009]HH的项链和 [HEOI2012]采花两题树状数组解法对比分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.luogu.com.cn/problem/P1972

HH的项链这个题是静态区间查询的问题，如果用树状数组来解决，那么容易想到的方法是比如说问 $[l, r] 的$ 不同贝壳数量，那么我如果用树状数组维护区间的不同贝壳数，那么答案应该是 $q u e r y (r) - q u e r y (l - 1)$ ，但是这里带来一个问题，就是 $[1, l]$ 和 $[1, r]$ 这两个区间里面不能有重复的贝壳，否则就会出错，那如何来解决呢？
一个办法就是记录当前贝壳的上一次出现的位置,如果当前贝壳不是第一次出现，那么把它上一次出现的位置所对应的树状数组的值 $- 1$ ，这次出现的位置所对应的树状数组的值 $+ 1$ ，但这同样存在一个问题，如果你询问右端点在上一个出现位置前面怎么办？所以我们要先把查询时候的右端点按照从小到大的顺序排个序，然后就可以进行上述操作了，每次查询完毕就记录答案

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 2e6 + 100;
const int INF = 0x3f3f3f3f;
int Data[MAXN];
int a[MAXN];
int n, m;
struct st{int l, r;int id;bool operator< (st &x)const {return r < x.r;}
}s[MAXN];
int lowbit(int x){return x & -x;
}
void ADD(int x, int val){while(x <= n){Data[x] += val;x += lowbit(x);}
}
int query(int x){int res = 0;while(x > 0){res += Data[x];x -= lowbit(x);}return res;
}
int last[MAXN], pre[MAXN];
int ans[MAXN];
int main(){#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endifios::sync_with_stdio(false);cin >> n;for(int i=1;i<=n;i++){cin >> a[i];pre[i] = last[a[i]];last[a[i]] = i;}cin >> m;for(int i=1;i<=m;i++){cin >> s[i].l >> s[i].r;s[i].id = i;}sort(s + 1, s + 1 + m);int now = 1;for(int i=1;i<=m;i++){while(now <= s[i].r){if(pre[now]){ADD(pre[now], -1);}ADD(now, 1);++now;}ans[s[i].id] = query(s[i].r) - query(s[i].l - 1);}for(int i=1;i<=m;i++){cout << ans[i] << '\n';}return 0;
}

https://www.luogu.com.cn/problem/P4113

这个题问的也是种类数，也是静态区间查询问题，查询区间之间也是独立的，但是和上一个题的区别是必须有两个以上的同种颜色的花才能算数，这样的话我们可以再记录一个前驱的前驱，查询的时候先让前驱所对应的树状数组的值 $+ 1$ ，前驱的前驱所对应树状数组的值 $- 1$ ，当然前驱和前驱的前驱必须存在才能做相关操作

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 2e6 + 100;
const int INF = 0x3f3f3f3f;
int Data[MAXN];
int a[MAXN];
int n, c, m;
struct st{int l, r;int id;bool operator< (st &x)const {return r < x.r;}
}s[MAXN];
int lowbit(int x){return x & -x;
}
void ADD(int x, int val){while(x <= n){Data[x] += val;x += lowbit(x);}
}
int query(int x){int res = 0;while(x > 0){res += Data[x];x -= lowbit(x);}return res;
}
int last[MAXN], pre[MAXN], prepre[MAXN];
int ans[MAXN];
int main(){#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endifios::sync_with_stdio(false);cin >> n >> c >> m;for(int i=1;i<=n;i++){cin >> a[i];pre[i] = last[a[i]];last[a[i]] = i;prepre[i] = pre[pre[i]];}for(int i=1;i<=m;i++){cin >> s[i].l >> s[i].r;s[i].id = i;}sort(s + 1, s + 1 + m);int now = 1;for(int i=1;i<=m;i++){while(now <= s[i].r){if(pre[now]){ADD(pre[now], 1);}if(prepre[now]){ADD(prepre[now], -1);}++now;}ans[s[i].id] = query(s[i].r) - query(s[i].l - 1);}for(int i=1;i<=m;i++){cout << ans[i] << '\n';}return 0;
}