CF1945F Kirill and Mushrooms

题意

营地里的人一睡着，基里尔就偷偷溜出帐篷，去智者橡树那里采蘑菇。

众所周知，橡树下生长着 \(n\) 种蘑菇，每种蘑菇都有 \(v_i\) 的魔力。基里尔非常想用这些蘑菇制作一种魔力最大的灵药。

灵药的强度等于其中蘑菇的数量与这些蘑菇中最小魔力的乘积。为了配制灵药，基里尔将依次采摘生长在橡树下的蘑菇。基里尔可以按照任何顺序采集蘑菇。

然而，事情并非如此简单。智慧橡树告诉基里尔从 \(1\) 到 \(n\) 的数字 \(p\) 的排列组合。如果基里尔只采摘 \(k\) 蘑菇，那么所有指数为 \(p_1, p_2, \dots, p_{k - 1}\) 的蘑菇的魔力就会变成 \(0\) 。基里尔不会使用魔力为零的蘑菇来配制灵药。

你的任务是帮助基里尔采集蘑菇，使他能够酿造出最大魔力的灵药。不过，基里尔有点害怕在橡树附近逗留太久，所以在所有适合采集蘑菇的选项中，他要求您找到蘑菇数量最少的那个。

长度为 \(n\) 的排列是由 \(n\) 个不同的整数组成的数组，这些整数的顺序从 \(1\) 到 \(n\) 。例如， \([2,3,1,5,4]\) 是一个排列，但 \([1,2,2]\) 不是排列（ \(2\) 在数组中出现两次）， \([1,3,4]\) 也不是排列（ \(n=3\) ，但 \(4\) 在数组中出现）。

思路

考虑枚举摘 \(k\) 个蘑菇，然后就可以获得哪些蘑菇会归 \(0\) , 则答案贪心的想即选前 \(k\) 个蘑菇
则最小值为当前序列第 \(k\) 大

支持修改且可以动态维护第 \(k\) 大的显然是权值线段树

代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int a[N];
int b[N];
int v[N];
struct node
{
    int l,r;
    int sum;
}tr[N<<2];
void pushup(int id){tr[id].sum=tr[id<<1].sum+tr[id<<1|1].sum;}
void build(int id,int l,int r)
{
    tr[id]={l,r};
    if(l==r)
    {
        return;
    }
    int mid=(l+r)/2;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}
void change(int id,int x,int v)
{
    if(tr[id].l==tr[id].r)
    {
        tr[id].sum+=v;
        return;
    }
    int mid=(tr[id].l+tr[id].r)/2;
    if(x<=mid) change(id<<1,x,v);
    else change(id<<1|1,x,v);
    pushup(id);
}
int find(int id,int k)
{
    if(tr[id].l==tr[id].r)
    {
        return tr[id].l;
    }
    if(k<=tr[id<<1|1].sum) return find(id<<1|1,k);
    else return find(id<<1,k-tr[id<<1|1].sum);
}
int main()
{
    int _;
    cin>>_;
    while(_--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+1+n);
        int m=unique(b+1,b+1+n)-b-1;
        build(1,1,m);
        for(int i=1;i<=n;i++)
        {
            a[i]=lower_bound(b+1,b+1+m,a[i])-b;
            change(1,a[i],1);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
        }
        long long ans=b[m];
        int id=1;
        for(int i=2;i<=n;i++)
        {
            if(n-i+1<i) break;
            change(1,a[v[i-1]],-1);
            long long cnt=1LL*b[find(1,i)]*i;
            if(cnt>ans)
            {
                ans=cnt;
                id=i;
            }
        }
        cout<<ans<<" "<<id<<"\n";
    }
}