线段树，
a的意义为每一排实际坐着的人数
f的意义为0~n-1中某段区间中坐着的人数最小值，那么显然如果最小值如果小于m-k，那么我们可以深入这段区间中寻找坐着的人数小于m-k的最靠前的排-----对应gather操作
p的意义为0~n-1中某段区间中坐着人数和，如果此段区间中的作为减去人数和<K，那么显然无法再坐人----对应scatter操作
同时每一次成功坐人我们都要更新a/f/p数组
同时要注意数组的数据范围，p是记录人数和的数组所以会爆Int
class BookMyShow {
int N=50010;
int [] a=new int[N];
int [] f=new int[4*N];
long [] p=new long[4*N];
int n=0;
int m=0;
public BookMyShow(int n1, int m1) {
n=n1;
m=m1;
}
public int check(int c,int l,int r,int num){ //check函数返回人数小于等于num的最小排号
if(f[c]>num) return 0x3f3f3f3f;
if(l==r) return l;
int mid=l+r>>1;
if(f[c+c]<=num) return check(c+c,l,mid,num);
if(f[c+c+1]<=num) return check(c+c+1,mid+1,r,num);
return 1;
}
/*
public void add(int c,int l,int r,int x,int k){
}
*/
public void add(int c,int l,int r,int x,int k){
if(l==r){
a[l]+=k;
f[c]+=k;
p[c]+=k;
return;
}
int mid=l+r>>1;
if(x<=mid) add(c+c,l,mid,x,k);
else add(c+c+1,mid+1,r,x,k);
f[c]=Math.min(f[c+c],f[c+c+1]);
p[c]=p[c+c]+p[c+c+1];
}
public int[] gather(int k, int maxRow) {
List<Integer> list=new ArrayList();
int c=check(1,0,n-1,m-k);
if(c>maxRow) return list.stream().mapToInt(Integer::intValue).toArray();
else{
list.add(c);
list.add(a[c]);
add(1,0,n-1,c,k);
return list.stream().mapToInt(Integer::intValue).toArray();
}
}
public long sum(int c,int l,int r,int kl,int kr){
if(l==kl&&r==kr) return p[c];
int mid=l+r>>1;
if(kr<=mid) return sum(c+c,l,mid,kl,kr);
if(kl>=mid) return sum(c+c+1,mid,r,kl,kr);
return sum(c+c,l,mid,kl,mid)+sum(c+c+1,mid+1,r,mid+1,kr);
}
public boolean scatter(int k, int maxRow) {
if((maxRow+1)*(long)m-sum(1,0,n-1,0,maxRow)<k) return false;
else{
int d=0;
while(k>0){
if(a[d]==m) {
d++;
continue;
}
else{
int left=m-a[d];
if(left>=k){
add(1,0,n-1,d,k);
return true;
}else{
k-=m-a[d];
add(1,0,n-1,d,left);
d++;
}
}
}
return true;
}
}
}
