Qiuly

「CTSC2018」混合果汁 主席树 loj2555
先将所有的果汁按照 $d$ 排序。考虑 $i$ 号果汁,假设以这瓶果汁作为答案,那么这个时候我们就这能在 $i$ ...
扫描右侧二维码阅读全文
14
2019/06

「CTSC2018」混合果汁 主席树 loj2555

先将所有的果汁按照 $d$ 排序。考虑 $i$ 号果汁,假设以这瓶果汁作为答案,那么这个时候我们就这能在 $i$ 到 $n$ 号果汁里面选择一些果汁加入进来变为混合果汁,一个显然的贪心想法就是先选价钱低的。

按照价钱作为"权值"建造主席树,询问时遇到一个结点,如果可以的话选择左子树的所有结点(果汁)然后去右子树,如果已经超标了的话往左子树走即可。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
const int LogN=40;

struct Juice{int d,p,l;} a[N];
int n,m,limit;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

bool cmp(Juice a,Juice b) {return a.d<b.d;}

#define mid ((l+r)>>1)
int root[N],cnt;
struct Node {ll PL,L;int lc,rc;} t[N*LogN];
void Insert(int&now,int last,int l,int r,int P,int L){
    t[now=++cnt]=t[last],t[now].PL+=1ll*P*L,t[now].L+=L;
    if(l==r) return;
    if(P<=mid) Insert(t[now].lc,t[last].lc,l,mid,P,L);
    else Insert(t[now].rc,t[last].rc,mid+1,r,P,L);
}
ll query(int i,int j,int l,int r,ll L) {
    if(l==r) return 1ll*L*l;
    ll val=t[t[j].lc].L-t[t[i].lc].L;
    if(L<=val) return query(t[i].lc,t[j].lc,l,mid,L);/*超标了,往左子树走*/
    else return (t[t[j].lc].PL-t[t[i].lc].PL)+query(t[i].rc,t[j].rc,mid+1,r,L-val);
    /*不然选择左子树全部果汁往右子树走*/
}
#undef mid

int main() {
    IN(n),IN(m);
    for(int i=1;i<=n;++i) 
        IN(a[i].d),IN(a[i].p),IN(a[i].l),limit=max(limit,a[i].p);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i)
       Insert(root[i],root[i-1],1,limit,a[i].p,a[i].l);
    while(m--) {
        ll G,L;IN(G),IN(L);
        int l=1,r=n,ans=-1;
        while(l<=r) {/*二分*/
            int mid=l+r>>1;
            if(t[root[n]].L-t[root[mid-1]].L>=L&&query(root[mid-1],root[n],1,limit,L)<=G)
                l=mid+1,ans=mid;
            else r=mid-1;
        }
        ans==-1?puts("-1"):printf("%d\n",a[ans].d);
    }
    return 0;
}
最后修改:2019 年 06 月 14 日 05 : 13 PM

发表评论