T2T3真就***写了线段树主席树，T4倒是推了半天斜率优化式子（一开始推错了）以为斜率不递增怒敲cdq分治。。。发现式子推错之后以为只要上二分就可以。最后调试才发现并不是后面所有格子都可以产生贡献 /fad