ABC289G贪心单调性分析与离线分治均摊

容易发现，每个询问是独立的，但是值越大，商品数量好像越多越有利。
简单来说，就是询问递增，那么商品数量不递减，所以按照询问值排序。

#include <bits/stdc++.h>
#define N 200050
using namespace std;
int n, m, i, j, k, a[N];
long long ans[N];
struct AB{
    int c, i;
    bool operator < (const AB &A) const{
        return c < A.c;
    }
} d[N];
void dfs(int x, int y, int l, int r){
    if(l > r)  return;
    long long m=l+r>>1, i, j, k, s=0, c=d[m].c;
    for(i=x; i<=y; i++){
        if((a[i]+c)*(n-i+1) > s){
            s = (a[i]+c)*(n-i+1);
            k = i;
        }//n-i+1个商品，单价是a[i]+c
    }//不妨先解决中间的询问
    ans[d[i=j=m].i] = s;//相等之间记录答案，避免被卡
    while(d[++j].c == d[m].c) ans[d[j].i] = s;
    while(d[--i].c == d[m].c) ans[d[i].i] = s;
    dfs(k, y, l, i);//小的询问在右边
    dfs(x, k, j, r);//大的询问在左边
}//询问[l, r]的答案，在商品[x, y]之间
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    sort(a+1, a+n+1);
    for(i=1; i<=m; i++){
        scanf("%d", &d[i].c);
        d[i].i = i;
    }
    sort(d+1, d+m+1);
    d[0].c = d[m+1].c = -1;//哨兵
    dfs(1, n, 1, m);
    for(i=1; i<=m; i++) printf("%lld ", ans[i]);
    return 0;
}