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

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

• HH的项链这个题是静态区间查询的问题，如果用树状数组来解决，那么容易想到的方法是比如说问$[l,r]的$不同贝壳数量，那么我如果用树状数组维护区间的不同贝壳数，那么答案应该是$query(r)?query(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;
}