Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet last数组、预处理、优化

My Solution

题意：给出n*m个树，询问第i行到第j行是否至少有一列是非递减序列。

预处理、last数组、优化

用 vector f[maxn]，其中f[i]表示第i列的数据，

然后O(n*m)的标出非递减状态结束时的点。

然后用lastj[j]表示上一次处理时访问到的非递减状态结束时的点的下一个点。

所以对于每个0 < i < n 预处理出ans[i]表示i为起点的存在的最长的非递减序列的长度，对于每个1 <= j <= m，扫到本次非递减状态结束的点然后刷新last[j]。

克制当 last[j] > i 时不用扫第j列了，直接 ans[i] = max(ans[i], last[j] - i); 然后contine;

通过last数组的优化，在获得ans[i]的过程中每一个元素 f[i][j]只会访问一次，

所以 复杂度 O(n*m <= 1e5)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

vector f[maxn];
int ans[maxn], last[maxn];

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m, i, j, a, k, l, r;
    cin >> n >> m;
    for(i = 0; i < n; i++){
        for(j = 1; j <= m; j++){ cin >> a;
            f[j].push_back(a);
        }
    }
    for(j = 1; j <= m; j++){
        f[j].push_back(-1);
    }

    for(j = 1; j <= m; j++){
        for(i = 0; i < n; i++){ if(f[j][i] > f[j][i+1]){
                f[j][i] = 1;
            }
            else f[j][i] = 0;
        }
    }
    for(i = 0; i < n; i++){
        ans[i] = 1;
        for(j = 1; j <= m; j++){ if(last[j] > i){
                ans[i] = max(ans[i], last[j] - i);
                continue;
            }
            for(k = i; k < n; k++){ if(f[j][k] == 1){ ans[i] = max(ans[i], k - i + 1); last[j] = k + 1; break; } } } } cin >> k;
    while(k--){
        cin >> l >> r;
        if(ans[l-1] >= (r - l + 1)) cout << "Yesn";
        else cout << "Non";
    }

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx