数颜色题解

题意

给定一个长度为n的序列A[],你需要回答q个询问。每次给定两个端点,询问区间内不同颜色的个数。n, q < 1e5。

主要思路

可以考虑建立主席树,以位置做版本下标,以颜色离散化后的值做下标,记录该颜色前缀个数,然后版本信息相减即可。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注