[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=60083619
向大(hei)佬(e)势力学(di)习(tou)
前段时间做了一套大佬自己出的题(大佬竟然是个宅男2333),蒟蒻的我自然是只得了30分的暴力分:-(
fleet
舰队
【题目描述】
舰队里的每位舰娘都有一个编号i,也有一个类型ti,例如驱逐舰、轻巡洋
舰、航空母舰……
每次提督都想知道从第l 位舰娘到第r 位舰娘中(包含l、r),一共有多
少不同的类型。请你回答他的询问。
【输入格式】
第一行一个整数n,表示舰娘数量。
第二行n 个整数,第i 个整数ti 表示舰娘i 的类型。
第三行一个整数q,表示提督的询问数量。
接下来q 行,每行2 个整数l,r,表示询问[l,r]有多少不同类型的舰娘。
为了模拟真实情况,本题强制在线。你需要记录上一次的答案lastans(初
始值为0),每次询问真实的l,r 为l xor lastans 与r xor lastans,其中xor
表示按位异或操作。
【输出格式】
输出q 行,每行一个整数表示询问的答案。
【样例数据】
fleet.in
5
1 1 2 1 3
3
1 5
1 7
1 7
fleet.out
3
2
3
【数据范围】
对于30%的数据,n,q≤5000。
对于另30%的数据,ti≤100000。
对于100%的数据,1≤n,q≤200000,1≤l≤r≤n,1≤ti≤10^9。
正解当然不是我想出来的,而是另一个大佬自己yy出来的
我们建的线段树表示原序列中出现的不同的数的个数,就是对原序列建树,只不过对于节点i的线段树表示1~i区间出现的不同数的个数。
建树的时候需要记录这一个数上一次出现的位置,新建一棵树的时候既要加,又要减。
查询的时候利用前缀和区间查询即可
注意要离散化
然后就没更多的技巧了,但是将这一模型抽出来着实很厉害