关于区间数颜色的主席树解决

这里考虑我今天才了解全的做法

1

这是我一直在用的做法，就是考虑维护某一个颜色的最右边的端点，也就是离线HH的项链的做法

2

然后第二种是考虑反向思维，对于一次 l,r 的查询是在 l 这颗树上查询 l~r 的区间和，就可以发现这并不需要减少

然而我并不会打

3

考虑转化二维数点

我们可以考虑将所有的点和它的前缀连边，有多少个在l~r的点与前缀的连边跨越了l

我们将(l,last[l])放到平面上，就变成了一个二维数点问题，避免了1做法中的两次操作

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zzqdeco/p/13866352.html