題目鏈接：

題目描述

給你一個長度為 n 的序列 a ，求最長的連續的嚴格上升區間的長度。
同時會進行 m 次修改，給定 x , y ，表示將 ax 修改為 y ,每次修改之后都要求輸出答案。

輸入描述:

第一行 2 個數 n,m，表示序列長度，修改次數； 接下來一行 n 個數表示 ； 接下來 m 行，每行 2 個數 x , y ，描述一次修改。

輸出描述:

第一行 1 個數表示最初的答案； 接下來 m 行，第 i 行 1 個數表示第 i 次修改后的答案。

輸入

4 3 1 2 3 4 3 1 2 5 3 7

輸出

4 2 2 3

說明

序列變換如下： 1 2 3 4 1 2 1 4 1 5 1 4 1 5 7 4

備注:

n,m ≤ 100000,1 ≤ x ≤ n，1 ≤ ai,y ≤ 100

AC

• 因為Y的范小，每次更新數字，只用100次更新就可以完成，最大值也可以在100次中找到，所以暴力就能做

#include <iostream> #include <stdio.h> #include <map> #include <vector> #include <set> #include <cstring> #include <cmath> #include <algorithm> #define N 100005 #define ll long long using namespace std; // VIS數組記錄所有存在的長度 // a 數組記錄原數據 // sum數組記錄 到當前數字為止，遞增序列的長度 int vis[105]; int a[N], sum[N]; // O(100) 找到最大值 void solve() {int ans = 1;for (int i = 2; i <= 100; ++i) {if (vis[i]) ans = i;}printf("%d\n", ans); }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}for (int i = 1; i <= n; ++i) {if (a[i] > a[i - 1])sum[i] = sum[i - 1] + 1;else sum[i] = 1;vis[sum[i]]++;}solve();for (int i = 0; i < m; ++i) {int x, y;scanf("%d%d", &x, &y);a[x] = y;// 每次修改之后更新 sum 和 vis for (int i = x; i <= min(x + 101, n); ++i) {vis[sum[i]]--;if (a[i] > a[i - 1])sum[i] = sum[i - 1] + 1;elsesum[i] = 1;vis[sum[i]]++;}solve();}return 0; }

總結

以上是生活随笔為你收集整理的牛客练习赛25 B-最长区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。