LCIS HDU - 3308 （线段树区间合并）
2024-09-02 16:05:35
LCIS HDU - 3308
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
InputT in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10 5).
The next line has n integers(0<=val<=10 5).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10 5)
OR
Q A B(0<=A<=B< n).
OutputFor each Q, output the answer.Sample Input
1
10 10
7 7 3 3 5 9 9 8 1 8
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9
Sample Output
1
1
4
2
3
1
2
5
个人思路：这道题应该算是线段树区间合并的板子题，关键就是明确区间合并时的逻辑关系就可以了
我因为忽略区间内的最长连续上升序列有可能由子区间的区间内连续上升序列得到而错了好几次
//线段树区间合并
//关键：明确相邻区间合并时候的逻辑关系
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define mem(a,x) memset(a,x,sizeof(a))
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid + 1,r
#define P pair<int,int>
#define ull unsigned long long
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
const int inf = 0x3f3f3f3f; struct node
{
int l,r;
int left ,right ,mid;
int maxx;
}tree[maxn << ]; int n,m;
int arr[maxn]; void Pushup(int rt)
{
tree[rt].left = tree[rt << ].left;
tree[rt].right = tree[rt << |].right;
bool flag = arr[tree[rt << |].l] > arr[tree[rt << ].r]; if(tree[rt << |].right == tree[rt << |].r - tree[rt << |].l + && flag)
{
tree[rt].right += tree[rt << ].right;
}
// 合并以左端点为头的最长序列 if(tree[rt << ].left == tree[rt << ].r - tree[rt << ].l + && flag)
{
tree[rt].left += tree[rt << |].left;
}
// 合并以右端点为尾的最长序列 if(arr[tree[rt << |].l] > arr[tree[rt << ].r])
{
tree[rt].mid = tree[rt << ].right + tree[rt << |].left;
}
else
{
tree[rt].mid = max(tree[rt << ].right , tree[rt << |].left);
}
tree[rt].mid = max(tree[rt].mid , max(tree[rt << ].mid,tree[rt << |].mid));
// 获得区间内的最长序列：可能由子区间构成 也可能从子区间得到
tree[rt].maxx = max(tree[rt].mid, max(tree[rt].left , tree[rt].right));
} void build(int rt ,int l ,int r)
{
tree[rt].l = l , tree[rt].r = r;
if(l == r)
{
tree[rt].left = tree[rt].right = tree[rt].maxx = tree[rt].mid = ;
return;
}
int mid = l + r >> ;
build(lson);
build(rson);
Pushup(rt);
} void update(int rt ,int k ,int v)
{
if(tree[rt].l == k && tree[rt].r == k)
{
arr[k] = v;
tree[rt].left = tree[rt].right = tree[rt].maxx = tree[rt].mid = ;
return;
}
int mid = tree[rt].l + tree[rt].r >> ;
if(mid >= k)
{
update(rt << , k , v);
}
else
{
update(rt << | , k , v);
}
Pushup(rt);
} int query(int rt , int l ,int r)
{
if(tree[rt].l == l && tree[rt].r == r)
{
return tree[rt].maxx;
}
int mid = tree[rt].l + tree[rt].r >> ;
if(mid >= r)
{
return query(rt << , l , r);
}
else if(mid < l )
{
return query(rt << | , l , r);
}
else
{
int m = min(mid - l + , tree[rt << ].right) + min(r - mid , tree[rt << |].left);
int left = query(rt<< ,l ,mid);
int right = query(rt << | , mid + , r);
if(arr[tree[rt << ].r] < arr[tree[rt << |].l])
{
return max(m,max(left , right));
}
else
{
return max(left , right);
}
}
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
//mem(arr,0);
scanf("%d %d",&n,&m);
for(int i = ; i <= n ; ++ i)
{
scanf("%d",&arr[i]);
}
build(,,n);
while(m -- )
{
char judge;
int l,r;
scanf(" %c %d %d",&judge ,&l , &r);
if(judge == 'U')
{
update(,l + ,r);
}
else
{
printf("%d\n",query(,l + , r + ));
}
}
}
return ;
}
AC代码
一个从很久以前就开始做的梦
最新文章
- Windows 常用运行库下载 (DirectX、VC++、.Net Framework等)
- LeetCode 【347. Top K Frequent Elements】
- 在Xcode 6 beta里编译Cocos2d-x iOS项目时失败
- Elasticsearch聚合 之 Terms
- git 创建分支并切换
- 【转】又一波你可能不知道的 Linux 命令行网络监控工具
- Mono 之 Jexus
- OC的类的构造方法
- HTML特殊符号对照表(转)
- 【译】 AWK教程指南 1前言
- C语言实现界面（不通过MFC\避免遗忘）
- MySQL的create table as 与 like区别(转)
- merge 语句的语法
- PXC5.7集群部署
- Ajax 的用法
- mysql8.0 定时创建分区表记录 每天定时创建下一天的分区表
- CORS——跨域请求那些事儿
- canvas-a13prototype.html
- 关于jQuery出现的新添加元素点击事件无效
- CRF++地名实体识别（特征为词性和词）