f_{i,j}

di​按从大到小排序这并不会影响答案。

因此用平衡树维护即可操作一对应区间平移操作二对应前缀减

复杂度

j1仍然不可能成为答案。

考虑是一条直线来截每个点使得截矩最大因为斜率是整数而相邻两点间斜率之差又不超过

remark

p){t[p].szt[t[p].l].szt[t[p].r].sz1;

int

val){tot;t[tot].fixgen(),t[tot].lt[tot].rt[tot].tag0,t[tot].sz1,t[tot].valval;return

tot;

x){if(!p)return;t[p].valx,t[p].tagx;

void

p){if(t[p].tag)add(t[p].l,t[p].tag),add(t[p].r,t[p].tag),t[p].tag0;

int

xy;if(t[x].fixt[y].fix){pushdown(x);t[x].rmerge(t[x].r,y);pushup(x);return

x;}else{pushdown(y);t[y].lmerge(x,t[y].l);pushup(y);return

y;}

val){if(!rt){xy0;return;}pushdown(rt);if(t[rt].valval){xrt;split0(t[x].r,t[x].r,y,val);pushup(x);}else{yrt;split0(t[y].l,x,t[y].l,val);pushup(y);}

void

val){if(!rt){xy0;return;}pushdown(rt);if(t[t[rt].l].sz1val){xrt;split1(t[x].r,t[x].r,y,val-t[t[rt].l].sz-1);pushup(x);}else{yrt;split1(t[y].l,x,t[y].l,val);pushup(y);}

int

x){pushdown(x);if(t[x].l)dfs(t[x].l);c[cnt]t[x].val;if(t[x].r)dfs(t[x].r);

int

main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinT;while(T--){cinnstr;for(int

sm0;int

i1;in;i){if(r[i]b[i]){smb[i];continue;}else

x,y;split0(rt,x,y,r[i]-b[i]);rtmerge(x,merge(newnode(r[i]-b[i]),y));}else{smr[i];int

x,y;split1(rt,x,y,min(1ll*c1,r[i]-b[i]));if(!x||!y){add(x,-1);rtxy;}else{int

_xrs(x),_yls(y);if(t[_x].valt[_y].val){ll

valt[_x].val;int

a,b,c,d;split0(x,a,b,val1);split0(y,c,d,val);add(a,-1),add(b,-1);rtmerge(merge(a,c),merge(b,d));}else{add(x,-1);rtmerge(x,y);}}}}cnt0,dfs(rt);ll

ressm;for(int

i1;ic1;i){smc[i],resmax(res,sm);}coutres\n;}