spoj DQUERY – D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接
题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。

思路:离线处理+线段树的做法不多说了:

之后补一个主席树的做法

先来补一个莫队的做法。

因为a[i]<=1E6,可以很方便得统计每个数出现的次数,update的时候,如果是1变成0,那么区间中不同的数的个数减1,如果是0变成1,那么区间中不同数个数+1

 

补一个在线的做法,可持久化线段树,其实思路和离线线段树几乎一样。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz