题目链接：Lomsat gelral 题目大意：就是求任意一个子树的出现最多的颜色的值，如果出现次数一样则累加。 然后就是一道树上启发式合并的裸题啦！ 我们每次用重链维护信息，往上传递，其他信息暴力更新即可。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; int n,c[N],cnt[N],mx,sum,res[N],sz[N],son[N],skip; int head[N...

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 输入格式 第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2, \cdots n-1,n)(1,2,⋯n−1,n) m表示翻转操作次数 接下来m行每行两个数 [l,r][l,r] 数据保证 1 \leq l \leq r \leq n1≤l≤r≤n 输出格式 输出一行n个数字，表示原始序列经过m次变换后的结果 输入输出样例 ...

题目背景 小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。 题目描述 这些花都很漂亮，每朵花有一个美丽值W，价格为C。 小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作： 操作 含义 1 W C 添加一朵美丽值为W，价格为C的花。 3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。 2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。 -1 完成添加与删除，开始包装花束 若删除操作时没有花，则跳过删除操作。 如果加入的花朵价格已经与花束中已有花朵价格重复，则这一...

题目链接： - 题 - 目 - 一看到题目然后就想到了线段树，但是想了一会，没想到怎么维护。 然后突然一看，诶，这不是莫队的板子题嘛，然后写就A了 对于当前这种大小相等的数字的贡献为： ai * cnt *cnt ，仔细推一下即可发现。 然后就相当于莫队维护区间平方和了，但是我们再乘上 ai。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; int n,m,a[N],cnt[...

题目描述 小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题： 无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。 输入描述: 第一行两个整数n，m代表图的点数和边数。 接下来m行，每行两个整数u，v代表u，v有边相连（无向边） 输出描述: 输出一行，代表最少要添加的边数。 示例1 输入 复制 5 4 1 2 2 3 3 4 4 5 输出 复制 1 示例2 输入 复制 5 5 1 2 2 3 ...

Average distance Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1980 Accepted Submission(s): 717 Special Judge Problem Description Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance...

题目描述 “狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。 通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证...

You are given a directed graph with n vertices and m directed edges without self-loops or multiple edges. Let’s denote the k-coloring of a digraph as following: you color each edge in one of k colors. The k-coloring is good if and only if there no cycle formed by edges of same color. Find a good k...

题目描述 最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益，即如果区域(i,j)相邻（相邻是指两个格子有公共边）有k块（显然k不超过4）类型不同于(i,j)的区域，则这块区域能增加k×Cij...

题目链接：Light bulbs 一道离散化+差分 由于区间很大，我们不能直接去差分，必然TLE，但是我们可以注意到修改次数十分小，于是我们可以想到离散化之后再差分。 对于求解答案，我们可以只分析区间。同时根据差分的思想，用一个变量记录前缀和。如果当前是左区间则加一，否则减一（右区间）。然后每次记录答案，如果当前的前缀和为奇数，那么代表是亮的，于是我们答案加上当前后面的那个值，与当前这个值之间的和，因为这个区间没有操作能改变它们了。注意不能加到后面那个值的位置，因为那是未知的，可能被后续操作改变。 AC代码： #pragma GCC optimize(2) #include...

F. The Shortest Statement time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given a weighed undirected connected graph, consisting of n vertices and m edges. You should answer q queries, the i-th query is to find the shortest distance...

B. Little Elephant and Array time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard output The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let’s denote the number with index i as ai. ...

E. XOR and Favorite Number time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard output Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs...

Task Schedule Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13372 Accepted Submission(s): 4030 Problem Description Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factor...