XYD 序列上的树

毒瘤题

统计区间个数。很多都是扫描线。通常有两种常用的方法。一种是枚举右端点，然后求有多少左端点。一种是枚举左端点，求有多少右端点。第二种是完全劣于第一种的。因为我们可以在扫描线扫过去的时候，记录一些答案，为我们在求左端点的时候提供一些便利。

所以我们从右往左做，然后找有多少右端点。假设我们现在做到了i那么我们的右端点一定是右边满足a[j]==a[i]的某一个。那么我们要找最远的右端点，那么包在右端点里的j都合法。我们发现我们可以利用之前的答案然后只要判断i-nxt[a[i]]对答案的贡献即可。首先我们发现如果一个数出现了1次，那么它必然就是叶子，然后叶子肯定是从上往下走的，然后在走上去。所以叶子的左右是相同的。然后对于一个数，它第一次出现的位置肯定是第一次进入子树的位置，最后一次出现的位置是跳出子树的位置，那么第一次出现的和最后一次出现的两边必然是相同的。这就是判定的方法。我们发现在递归的过程中，有许多小的段也是合法的。就比如单个的，包了第一层的，比如就是1 * 1 * 1其中是合法的欧拉序，那么1 * 1也是 1 * 1 1也是，这个可以通过乘法原理解决。所以我们对于每个数，都找到第一次和最后一次出现的位置，1212.然后对于一段合法的欧拉序，比如1111，那么*也是合法的。所以我们首先要找到最远右端点使得里面数都不重复。这不是个很经典的的东西吗。就是有道主席树的题也用到了这个东西。我们将每个数的nxt[a[i]]也就是a[i]出现的下一个位置，那么我们要找到一个最大的r使得里面的nxt[a[i]]>=r。我们建立一颗线段树，对于区间里nxt[a[i]]>nxt[l]的数去取个min。但我们发现这样根本做不了（xuzishuai场上就想到这里了orz）。我们在维护一个lst，刚好和nxt相反，那么我们只要找到最小的j使得lst[j]<nxt[l]即可。这个可以线段树上二分做。