[ICPC Blog OJ] MTF July 2017 E - height 1

題目連結：https://oj.icpc.tw/contest/9/problem/E

我們可以先想一下，對於某個區間L,R，你要怎麼Ｏ(1)判斷他能不能利用Ｋ分來使這個區間變成最長連續同值區間。

既然要變成最長連續同值區間，一定是使所有值變成該區間內的最大值，而需要多少分才能辦到就等同於將區間最大值乘以區間長度減掉區間和。可利用sparse table以及前綴和來實作。

我們便可以窮舉所有區間，但顯然會TLE。

但在當我們窮舉右界時，其左界具有單調性，因此只要滑過去，一邊取區間長度的max就好。

#include <iostream>
#include <vector>
#define N 1000005
#define PB push_back
using namespace std;
int n,k;
int a[N];
int logg(int l,int r){return 31 - __builtin_clz(r-l+1);}
vector <int> s[20];
bool check(int aa,int bb){
    int tt = logg(aa,bb);
    int mm = max(s[tt][aa-1],s[tt][bb-(1 << tt)]);
    int tmp = mm * (bb-aa+1) - a[bb] + a[aa-1];
    if(tmp <= k)return 1;
    return 0;
}
int main(){
    int T;cin >> T;
    while(T--){
        for(int i = 0; i < 20 ; i++)s[i].clear();
        cin >> n >> k;
        for(int i = 1 ; i <= n ; i++){
            cin >> a[i];
            s[0].PB(a[i]);
            a[i] += a[i-1];
        }
        for(int i = 1 ; (1 << i) <= n; i++)
            for(int j = 0 ; j+(1<<i) <= n ; j++)
                s[i].PB(max(s[i-1][j],s[i-1][j+(1 <<(i-1))]));
        int l = 1,ans = 1;
        for(int i = 2 ; i <= n ; i++){
            while(!check(l,i))l++;
            ans = max(ans,i-l+1);
        }       
        cout << ans <<endl;
    } 
    return 0;
}