高度由习惯堆积

分类 数据结构:树状数组 下的文章

BZOJ2738 矩阵乘法

题目给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数。思路整体二分。整体二分主要适用于对于二分状态的改变,可以在可接受的复杂度内修改的题目。就本题而言,二分答案,如果考虑将[1,mid]的区间内的点加入树状数组中,在二维平面上标记为1,然后比较每个询问与K的关系,接着将询问分组,接着二分。以上应该是整体二分的基本模型。代码#include<bits/stdc++....

BZOJ 4553 [Tjoi2016&Heoi2016]序列

题目佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。注意:每种变化最多只有一个值发生变化。在样例输入1中,所有的变化是1 2 32 2 31...
February 17, 2019

NOIP2017 列队

题目题目链接思路30% 直接暴力模拟。50% 离散,模拟80% 注意x=1那一档,可以维护一棵树状数组,每删除一个点,就把树状数组上的点删除,再把它放在最后,每次询问在树状数组+二分。正解1