原题地址 感觉还是很妙一个题，自己想了一会，看标签后茅塞顿开。发现这个题的操作一直在用数列已经有的部分去覆盖一部分。因为一直在用原来的，有点可持久化的意思。发现其实我只要维护一个数据结构，可以把原来的一段提取出来插入到一个位置，并且可以维护区间加区间和以及可以可持久化即可，这里的可持久化是为了不影响原来已有的部分，对于所有的修改都在新点上操作。这样的数据结构就只有可持久化平衡树了。非旋Treap的可持久化和线段树差不多，只要有修改的地方拉一个新点起来就行了。时间复杂度O(n log n)，空间常数很大，注意不要爆空间。#include<cstdio>
#include<alg
【题目描述】给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节点的颜色为c[i]。如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。 每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色。请写一个程序，快速回答这些询问。 【输入】第一行包含一个正整数T(1<=T<=500)，表示测试数据的组数。 每组数据中，第
Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could b
题目描述Byteasar works for the BAJ company, which sells computer games. The BAJ company cooperates with many courier companies that deliver the games sold by the BAJ company to its customers. Byteasar is inspecting the cooperation of the BAJ company with the couriers. He has a log of successive packages
题目背景这是个非常经典的主席树入门题——静态区间第K小 数据已经过加强，请使用主席树。同时请注意常数优化 题目描述如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。 输入输出格式输入格式： 第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。 第二行包含N个正整数，表示这个序列各项的数字。 接下来M行每行包含三个整数l, r, kl,r,k , 表示查询区间[l, r][l,r]内的第k小值。 输出格式： 输出包含k行，每行1个正整数，依次表示每一次查询的结果 输入输出样例输入样例#1：5&nbs
原题: 可持久化并查集 Descriptionn个集合 m个操作操作：1 a b 合并a,b所在集合2 k 回到第k次操作之后的状态(查询算作操作)3 a b 询问a,b是否属于同一集合，是则输出1否则输出0 0<n,m<=2*10^4 Sample Input5 6 1 1 2 3 1 2 2 0 3 1 2 2 1 3 1 2 Sample Output1 0 1 无语了,第一次接触可持久化数据结
Rockdu's Blog