满足O(1)转移相邻状态的条件，显然莫队。
N
50000，
，所以应定义某些变量为unsigned或long long。
具体可参考hzwer的题解。
分类：莫队算法
[BZOJ 2743] [HEOI 2012] 采花
树状数组 + 差分
看上去就像莫队算法。
然后发现数据有点大......算了。
可以发现每种花只有当前区间中的第二枝对后面有贡献。则计算答案可以利用差分方法：若在 pos 位置的一束花能对后方产生贡献，则在树状数组中将 [pos, n] 区间 +1。最终此时某个区间答案即为区间和。
记录下位置 i 后第一次出现该位置颜色花的位置 nxt[i]。考虑从一个区间 [L, R] 到另一个区间 [L+1, R] 答案的变化：既然位置 L 处的花退出了区间，那么花 i 对答案的影响也要被去除，即在树状数组中把 [L, n] 答案 -1。原本 nxt[i] 位置的花是区间内第二朵花，现在也变成了第一朵，因此更新答案，[nxt[i], n] 区间 +1。
既然知道了相邻区间的转移，那么整体的做法也可以明确了：先将读入的所有区间按左端点排序，然后按刚才的方法在左端点间一位一位转移，答案就是区间和了。
代码如下：