2020牛客多校第八场K题
__int128(例题：2020牛客多校第八场K题)
题意:
有n道菜，第i道菜的利润为\(a_i\)，且有\(b_i\)盘。你要按照下列要求给顾客上菜。
1.每位顾客至少有一道菜
2.给顾客上菜时，都必须从第一道菜开始，上连续的编号的菜，例如，你可能给一位顾客 上的菜为第一道，第二道，第三道，但是不能为只上第二道而不上第一道，或者第一道，第三道中间缺少第二道。求这些菜能够容纳的最大顾客数，并且求出在容纳最多顾客时的利润最大为多少。
输入输出
有t组样例，没组样例第一行为\(n\)，表示有n道菜，接下来共有两行，第一行n个数\(a_1,a_2 … a_n\)，第i个数表示第i种菜的利润，第二行为n个数\(b_1,b_2…b_n\)，第i个数表示第i种菜的个数。
数据范围
\(1\le n\le 10^{5}\),\(-10^{9}\le a_i\le10^{9}\),\(1\le b_i\le10^{5}\)
输入
2
3
2 -1 3
3 2 1
4
3 -2 3 -1
4 2 1 2
输出
Case #1: 3 8
Case #2: 4 13
说明
对于测试案例1，最大访问者数量为3，一种可能的解决方案是：
第一位访客获得食物1，利润是2。
第二位访客获得食物1，利润为2。
第三位访客获得食物1 +食物2 +食物3，利润为2 +（-1）+ 3。
题解
1.由于必须上第一道菜，因此第一道菜的数量即为最大招待顾客的数量。
2.计算最大利润时，采用贪心策略，在满足条件时，优先选取利润最大的即可，由于每次选取 1~i的连续的菜，可以先求出前i份菜的利润的前缀和。然后按利润前缀和大小排序，从大到小遍历，对于前n份菜利润为sum的贡献计算方法为，求出前n种菜剩余的菜的最小的数量 min，让答案累加\(min*sum\),然后将前n种菜的数量都减去min,这个操作可以用线段树来进行区间查询和修改。
3.由于答案最大值为 \(10^{19}\),稍微超过了long long int的范围，因此c++要采用 __int128，__int128为128位的整数，是gcc的扩展，大小范围在 [\(2^{127},2^{127}-1\)].且在windows环境下的gcc不支持编译，在linux环境下的gcc支持编译，不过没有对应的输入输出函数，要自定义输入输出函数。
__int128模板
`inline __int128 read(){//读入
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void fprint(__int128 x){//输出。
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
fprint(x/10);
putchar(x%10+'0');
}`
题目完整code
#include<bits/stdc++.h>
#define scd(x) scanf("%d",&x)
#define scdd(x,y) scanf("%d%d",&x,&y)
#define sclld(x) scanf("%lld",&x)
#define sclldd(x,y) scanf("%lld%lld",&x,&y)
#define print(x) cout<<x<<endl
#define CLR(a) memset(a,0,sizeof(a))
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;
typedef long long ll;
typedef double db;
const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const ll mod = ll(1e9)+7;
const int maxn=int(2e5)+500;
template<typename tp>inline tp lowbit(tp x){return x&(-x);}
template<typename tp_>void debug(tp_ x) {cout<<"*********** "<<x<<" *************"<<endl;}
template<typename tp1_,typename tp2_>void debug(tp1_ x,tp2_ y){cout<<"*********** "<<x<<" "<<y<<" *************"<<endl;}
struct P{int x;__int128 y;P(){}P(int _x,__int128 _y):x(_x),y(_y){}};
bool cmp(const P elem1,const P elem2){
if(elem1.y==elem2.y)return elem1.x>elem2.x;
return elem1.y<elem2.y;
}
__int128 a[maxn];
__int128 b[maxn];
P sum[maxn];
int Case = 1;
struct node{
__int128 sum;
__int128 lazy;
}tree[maxn<<2];
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void fprint(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
fprint(x/10);
putchar(x%10+'0');
}
void build(int rt,int l,int r){
tree[rt].sum=tree[rt].lazy=0;
if(l==r){
tree[rt].sum = b[l];
return ;
}
int mid = (l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
tree[rt].sum = min(tree[ls].sum,tree[rs].sum);
}
void pushdown(int rt,int l,int r){
if(tree[rt].lazy){
__int128 val = tree[rt].lazy;
tree[ls].sum-=val;
tree[rs].sum-=val;
tree[ls].lazy += val;
tree[rs].lazy += val;
tree[rt].lazy = 0;
}
}
void update(int rt,int l,int r,int L,int R,__int128 val){
if(l>=L&&r<=R){
tree[rt].sum -=val;
tree[rt].lazy += val;
return ;
}
pushdown(rt,l,r);
int mid= (l+r)>>1;
if(L<=mid)update(ls,l,mid,L,R,val);
if(R>mid)update(rs,mid+1,r,L,R,val);
tree[rt].sum = min(tree[ls].sum,tree[rs].sum);
}
__int128 ask(int rt,int l,int r,int L,int R){
if(l>=L&&r<=R){
return tree[rt].sum;
}
pushdown(rt,l,r);
int mid = (l+r)>>1;
__int128 res = inf;
if(L<=mid)res=min(res,ask(ls,l,mid,L,R));
if(R>mid)res=min(res,ask(rs,mid+1,r,L,R));
return res;
}
void solve() {
int n;
scd(n);
sum[0].y = 0;
for(int i=1;i<=n;i++){
a[i]=read();
sum[i].x=i;
sum[i].y=a[i]+sum[i-1].y;
}
for(int i=1;i<=n;i++)b[i]=read();
sort(sum+1,sum+n+1,cmp);
__int128 visit = b[1];
build(1,1,n);
__int128 ans = 0;
for(int i=n;i>=1;i--){
__int128 cnt = ask(1,1,n,1,sum[i].x);
ans+= cnt*sum[i].y;
update(1,1,n,1,sum[i].x,cnt);
}
printf("Case #%d: ",Case);
fprint(visit);
printf(" ");
fprint(ans);
printf("\n");
}
void Main(){
int _;
scd(_);
while(_--)
solve(),++Case;
}
//#define _Debug
int main(){
#ifdef _Debug
freopen("data.in","r",stdin);
clock_t b = clock();
Main();
clock_t e = clock();
cout<<"the time of cost is "<<(e-b)<<endl;
#else
Main();
#endif
return 0;
}
