锐客网

  1. 首页 > it技术 > >

牛客网 练习赛25 B最长区间

线段树

链接：https://www.nowcoder.com/acm/contest/158/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述 给你一个长度为 n 的序列 a ，求最长的连续的严格上升区间的长度。
同时会进行 m 次修改，给定 x , y ，表示将 ax 修改为 y ,每次修改之后都要求输出答案。
输入描述:

第一行 2 个数 n,m，表示序列长度，修改次数； 接下来一行 n 个数表示； 接下来 m 行，每行 2 个数 x , y ，描述一次修改。

输出描述:
第一行 1 个数表示最初的答案； 接下来 m 行，第 i 行 1 个数表示第 i 次修改后的答案。


示例1
输入 复制
4 3 1 2 3 4 3 1 2 5 3 7

输出 【牛客网 练习赛25 B最长区间】复制
4 2 2 3

说明
序列变换如下： 1234 1214 1514 1574

备注:
n,m ≤ 100000,1 ≤ x ≤ n，1 ≤ ai,y ≤ 100

解法1：
线段树维护区间最长严格递增子序列
#include #define lson l,mid,(rt<<1) #define rson (mid+1),r,(rt<<1|1) using namespace std; const int MAXN = 100005; struct node{ int l,r; // 当前节点区间左右端点 int lsum,rsum,msum; // 当前节点 左侧部分LICS 、 右侧 LCIS 、 总的最大的LCIS int mid(){ return (l+r) >> 1; } }; node tree[MAXN << 2]; int num[MAXN]; void pushUp(int rt){ // 初始为 左右孩子 中最大的 msum tree[rt].msum = max(tree[rt<<1].msum,tree[rt<<1|1].msum); tree[rt].lsum = tree[rt<<1].lsum; // 初始为 对应的 LCIS (lsum 对应左孩子的LCIS、右孩子 对应右侧LCIS) tree[rt].rsum = tree[rt<<1|1].rsum; // 如果 左儿子最右侧值 小于 右儿子 最左侧值 则 更新 父节点的 lsum,rsum,msum if(num[tree[rt<<1].r] < num[tree[rt<<1|1].l]){ int mid = tree[rt].mid(); if(tree[rt<<1].lsum == mid-tree[rt].l + 1){ // lsum 的LCIS 长度等于其对应区间长度 说明 该区间整体严格递增（更新：加上右侧递增部分长度） tree[rt].lsum += tree[rt<<1|1].lsum; } if(tree[rt<<1|1].rsum == tree[rt].r-mid){//同上 tree[rt].rsum += tree[rt<<1].rsum; } tree[rt].msum = max(tree[rt].msum,tree[rt<<1].rsum + tree[rt<<1|1].lsum); } }void build(int l, int r, int rt){ tree[rt].l = l; tree[rt].r = r; if(l == r){ tree[rt].lsum = tree[rt].rsum = tree[rt].msum = 1; return; } int mid = (l+r) >> 1; build(lson); build(rson); pushUp(rt); }void update(int a, int b, int rt){ if(tree[rt].l == tree[rt].r){ num[a] = b; return; } int mid = tree[rt].mid(); if(a <= mid) update(a,b,rt<<1); else update(a,b,rt<<1|1); pushUp(rt); }int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m,t; cin >> n >> m; for(int i = 1; i <= n; ++i){ cin >> num[i]; } build(1,n,1); cout << tree[1].msum << endl; int a,b; while(m--){ cin >> a >> b; update(a,b,1); cout << tree[1].msum << endl; }return 0; }


解法2：
每次只影响改变位置之后的位置，注意题目最长序列为100，依据此可以进行优化。
#include #include #include #include #include #include #include #include #include using namespace std; const int N = 100005; int dp[N]; int sum[N]; int a[N]; int solve(){ for(int i = N; i > 0; --i){ if(sum[i] > 0) return i; } }int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; memset(sum,0,sizeof(sum)); cin >> n >> m; fill(dp,dp+N,1); for(int i = 1; i <= n; ++i){ cin >> a[i]; } for(int i = 2; i <= n; ++i){ if(a[i-1] < a[i]){ dp[i] = max(dp[i],dp[i-1]+1); } ++sum[dp[i]]; }//int ans = *max_element(dp+1,dp+n+1); int ans = solve(); cout << ans <> x >> v; --sum[dp[x]]; a[x] = v; if(x > 1){ if(a[x-1] < a[x]){ dp[x] = dp[x-1] + 1; } else{ dp[x] = 1; } } else{ dp[x] = 1; } ++sum[dp[x]]; for(int i = x+1; i <= n; ++i){ --sum[dp[i]]; if(a[i-1] < a[i]){ dp[i] = dp[i-1] + 1; } else{ dp[i] = 1; } ++sum[dp[i]]; }//int ans = *max_element(dp+1,dp+n+1); int ans = solve(); cout << ans <


    推荐阅读


    上一篇：javaweb可能用到的库包

    下一篇：Python输出菱形程序