牛客练习赛25—B最长区间(线段树)
题目链接:传送门
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述 【牛客练习赛25—B最长区间(线段树)】给你一个长度为 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
输出 复制
4 2 2 3
说明
序列变换如下: 1234 1214 1514 1574
备注:
n,m ≤ 100000,1 ≤ x ≤ n,1 ≤ ai,y ≤ 100
代码:
#include using namespace std;
#define lchild (rt<<1)
#define rchild (rt<<1|1)typedef long long llt;
const int INF = 0x3fffffff;
const int N = 100010;
const int M = 100010;
const double pi = acos(-1);
const int mod = 1e9+7;
struct Node{
int ls,rs,ns;
}node[N<<2];
int id[N];
void PushUp(int l,int r,int rt)
{
node[rt].ls = node[lchild].ls;
node[rt].rs = node[rchild].rs;
node[rt].ns = max(node[lchild].ns,node[rchild].ns);
int m = (l+r)>>1;
if(id[m] < id[m+1]){
if(node[lchild].ls == m-l+1) node[rt].ls += node[rchild].ls;
if(node[rchild].rs == r-m)node[rt].rs += node[lchild].rs;
node[rt].ns = max(node[rt].ns,node[lchild].rs+node[rchild].ls);
}
}void Build(int l,int r,int rt)
{
if(l == r){
node[rt].ls = node[rt].rs = node[rt].ns = 1;
return;
}
int m = (l+r)>>1;
Build(l,m,lchild);
Build(m+1,r,rchild);
PushUp(l,r,rt);
}void Update(int L,int C,int l,int r,int rt)
{
if(l == r){
id[l] = C;
return;
}
int m = (l+r)>>1;
if(L <= m) Update(L,C,l,m,lchild);
else Update(L,C,m+1,r,rchild);
PushUp(l,r,rt);
}int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;
i <= n;
++i){
scanf("%d",&id[i]);
}
Build(1,n,1);
printf("%d\n",node[1].ns);
int x,y;
for(int i = 0;
i < m;
++i){
scanf("%d%d",&x,&y);
Update(x,y,1,n,1);
printf("%d\n",node[1].ns);
}
return 0;
}
推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想()
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读,亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话(49)——一位清华教授在朋友圈给大学生的9条建议
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术