A.给出一个序列a[i]，每个元素属于[1,n]。m个操作，子区间每次可以修改一个a[i]或者询问当前有多少个子区间内没有重复的颜色。n,m<=10W ３０％ｎ，ｍ＜＝１０００
题解： 考虑枚举左端点，ｒ［ｉ］表示ｉ到ｒ［ｉ］这段区间没有重复的颜色且ｒ［ｉ］最大。那么ｉ对ａｎｓ的贡献就是ｒ［ｉ］－ｉ＋１。
容易知道随着ｉ的增加，ｒ［ｉ］不减。所以计算一次所有的ｒ［ｉ］是Ｏ（ｎ）的。
这样可以拿３０分。
然后再乱搞一下，每次修改只会影响ｉ－ｒ［ｉ］包含ｘ的ｉ。
那么我们ｌｏｗｅｒ－ｂｏｕｎｄ一下，把这一段暴力算一算。
复杂度不好估计。。。随机数据跑的很快。。。构造的估计就呵呵了。。。
UPD：居然有90 233 数据略弱了。。。
Ｂ．看了题面就弃疗了。
Ｃ．ｎ＊ｍ的方格，要求在每个格子里填上－９的数，并且相邻的数之和＜＝某个数（给出的）。求在格子里填的数的总和。
题解：５０％ｎ，ｍ＜＝３ 呵呵 我 暴力枚举每一行用的数字。。。
满分做法据说是网络流，不明觉厉。
评论 (0)
