icontofig | 发布于 2020-02-03 23:19:32 | 阅读量 344 | 点分治 树状数组
发布于 2020-02-03 23:19:32 | 点分治 树状数组
luogu P4178 Tree 点分治+树状数组
题解树上点对距离问题,非常经典的点分治问题。 点分治的基本思路: 对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。 重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。 重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。 此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。 可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理
继续阅读
icontofig | 发布于 2020-01-15 19:57:24 | 阅读量 886 | 思维题 树状数组
发布于 2020-01-15 19:57:24 | 思维题 树状数组
Educational Codeforces Round 80 (Rated for Div. 2) E Messenger Simulator 树状数组求区间内不同的数的个数
题目大意一开始有一个初始顺序的排列[1,n],一共有m次操作,每次将数ai从序列中取出,放到最开头的位置生成一个新的排列。 求问在所有过程中每一个数最小的下标位置和最大的下标位置。 题解最小的下标位置是非常容易求得的,这很明显,因为如果从来没有被放到开头,那么答案一定是i,否则答案就是1。 需要思考的点在于求最大的下标位置。 这个数据范围不允许进行模拟,链表也不行(链表的单个操作、查询效率极差)。 先来考虑一种特殊情况1: 假设当前所有的数字都已经被放置到第一位过了,在满足这种条件后的最大的下标位置怎么求。 明显元素之间一开始的位置在哪里已经完全互不影响了。 如果一个数再被要求放到第一位,那么
继续阅读
icontofig | 发布于 2019-11-25 13:21:43 | 阅读量 426 | 树状数组 二分
发布于 2019-11-25 13:21:43 | 树状数组 二分
Codeforces Technocup 2020 - Elimination Round 3  D2. Optimal Subsequences (Hard Version) 二分+树状数组
题目大意给定一个序列,每次询问参数为pos和k,求问长度为pos的和最大的子序列中第k个元素是什么。 题解这题其实有一个easy version,用map稍微搞一搞就能过那种 然后这题数据范围到2e5了,就不能用map乱搞了。 首先我们要想一下如何构造这个长为pos且和最大的子序列怎么构造呢? 我们只要对原序列从大到小排一次序,且保证在等大的时候原序列中靠前的元素在排序后也考前,然后我们只需要从排序后的序列中取前pos个数,就是符合要求的子序列了。 但是询问次数过多,我们就不能对于每一个request都重新求一次符合要求的子序列。 我们发现这个序列是递增的,就是如果pos[i] > po
继续阅读
icontofig | 发布于 2019-10-31 20:13:52 | 阅读量 321 | 二分 分数规划 树状数组
发布于 2019-10-31 20:13:52 | 二分 分数规划 树状数组
CCPC2017哈尔滨站 Server——01分数规划+树状数组
题目大意给出一些线段,给出这些线段的起始和终止位置,并给出这些线段选取的两个代价A和B,要求选取一些线段覆盖区间[1----t],使得ΣAi与ΣBi的比值最小。 题解很经典的01分数规划问题的形式。 当天训练的时候就想到了BUPT2019校赛的一道01分数规划问题,当时还是我们队拿的那题一血,可惜当时的队友现在因为一些原因分开了,真是令人感叹,sigh。 回归正题…… 这一类最经典的01分数规划的解题基本思路是十分固定的,如下: 1.二分一个目标值mid 2.贪心地去构造检验是否有一组可行解,使得ΣAi / ΣBi <= mid; 3.如果能构造出这样一组可行解,那么将二分区间向左缩进,
继续阅读
icontofig | 发布于 2019-09-08 00:15:37 | 阅读量 378 | 树状数组 偏序
发布于 2019-09-08 00:15:37 | 树状数组 偏序
The Preliminary Contest for ICPC Asia Xuzhou 2019 I.query 树状数组 二维偏序
题目大意给定一个1---n的排列和m次询问,每次询问区间 [l,r]之间min(pi,pj) = gcd(pi,pj)的数对的个数。 题解一开始看到是数对问题还以为是莫队,不过话说回来莫队WA了而不是T是怎么回事…… 首先我们需要注意min(pi,pj) = gcd(pi,pj)可以转化为pi和pj互为因数和倍数的关系(这样可以做一点常数上面的优化,也更好判断总体的数对的个数)。 然后我们要知道,所有的数对个数大概是O(nlogn)级别的。 于是我们可以枚举每个数的倍数预处理出所有的数对的位置对(i,j),我们尽量让i比j大,这有利于下面的思路。 然后有没有发现这个位置对很像是二维平面上的坐标
继续阅读
icontofig | 发布于 2019-09-02 23:23:58 | 阅读量 679 | 思维题 扫描线 树状数组
发布于 2019-09-02 23:23:58 | 思维题 扫描线 树状数组
2019 南京网络赛 A.The beautiful values of the palace 思维题+扫描线+树状数组
题目大意每个点的数值是通过一个从中心最大值开始的蛇形矩阵确定的。其中有m个点上的权值可用,对于q个询问,输出左下角为(x1,y1),右上角为(x2,y2)的矩阵区域内所有可用点的权值经过处理后的和。 处理的方法是,将原权值所有数位上的数相加。 题解此题估计是模仿NOIP2014普及组T3的蛇形矩阵出的规律题目。 首先n为奇数,n*n为奇数,地图大小为 一定为奇数,所以 x = x − n/2 − 1y = y  - n /2 - 1;t = max(abs(x),abs(y)); //确定该点在第几圈螺旋 if(x >= y)ans = n ∗ n
继续阅读
icontofig | 发布于 2019-05-31 00:46:09 | 阅读量 295 | 树状数组
发布于 2019-05-31 00:46:09 | 树状数组
BUPT校内训练 Codeforces Gym 101572 G Galactic Collegiate Programming Contest 离散化+树状数组计数
题目大意一场ICPC赛制比赛,有n支队伍和m次正确提交 每次正确提交包含a,b两个参数,a表示队伍编号,b表示此题的罚时。 要求对于每次事件,输出1号队伍的排名(并列的算同样的排名) 具体排名方法为:通过题目数多的队伍排名靠前,通过题目数相同的队伍总罚时低的靠前。 题解&分析如果暴力做的话,每一修改O(1),排序查询O(nlogn),总复杂度O(mnlogn),这对于10^6的数据是不现实的。 我们要求做到O(nlogn),也就是说不能有每修改一次就排序的操作。 我们可以注意到,每一次事件发生后,只会有一个队伍的成绩发生变化,其余的成绩是不动的。 所以我们可以读入所有数据,然后计算每一
继续阅读
icontofig | 发布于 2019-05-19 21:03:32 | 阅读量 388 | 莫队 树状数组
发布于 2019-05-19 21:03:32 | 莫队 树状数组
XTCPC2019 湘潭邀请赛 Problem C Chika and Friendly Pairs (莫队+树状数组)
 题意:给定n个数,m条询问,每个询问中包含l、r查询这个区间[l,r]中有多少个数对满足两个数的绝对值之差小于等于K 题解:上来一看区间查询,第一反应一般都是线段树/树状数组等数据结构。 但是看一下这道题要求什么,求区间内满足条件的数对个数。 我好像没有见过能维护数对个数的树状数组或者线段树什么的。 对于数对而言,一般都应该先枚举其中一个数,剩下的才能去判断吧。 如果两个数i,j满足绝对值之差小于等于K,那么肯定能有这样一个关系式:i−k<=j<=i+k 这样的话,对于某个区间内的所有数,能跟当前枚举出来的数x组成满足题意的数对的,一定在[x-k,x+k]这个区间里,我
继续阅读
icontofig | 发布于 2019-02-27 23:53:01 | 阅读量 196 | 树状数组
发布于 2019-02-27 23:53:01 | 树状数组
由于格式问题,这道题的题面就不往这里放了,给一个洛谷的链接吧:[POI2005]AUT-The Bus 题解这道题有中文题意,没有BZOJ权限号的可以去洛谷上搜到这道题。首先会想到DP,但是一看这个数据范围也太大了,离散化后也没法做二维DP。但是离散化也是要的,不然10的9次方的数据谁顶得住啊。考虑这是一个二维偏序问题。一般的二维偏序都是找比当前物品的两个值都小的问题,而这道题并不是,这道题要做的是维护最大前缀和。首先按照y排序并且离散化每个车站的y坐标,然后再按照x排序,使用树状数组维护最大前缀和即可(当然线段树应该也是可以的,只不过会比树状数组麻烦一点)。注意这里的树状数组不是维护的前缀和
继续阅读
icontofig | 发布于 2017-01-18 08:56:15 | 阅读量 210 | CDQ分治 树状数组
发布于 2017-01-18 08:56:15 | CDQ分治 树状数组
Description你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:命令 参数限制 内容1 x y A 1<=x,y<=N,A是正整数 将格子x,y里的数字加上A2 x1 y1 x2 y2 1<=x1<= x2<=N1<=y1<= y2<=N 输出x1 y1 x2 y2这个矩形内的数字和3 无 终止程序 Input输入文件第一行一个正整数N。 接下来每行一个操作。 Output对于每个2操作,输出一个对应的答案。 Sample Input41 2 3 32 1 1 3 31 2 2 22 2 2 3 43
继续阅读