CF1515I Phoenix and Diamonds解题报告

解题报告

CF1515I Phoenix and Diamonds解题报告：

更好的阅读体验

似乎是你谷首杀，针不戳。

题意

$n$种钻石，一颗第$i$种钻石重量为$w_i$，价值为$v_i$，一开始第$i$中钻石的库存为$a_i$。接下来进行$m$次操作：

• $1\ k\ d$：进货了$k$个种类为$d$的钻石；
• $2\ k\ d$：卖出了$k$个种类为$d$的钻石；
• $3\ c$：如果你有一个大小为$c$的袋子，且按照第一关键字为价值（从大到小），第二关键字为重量（从小到大）的顺序取钻石的话，你最终可以取到钻石的价值为多少（注意操作不会真正执行）

$1\leqslant n\leqslant 2\times 10^5,1\leqslant m\leqslant 10^5,1\leqslant k,d,a_i\leqslant 10^5,1\leqslant c\leqslant 10^{18}$

分析

神奇的题目，感觉没有CF*3400评分这么夸张，不过这数据确实强。

由于钻石种类已经给定，因此我们可以知道拿钻石的优先级。

发现处理询问的复杂度与$c$总得有点关系，看$c$的数据范围就大胆猜想复杂度要带$\log C$，那么考虑如何每次至少把$c$除二。

设$c$的最高位为$\omega$，对于第$\omega$位，设一个钻石是“轻的”当且仅当其重量小于$2^{\omega-1}$，否则如果它的重量小于$2^{omega}$，那么它是“重的”，一个很显然的结论就是在最高位不变的情况下不能取多于一个“重的”钻石。

自然而然地设$lightv_{l,r,k}/lightw_{l,r,k}$表示对于第$k$位，$l$到$r$“轻的”钻石价值和与重量和，$extra_{l,r,k}$表示对于第$k$位，$l$到$r$“轻的”钻石重量加上一个最小的“重的”钻石的重量之和。

状态是$O(n^2\log c)$的，不好存储，考虑上线段树，将上面的区间$[l,r]$改为其对应线段树上的结点$now$，那么很容易写出一个$\log c$的$\text{pushup}$来动态维护这三个数组。

查询部分，我们就先判掉叶子结点的情况，然后考虑重钻石与轻钻石都可以取走的情况，然后再判一判是不是只能取轻钻石，如果都不是的话就递归两个儿子处理。

记得动态维护当前$c$的最高位$\omega$。

时间复杂度：$O((n+q)\log n\log c)$。（复杂度不太会证/kel）

long long query(int l,int r,int now){//calc()是维护c的最高位ω的函数
    if(l==r){
        long long num=min(a[id[l]],c/w[id[l]]);
        c-=num*w[id[l]],calc();
        return num*v[id[l]];
    }
    if(lightw[now][omega]<=c){
        long long res=lightv[now][omega];
        c-=lightw[now][omega],calc();
        return res;
    }
    if(lightw[now][omega-1]<=c&&c<extra[now][omega-1]){
        long long res=lightv[now][omega-1];
        c-=lightw[now][omega-1],calc();
        return res;
    }
    int mid=(l+r)>>1;
    return query(l,mid,lc[now])+query(mid+1,r,rc[now]);
}

AC记录&代码