(luogu2073)送花 发表于 2021-02-09 | 分类于 solution , 数据结构 , 树状数组 原题链接 思路:使用权值树状数组. 插入操作先查找对应的位置值是不是0, 然后插入. 删除操作二分查找最大值和最小值. 美丽值总和做个前缀和就行, 至于总的价格在插入和删除的时候维护即可. 代码:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include <cstdio>#include <cstdlib>typedef long long LL;const int Mn(1000050);class BinT { //树状数组(我也不知道我为什么要建个类)private: int len; //树状数组长度 LL* c; //数组本体 inline int lb(int x) { //lowbit return x&(-x); }public: explicit BinT(int n=Mn) { this->len = n; c = (LL*)malloc((n+1)*sizeof(LL)); } void add(int p,LL x) { //修改操作 while(p<=len) { c[p] += x; p += lb(p); } } LL sum(int p) { //查询前缀和 LL ret(0); while(p) { ret += c[p]; p -= lb(p); } return ret; }}bt;int main() { int opt; //操作数 LL prc(0); //价值总和 while(~scanf("%d",&opt)) { if(opt == -1) { break; } else if(opt == 1) { int x,y; scanf("%d %d",&x,&y); if(bt.sum(y)-bt.sum(y-1)==0) { //是否可以插入 bt.add(y,x); prc += y; } } else if(opt == 2) { if(bt.sum(Mn)==0) { continue; } int l(1),r(Mn); while(r-l>3) { //二分查找最大值 int mid((l+r)/2); if(bt.sum(r)-bt.sum(mid)>0) { //如果右区间有值 l = mid+1; } else { r = mid; } } /*二分区间长度较小时暴力查找, 避免边界问题*/ for(int i(r);i>=l;--i) { LL tmp; if((tmp=bt.sum(i)-bt.sum(i-1))>0) { bt.add(i,-tmp); prc -= i; break; } } } else if(opt == 3) { if(bt.sum(Mn)==0) { continue; } int l(1),r(Mn); while(r-l>3) { //同样是二分 int mid((l+r)/2); if(bt.sum(mid)==0) { l = mid+1; } else { r = mid; } } for(int i(l);i<=r;++i) { LL tmp; if((tmp=bt.sum(i)-bt.sum(i-1))>0) { bt.add(i,-tmp); prc -= i; break; } } } } printf("%lld %lld",bt.sum(Mn),prc); return 0;}