[BZOJ1878][SDOI2009]HH的项链
试题描述
输入
输出
M行，每行一个整数，依次表示询问对应的答案。
输入示例
6 1 2 3 4 3 5 3 1 2 3 5 2 6
输出示例
2 2 4
数据规模及约定
对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。
题解
找到每个颜色的前驱（即上一次出现在哪）并维护下来，那么询问时对于一个区间 [L, R]，若某个颜色为 c 的点的前驱小于 L，那么它是最靠前的颜色为 c 的点，显然，统计出有多少个“最靠前的某颜色的点的个数”，就能得到答案了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
return x * f;
}
#define maxn 50010
#define maxnode 1600010
#define maxc 1000010
int ToT, rt[maxn], sumv[maxnode], lc[maxnode], rc[maxnode];
void update(int& y, int x, int l, int r, int p) {
sumv[y = ++ToT] = sumv[x] + 1;
if(l == r) return ;
int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x];
if(p <= mid) update(lc[y], lc[x], l, mid, p);
else update(rc[y], rc[x], mid + 1, r, p);
return ;
}
int query(int o, int l, int r, int qr) {
if(!o) return 0;
if(r <= qr) return sumv[o];
int mid = l + r >> 1, ans = query(lc[o], l, mid, qr);
if(qr > mid) ans += query(rc[o], mid + 1, r, qr);
return ans;
}
int lstp[maxc];
int main() {
int n = read();
for(int i = 1; i <= n; i++) {
int col = read();
update(rt[i], rt[i-1], 0, n, lstp[col]);
lstp[col] = i;
}
int q = read();
while(q--) {
int ql = read(), qr = read();
printf("%d\n", query(rt[qr], 0, n, ql - 1) - query(rt[ql-1], 0, n, ql - 1));
}
return 0;
}
原文：http://www.cnblogs.com/xiao-ju-ruo-xjr/p/6358108.html