Problem-D-CodeforcesLexichromatography-洛谷先注意读题：对于所有的值\(k\)，在这个序列的任意子区间\([l,r]\)中，值为\(k\)且为红色的位置数减去值为\(k\)且为蓝色的位置数的绝对值不超过\(1\)注意是任意子区间这说明什么？说明如果只有第二个条件，我

CF1876DLexichromatographyLuoguCF1876D题目描述给定一个长为\(n\)的序列\(a\)，你需要对这个序列进行红蓝染色。染色有如下要求：每个位置恰好染上其中一种颜色。对于所有的值\(k\)，在这个序列的任意子区间\([l,r]\)中，值为\(k\)且为红色的位置数减去值为\(k\)且为

CF1876DLexichromatography题目链接：https://codeforces.com/problemset/problem/1876/D题意给一个$n$个数的数组$a$染色，每个元素被染为红色或蓝色。求满足下面两个条件的染色方案数：将蓝色和红色的数分别取出成为两个数列，则蓝色序列字典序小于红色序列。任意一个子数组

题中的约束可以描述为：红的字典序比蓝大。对于每个数值，必然是红蓝交替涂色。设总共出现了\(c\)个颜色，总涂色方案数就是\(2^c\)种，其中字典序情况包含大于，小于，相等，且前两者方案数相同。所以不妨选取更简单的部分相等进行处理，设相等的方案数为\(x\)，则答案就为\(\frac{1}

洛谷传送门CF传送门这说明你的能力还不足以维持IM。显然balanced的充要条件是，对于每个值，染色一定是RB交替。然后一种值只会有先染红或先染蓝两种情况。然后还剩下字典序严格小于的条件。我场上的想法是枚举\(\text{LCP}\)，然后推出来一个巨大麻烦做法，根本写不出来。但