首页

# 统计区间不同颜色数

[SDOI2009] HH 的项链

# 题意

给出一个颜色序列，每次询问区间[L,R][L, R] 的不同颜色数，数据范围都 1e6。

# 思路

离线处理，按右端点排序。有两个位置颜色相同时，记录靠右的地方。

  • 从左到右扫一遍颜色数组。
    • 当前位置的颜色没出现过：树状数组这个位置 + 1
    • 当前位置的颜色出现过：上一个位置 -1， 这个位置 + 1
  • 若当前位置恰好是某一个查询的右端点，统计答案ans[i]=query(r)−query(l−1)ans[i] = query(r) - query(l - 1) 。（也就是为什么优先靠右记录）

核心代码：

sort(q + 1, q + m + 1, cmp1); // 右端点排序
int j = 1;
rep (i, 1, n)
{
	if (pos[a[i]])
	modify(pos[a[i]], -1);	// 出现过，现在不再统计原来的
    modify(i, 1); // 去统计新的
	pos[a[i]] = i;
	while (q[j].r == i) // 记得用 while
	{
		q[j].ans = query(q[j].r) - query(q[j].l - 1);
		j++;
	}
	if (j == m + 1)
		break;
}
sort(q + 1, q + m + 1, cmp2); // 按 id 排序
rep (i, 1, m)
	printf("%d\n", q[i].ans);

# 统计区间不同颜色数 ex

[HEOI2012] 采花

# 题意

跟上题一样，要求所查询区间内具有这个颜色的花至少有两朵。

# 思路

开两个数组 lst[col[i]]lst[col[i]] 和 llst[col[i]]llst[col[i]] 分别表示颜色 col[i]col[i] 在上次和上上次出现的时间。

要扩展区间右端点时，先看当前颜色有没有出现过。

出现过的话这样子： add(lst[col[i]], 1);

还有别忘了： add(llst[col[i]], -1); //如果llst不是0的话

也就是只有出现两次之后才会把前一次出现的位置对应 BIT 加一，大概不难想的样子 qwq

# 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int MAXN = 2e6 + 233;
int n, c, m;
int col[MAXN], tr[MAXN], lst[MAXN], llst[MAXN];
struct query
{
  int l, r, id, ans;
} q[MAXN];
bool cmp(query xx, query yy)
{
  return (xx.r == yy.r) ? xx.l < yy.l : xx.r < yy.r;
}
bool cmp2(query xx, query yy)
{
  return xx.id < yy.id;
}
int lb(int x)
{
  return (x) & (-x);
}
void add(int p, int v)
{
  for (; p <= n; p += lb(p))
    tr[p] += v;
}
int getsum(int p)
{
  int ans = 0;
  for (; p; p -= lb(p))
    ans += tr[p];
  return ans;
}
int main()
{
  //freopen("in.txt", "r", stdin);
  scanf("%d%d%d", &n, &c, &m); //n 点 c 颜色 (这个值在这个做法里好像没用 qwq) m 询问
  rep (i, 1, n)
    scanf("%d", &col[i]);
  rep (i, 1, m)
  {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + m + 1, cmp);
  int nowr = 1;
  rep (i, 1, m)
  {
    while (nowr <= q[i].r)
    {
      if (llst[col[nowr]])
        add(llst[col[nowr]], -1);
      if (lst[col[nowr]])
      {
        add(lst[col[nowr]], 1);
        llst[col[nowr]] = lst[col[nowr]];
        lst[col[nowr]] = nowr;
      }
      else
        lst[col[nowr]] = nowr;
      nowr++;
    }
    q[i].ans = getsum(q[i].r) - getsum(q[i].l - 1);
  }
  sort(q + 1, q + m + 1, cmp2);
  rep (i, 1, m)
    printf("%d\n", q[i].ans);
  return 0;
}