题解 P4113 【[HEOI2012]采花】

树状数组+离线 以询问的右节点排序，考虑左节点对答案的贡献 枚举右端点，到达一个颜色k，记$pre[k]$为当前颜色k前面的第一个颜色k，记$pp[k]$表示当前颜色k前面的第二个颜色k，那么当右端点到达k的时候，将区间$(pp_k, pre_k]$加一即可，（因为左节点在这一段的时候这种颜色会有贡献。 可以用常数小的树状数组维护差分数组，相当于有了单点查询区间修改的功能。 此题卡常，请开O2或者读优 代码： ```cpp #include<bits/stdc++.h> #define Re register #define fo(i, a, b) for (Re int i = (a); i <= (b); ++i) #define fd(i, a, b) for (Re int i = (a); i >= (b); --i) #define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v) #define pb push_back #define F first #define S second #define ll long long #define inf 10000000000007 #define mp std::make_pair #define lowbit(x) (x & -x) #define eps 1e-4 #define itset std::set<node>::iterator #define lb lower_bound #define N 2000005 #define ls (k << 1) #define rs (k << 1 | 1) #define M 260 int n, m, c, a[N], pre[N], ans[N], pp[N]; struct node{ int l, r, id; friend bool operator < (node x, node y) { return x.r < y.r; } }q[N]; int t[N]; inline void add (int x, int val) {for (int i = x; i <= n; i += lowbit(i)) t[i] += val;} inline int query (int x) {int ret = 0; for (int i = x; i; i -= lowbit(i)) ret += t[i]; return ret;} int main () { scanf("%d %d %d", &n, &c, &m); fo (i, 1, n) scanf("%d", &a[i]); fo (i, 1, m) { scanf("%d %d", &q[i].l, &q[i].r); q[i].id = i; } std::sort(q + 1, q + m + 1); int j = 1; fo (i, 1, n) { add(pre[a[i]] + 1, -1); add(pp[a[i]] + 1, 1); // printf("%d %d +1\n", pp[a[i]] + 1, pre[a[i]]); pp[a[i]] = pre[a[i]]; pre[a[i]] = i; while (q[j].r == i) { ans[q[j].id] = query(q[j].l); ++j; } } fo (i, 1, m) printf("%d\n", ans[i]); return 0; } ```