题目描述\(T\)组数据，给定长为\(n\)的字符串\(s\)，\(q\)次询问，给定\(i,r\)，求有多少个\(l\)满足：\(1\lel\ler\)。\(s[i:i+l-1]\)字典序小于\(R(s[i+l:i+2l-1])\)。数据范围\(1\leT\le5,1\len,q\le10^5,1\lei+2r-1\len\)。时间限制\(\texttt{1s}\)，

A队彩笔高二生最后一次参加NOI。凡事有第一次，就会有最后一次。我打完了最后一场ZR，最后一场AtCoder，最后一场CF。接下来将迎来我的最后一场NOI。Day-1NOI2023在四川省成都市第七中学举办。下午飞抵成都，机场接站等学车爷等了一个多小时，导致快4点才到学校。工作人员很

写在前面照了挺多照片，本来只想传照片不写文字的，但博客园只让传小于等于2MB的照片（这大小是个手机照的照片都传不上去吧），那好吧，我就写写；Day0出发时还是很激动的，但没有CSP和NOIP那么紧张（那两篇等以后看看再写吧）；熟悉的大巴，熟悉的路线（毕竟也是第三次了），确实勾起了很多回忆；大巴上没

题解对于行操作，列操作和对角线操作，实际上仅仅只是在对若干个矩形求面积并而已，这是裸的扫描线题，套用模板即可，此时注意到对角线操作实际上是\(O(n)\)量级的矩阵面积并，因此复杂度是\(O(n\logq+q\logq)\)的量级，只能获得95pts。显然，面积并具有交换性，我们先做\(O(q\logq)\)

[NOI2023]桂花树题目描述小B八年前看到的桂花树是一棵\(n\)个节点的树\(T\)，保证\(T\)的非根结点的父亲的编号小于自己。给定整数\(k\)，称一棵\((n+m)\)个节点的有根树\(T^{\prime}\)是繁荣的，当且仅当以下所有条件满足：对于任意满足\(1\lei,j\len\)的\((i,j)

题意：给定一棵深度为\(n\)的完美二叉树，根节点为\(1\)，对于所有非\(1\)的点，都有一条连到其父亲的边权为\(a_i\)的单向边，除此之外，还给定了\(m\)条单向边（\(u\rightarrowv)\)，边权为\(w\)，保证\(u\)是\(v\)的祖先，求\(\sum_{i=1}^{2^n-1}\sum_{j=1}^{2^n-1}dis(i,j)\)，其

称编号\(>n\)的点为新点。由条件1可以推出树\(T\)为结点\(1\simn\)在树\(T'\)上的虚树。由条件2可以推出\(\forall1\leu<v\len+m,\operatorname{lca}(u,v)\lev+k\)。首先考虑\(k=0\)的做法：此时\(\forall1\leu<v\len+m,\operat

前情提要tjD类什么垃圾不用我说了吧。Day-1到场了，挺热的。和两位同校巨佬分到了一个宿舍还有一位E类都比我强/kel中午和三位同校巨佬还有教练去外面吃了一顿火锅，选的微辣但是我还是有点接受不了。北方人没吃过油碟。没有麻酱我们都有点奇怪。幸亏有冰红茶解辣。成

图中不存在横插边，\(u\rightsquigarrowv\)可拆成\(u\rightsquigarrow\operatorname{lca}(u,v)\rightsquigarrowv\)计算。对\(u\rightsquigarrow\operatorname{lca}(u,v)\)，不可能走第二类道路，树形DP统计每条边被经过的次数并累加答案即可，时间复杂度\(\mathcalO(2

Description传送门SolutionPart1考虑一棵合并树，令\(ls_u,rs_u\)表示\(u\)的左右儿子，\(d_u\)表示\(u\)子树的最大深度，\(c_u\)表示\(u\)被合并的次数，令所有非叶非根节点对应\(2^d-1\)的和为\(S\)，则答案为\(\sum_{i=1}^nc_iw_i+S\)。可以发现，我们只关心\(c

考虑对合并过程建一棵树。对于一个点\(x\)，定义\(a_x\)表示它向上合并的时候，对答案造成的重量贡献的系数。定义一个点的层级\(d_x\)为它的两个儿子层级的较大值\(+1\)。我们称\(d\)更小的层级为更深的层级。那么层级为\(i\)的非根非叶子节点会对答案造成\(2^i-1\)的

扔到cnblogs上。##Day-4最后一场模拟赛，肯定要用力打啊！然而一题不会，呜呜呜。于是开始拼暴力，写了$90+60+60=210$，结果挂成$40+60+60=160$。T1我将题目转化为：对于一个排列，每次只改动三个位置，要求某个数的出现位置，我用了fhq-treap！维护一个桶就好了，不知道自己

打的太shaber了，于是补补题。D1T1扫描线。首先我们可以容斥一下，答案为被一种操作覆盖到的减去被两种操作覆盖到的加上被三种操作覆盖到的。首先考虑只被一种操作覆盖到的，这很简单，直接上个区间颜色段推平就好了，顺便去了个重。接下来是有被斜线覆盖到的，这样的点数为\(O(nk)\)

题目链接题目要求我们求出任意两点间最短路径之和，由于图比较特殊，除树边外只有祖先到其子树内的边，我们首先考虑最短路径有没有什么特殊性质。注意到两点之间的最短路分为一下三种：节点到其祖先的最短路：直接沿着树边向上走即可，否则一定会走多余的边，不是最优。节点到其子树的

Day1被找规律随机区分\(35\)分。Day2以我现有的水平已经无力回天了，d2T3却还挂了\(35\)分。连队线的边都没碰到，只混到了\(100\)多名的Ag。我不愿回忆这场考试的任何细节，知道寄了就行了。分数是从低往高排的。nfls的众人中，我是第一个上去的。为什么在公布Ag名单时，

前情提要：HE春测+省选rk24，D类选手。前言之前省选游记好像说目标是拿到D类名额+省内高一前\(5\)，虽然做到了但是D1T2没分析出很显然的树上做法、D1T3没有想线段树分治以及D2T2选择二分图建模而不是二元组连边都是相当降智操作。结果是导致清北营不过审。中途\(6\)月

想了很久，还是决定写退役记，全都要靠回忆所以应该会漏不少细节。因为已经退役，比赛过程写的比较少，看个乐就行。7.2~7.212号提前到了成都七中，打了两周多的模拟赛。基本都是垫底的，题也补的很少。感觉状态有点差的。保持手感完全靠和学弟duel，学弟好强。7.22报到日。上午大概10

和考试的时候思路差不多。首先考虑钦定一部分关键点是合法的根，带上容斥系数。对于一条非树边，要求其在任何一个钦定点作为根的时候都不是横叉边。具体而言，对于一个钦定点集合，我们建出钦定点集合的虚树，那么符合条件的非树边有如下几类：不妨先考虑特殊性质\(B\)，没有横叉边的情

对于给出的串\(S\)，将其拓展成\(S+\)特殊字符\(+rev(S)\)，求出其后缀数组。那么对于一个子串\([l,r]\)，合法的必要条件是\(l\)的后缀在后缀数组的排名小于\(r\)的前缀的排名。之所以是必要条件，是因为会记入一些\([l,r]\)是回文串且\(l\)的排名小的情况。具体而言，这

P9482[NOI2023]字符串限制长的很像回文串，但是是字典序关系。定睛一看比较的是原串\(s\)的一个后缀的前缀和翻转串\(s'\)的一个后缀的前缀比字典序。直接把\(s'\)拼到\(s\)后面，中间加个分隔符，来一次后缀排序。排名小的后缀字典序比排名大的后缀小。设当前比较的是

在这段时间主要在学文化课，没怎么停课，天天暴力拼盘，所以索性合在一起。感觉非常意识流，和OI关系好像也不大。pig嫌我开始写的太短，我积极听取他人建议，加了一车流水账。联赛结束以后就退役了。因为即使NGOI也大概率会被卡“省线”，但还打算参加省选碰碰运气。遂在省选前两周申请一周半

Before提前若干天到成都，感觉环境很好啊。提前参观成七，果然是别人的学校，有\(NOI\)那味了打了套全真模拟，但是没出结果，不重要，反正啥也不会。、在宾馆/成七打了一堆板子，适应了键盘，其实用起来还不错？最后一天晚上出去吃，和\(Kaguya\)和牛老师吃了一顿麻辣烫，体验良好，出了很多汗

Day???来nfls集训并见证了一半的HN省队都在南京的奇景。认真打了一个月模拟赛，感觉还不错，终于有一套比较稳定的策略了虽然不时过不了大众题，在第14场的时候因为见过原题首次冲进前十，太感动了！因为补觉错过了UNR，保住了一点信心。最后一周的时候感觉有点累，润回长沙开摆了，算

Day-4打UNR，寄。具体情况见UNR游记。Day-3做了近九小时的车，来到了成都。众所周知，我是擅长睡觉的。所以，像是往常坐车的话，基本上都有一半的时间都睡过去了。然而这次，虽然路上很困，但是竟然全程没有睡着。大抵就是，感觉哪里不是很舒服就是了，有点累。想要睡着但是完全睡不

来成都之前，我一直认为自己拥有金牌的实力，也无论如何都有前\(100\)保底。而现实呢？\(100+95+60+52+100+44+10=461\)，放到正式选手中是\(\texttt{rk120}\)，如此拉跨的成绩。就算把所有会的分写上，且不挂分，也只有\(100+95+70+68+100+44+30=507\)，仍旧没有金牌。\(\texttt{Day2}\)