All About Programming: hdu5722 Jewelry - sukpigrabbit的博客

转自http://www.cnblogs.com/fzmh/p/5688069.html

题意就是说问有多少个区间，其中有至少一种种类的宝珠出现的次数恰好为x次。先预处理出每一个位置的宝珠下一个出现与其同种类的宝珠位置next和上一个出现与其同种类的位置pre

考虑在第i个位置的宝珠，要使其出现恰好x次，我们可以找到在i之后恰好出现了x次的位置j，这步操作可以用一定的技巧优化到O(1),那么对于区间[l,r],l∈[pre[i],i],r∈[j,next[j]],都满足题目要求的答案。

如何统计呢，可以把每次可行的区间看作一个矩形，底为[pre[i],i],高位[j,next[j]]，那么最后的答案就是这些矩形并的面积了

那么就是经典的线段树问题了，时间复杂度O(nlogn)

Labels