EC R 87 div2 D. Multiset 线段树 树状数组 二分
2021-01-09 20:29
标签：else 前缀 节点 ase href -- main ++ 直接 LINK：Multiset 主要点一下 二分和树状数组找第k大的做法. 线段树的做法是平凡的 开一个数组实现就能卡过. 考虑如树状数组何找第k大 二分+查询来判定是不优秀的。 考虑树状数组上倍增来做. 考虑从0开始跳 定义跳到的节点为前缀和. 那么不断跳累加权值即可. 第三种做法是二分 (其实我最先想到的是类似的做法. 观察到答案最终只要一个数字 受到第三个样例的启发 考虑维护最大值/最小值. 直接开堆乱搞是不正确的 无法衡量之前是否删除当前的最大值了. 考虑二分这个最大值/最小值 这里以最小值为例 因为比较好描述 那么check 就是看一下
这样做可以发现满足判定的单调性. 这里用的是第一种做法。 EC R 87 div2 D. Multiset 线段树 树状数组 二分 标签：else 前缀 节点 ase href -- main ++ 直接 原文地址：https://www.cnblogs.com/chdy/p/12961007.htmlconst int MAXN=1000010;
int n,Q;
int sum[MAXN>1;
if(x>1;
if(sum[zz]>=k)return ask(zz,l,mid,k);
return ask(yy,mid+1,r,k-sum[zz]);
}
inline void erase(int p,int l,int r,int x)
{
--sum[p];
if(l==r)return;
int mid=(l+r)>>1;
if(x0)insert(1,1,n,x);
else erase(1,1,n,ask(1,1,n,-x));
}
if(!sum[1])put(0);
else put(ask(1,1,n,1));
return 0;
}
下一篇：python：汉字编码
文章标题：EC R 87 div2 D. Multiset 线段树 树状数组 二分
文章链接：http://soscw.com/index.php/essay/41242.html