Gioush OJ
⌕ 题目搜索注册登录
P1044 · OFFICIAL SOLUTION

P1044 异色飞羽 官方题解

Gioush OJ · P1044 异色飞羽

异色飞羽

【题意简述】

给出长度为 nn 的颜色序列。每次询问区间 [l,r][l,r] 中出现了多少种不同颜色。

【Hint】

【提示】

将询问按右端点排序。扫描到位置 rr 时，只在每种颜色最后一次出现的位置保留一个 11。

【数据点 1∼101\sim 101∼10】

可以对每个询问扫描区间，并用集合或时间戳数组统计不同颜色。时间复杂度分别为 O(nqlog⁡n)\mathcal{O}(nq\log n) 与 O(nq)\mathcal{O}(nq)。

同一种颜色在一次询问中只需要贡献一次，因此真正需要维护的是每种颜色的一个代表位置。

【数据点 11∼1411\sim 1411∼14】

所有询问左端点均为 11。顺序扫描序列，第一次遇到某种颜色时把计数加一。询问 [1,r][1,r] 的答案就是扫描到 rr 时的计数。

【数据点 15∼1915\sim 1915∼19】

询问右端点单调不降。处理到 rr 时，只保留每种颜色在前缀 [1,r][1,r] 中最后一次出现的位置，并在这些位置放置 11。于是区间 [l,r][l,r] 的不同颜色数就是区间权值和。

【正解】

一般询问的右端点没有顺序，先把询问按 rr 从小到大排序，再沿用上一档的维护过程。

加入位置 ii 时，若颜色 aia_i 上一次出现在 Last⁡(ai)\operatorname{Last}(a_i)，先在旧位置减一，再在位置 ii 加一，最后令 Last⁡(ai)=i\operatorname{Last}(a_i)=i。此时树状数组中每种已经出现的颜色恰好有一个 11，并且位于其最后出现位置。

对于询问 [l,r][l,r]，某种颜色在区间中出现，当且仅当它在前缀 [1,r][1,r] 中的最后出现位置不小于 ll。因此答案为

Query⁡(r)−Query⁡(l−1).\operatorname{Query}(r)-\operatorname{Query}(l-1).

排序会打乱询问顺序，所以需要记录原编号，并把答案写回对应位置。

【复杂度分析】

时间复杂度为 O((n+q)log⁡n)\mathcal{O}((n+q)\log n)，空间复杂度为 O(n+q)\mathcal{O}(n+q)。

【参考代码】

/*Author:EhundateghDate:2026/7/30Name:beads.cppYou steal,I kill.*/#include <cstdio>#include <cstring>#include <algorithm>#define MAXN 1000010using namespace std;int T,n,q,Line[MAXN],Last[MAXN],C[MAXN],Ans[MAXN];struct query{    int l,r,p;}Q[MAXN];bool cmp(query a,query b){    if(a.r!=b.r) return a.r<b.r;    return a.l<b.l;}int lowbit(int x){return x&-x;}void Modify(int x,int Val){    for(;x<=n;x+=lowbit(x)) C[x]+=Val;}int Query(int x){    int Ret=0;    for(;x;x-=lowbit(x)) Ret+=C[x];    return Ret;}void Solve(){    scanf("%d%d",&n,&q);    memset(C,0,sizeof(C));    for(int i=1;i<=n;i++) scanf("%d",&Line[i]);    for(int i=1;i<=q;i++){        scanf("%d%d",&Q[i].l,&Q[i].r);        Q[i].p=i;    }    sort(Q+1,Q+q+1,cmp);    int Now=0;    for(int i=1;i<=q;i++){        while(Now<Q[i].r){            Now++;            if(Last[Line[Now]]) Modify(Last[Line[Now]],-1);            Modify(Now,1);            Last[Line[Now]]=Now;        }        Ans[Q[i].p]=Query(Q[i].r)-Query(Q[i].l-1);    }    for(int i=1;i<=q;i++) printf("%d\n",Ans[i]);    for(int i=1;i<=n;i++) Last[Line[i]]=0;}int main(){    int c;    scanf("%d%d",&c,&T);    while(T-->0) Solve();    return 0;}