字符串[LOJ6517]

题目描述有$N$个字符串,每个字符串有一个权值$v_i$。随后给出$M$次询问,每次对一个区间进行检测。令最长的字符串长度为$L$,那么会给出$g_1,\cdots,g_L$表示每个长度的字符串的「识别值」。 对若干个字符串构成的集合$P$进行测试的过程如下: 对字符串$S$定义$f(S)$表示$S$在$P$中以其为前缀出现的串的权值和。 那么如果$S$在$P$中作为前缀出现过,并且$B*f...

糖果公园[WC2013]

【题目描述】 题目描述太长了。。。建议自行读题 传送门 题意:给你一棵树,每个点有一个颜色$c[x]$,每种颜色有一个权值$v[c]$,还有$n$个参数$w[i]$。 如果一条路径上颜色为$c$的点有$cnt$个,那么产生$v[c]*w[cnt]$的贡献,路径的总权值就是每种颜色产生的贡献和。 每次询问一条路径的权值或者更改一个点的颜色 【输入/输出格式】 不关心 题解这道题就是树上莫队和带...

Count on a tree II [SP10707]

【题目描述】 给定一个$n$个节点的树,每个节点表示一个整数,问$u$到$v$的路径上有多少个不同的整数。 【输入格式】 第一行有两个整数$n$和$m$($n=40000,m=100000$)。 第二行有$n$个整数。第$i$个整数表示第$i$个节点表示的整数。 在接下来的$n-1$行中,每行包含两个整数$u,v$,描述一条边($u,v$)。 在接下来的$m$行中,每一行包含两个整数$u,v...

数颜色[国家集训队2011]

【题目描述】 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1.Q L R代表询问你从第$L$支画笔到第$R$支画笔中共有几种不同颜色的画笔。 2.R P Col 把第$P$支画笔替换为颜色$Col$。为了满足墨墨的要求,你知道你需要干什么了吗? 【输入格式】 第$1$行两个整数$N,M$,分别代表初始画笔的数量以及墨墨...

小Z的袜子「2009国家集训队」

【题目描述】作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……具体来说,小Z把这$N$只袜子从$1$到$N$编号,然后从编号$L$到$R$选择两只袜子。尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。你的任务便是...