Description
All modern mobile applications are divided into free and paid. Even a single application developers often release two versions: a paid version without ads and a free version with ads.
Suppose that a paid version of the app costs $ p $ ( $ p $ is an integer) rubles, and the free version of the application contains $ c $ ad banners. Each user can be described by two integers: $ a_{i} $ — the number of rubles this user is willing to pay for the paid version of the application, and $ b_{i} $ — the number of banners he is willing to tolerate in the free version.
The behavior of each member shall be considered strictly deterministic:
- if for user $ i $ , value $ b_{i} $ is at least $ c $ , then he uses the free version,
- otherwise, if value $ a_{i} $ is at least $ p $ , then he buys the paid version without advertising,
- otherwise the user simply does not use the application.
Each user of the free version brings the profit of $ c×w $ rubles. Each user of the paid version brings the profit of $ p $ rubles.
Your task is to help the application developers to select the optimal parameters $ p $ and $ c $ . Namely, knowing all the characteristics of users, for each value of $ c $ from $ 0 $ to $ (max b_{i})+1 $ you need to determine the maximum profit from the application and the corresponding parameter $ p $ .
Solution
发现$p$的最优值肯定是某个用户的$a$
先将所有用户按照$b$排序，那么枚举$c$时就可以单调地将每个用户加入一个数据结构，广告费可以$O(1)$计算，现在只需要考虑软件付费
设$d_i$表示$p$值为$i$时产生的总收益，那么加入一个用户时会对所有$i < a$的$d$增加一个$i$，相当于区间加等差数列
可以在值域上分块，对于完整的块更改标记，不完整的块暴力重建
每次查询的时候对每个块中的最大值求$max$即可
现在考虑如何找到每个块中的最大值
设标记为$cnt$，那么当$i < j$且$d_i+i imes cnt < d_j +j imes cnt$，有
$$frac{d_i - d_j}{j-i} leq cnt$$
那么在每个块内用队列维护一个下凸壳即可
#include<algorithm> #include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,w,B,blo[100005],q[320][320],h[320],t[320],pos=1,cnt[320],maxa; long long d[100005]; struct Node{ int a,b; bool operator < (const Node &z)const{return b<z.b;} }node[100005]; inline int read(){ int w=0,f=1; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return w*f; } double slope(int x,int y){return 1.0*(d[x]-d[y])/(y-x);} void solve(int x){while(h[x]<t[x]&&slope(q[x][h[x]],q[x][h[x]+1])<=cnt[x])++h[x];} void insert(int x){ if(!x)return; for(int i=1;i<blo[x];i++)++cnt[i],solve(i); int l=(blo[x]-1)*B+1,r=min(blo[x]*B,maxa),id=blo[x]; for(int i=l;i<=r;i++)d[i]+=1ll*cnt[id]*i; for(int i=l;i<=x;i++)d[i]+=i; h[id]=1,t[id]=0; for(int i=l;i<=r;i++){ while(h[id]<t[id]&&slope(q[id][t[id]-1],q[id][t[id]])>=slope(q[id][t[id]],i))--t[id];; q[id][++t[id]]=i; } cnt[id]=0,solve(id); } int main(){ n=read(),w=read(); for(int i=1;i<=n;i++)node[i]=(Node){read(),read()},maxa=max(maxa,node[i].a); sort(node+1,node+n+1),B=sqrt(maxa); for(int i=1;i<=maxa;i++)blo[i]=(i-1)/B+1; for(int i=1;i<=blo[maxa];i++)h[i]=t[i]=1,q[i][1]=min(maxa,i*B); for(int c=0;c<=node[n].b+1;c++){ while(pos<=n&&node[pos].b<c)insert(node[pos].a),++pos; long long ans1=0,ans2=0; for(int i=1;i<=blo[maxa];i++){ int x=q[i][h[i]]; if(1ll*cnt[i]*x+d[x]>ans1)ans1=1ll*cnt[i]*x+d[x],ans2=x; } printf("%I64d %I64d ",ans1+1ll*w*c*(n-pos+1),ans2); } return 0; }