老 K 的博客

题面

不是权限题美滋滋。

题面

其实没有范围

但是没有范围也没有关系。

题面

题目

传送门

把边按照\(a_i\)升序排序。

每次加入一条边，如果两端不连通，则直接加入，否则加入以后就会出现一个环，割掉这个环上\(b_i\)最大的边。

每次加入一条边后计算当前答案取最大值。

题意

有n个村庄，连成一棵树。

有m次操作，每次形如\(u,v,w\),表示给从u到v的所有村庄颁发一个类型为w的证书，求每个村庄得到哪类证书的个数最多。若有多个输出类型最小值，若没有证书输出0

\(n,m,w\le 10^5\)

题意

给定一棵n点的树，每个点有点权\(w_i\)。每次给定u,v，求\((\sum_{i=1}^n\sum_{j=1}^nf(i,j)) \mod 10^9+7\)，其中当i到j的路径和u到v的路径有交集时\(f(i,j)=w_iw_j\)，否则\(f(i,j)=0\)

给定一棵树，已知每个点点权\(w_i\)，每次给定\(s,t,a,b\)，求从s到t的路径上满足\(a\le\)点权\(\le b\)的点的点权和。

点数，询问数\(\le 10^5\)，多组数据，\(w_i,a,b\le 10^9\)

题目传送门

显然，我参加了这次HNOI。

然而并没有什么用，只拿了纯良心的70pts暴力。

30%的数据满足n≤500, m≤10；

70%的数据满足n≤5000；

100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。

并不知道在\(30pts\) \(m\le 10\)的基础上，为什么\(100 pts\) \(m\le 100\)，包括\(70 pts\) \(m\le 100\)，然而后面两个部分分真的m可以开到很大。

题解

显然手环2亮度减c和手环1亮度+c是等价的，所以修改相当于在手环2亮度+c\((|c| \le m)\)（显然）

假设下标从0开始到n-1(原题为从1到n)

题面

传送门 维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000. 操作一为增加，操作二为查询