题解 CF1515I【Phoenix and Diamonds】

· · 题解

CF1515I Phoenix and Diamonds解题报告：

更好的阅读体验

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

题意

- $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记录&代码