FZU 2059 MM
2024-10-07 15:51:26
Description
There is a array contain N(1<N<=100000) numbers. Now give you M(1<M<10000) query.
Every query will be:
1 x : ask longest substring which every number no less than x
2 y x : change the A[y] to x. there are at most change 10 times.
For each ask can you tell me the length of longest substring.
Input
There are multiple tests.
each test first line contain two integer numbers N M,second line contain N integer numbers.
Next M lines each line will be:
1 x : ask longest substring which every number no less than x
2 y x : change the A[y] to x. there are at most change 10 times.
0 < N <= 100000, 0 < M <= 10000, -1000000000 <= A[i] <= 1000000000
Output
Each ask output the length of longest substring .
Sample Input
5 5
1 2 3 2 1
1 2
1 3
2 3 1
1 2
1 3
Sample Output
3
1
1
0
预处理出N个数值能到达的最大长度 。
按照数值从大到小插入。
然后记录一个 vis[i] , l[i] , r[i] 。
表示这个数据是否插入 , 向左能到达最远哪里 , 向右能到达最远哪里 。
操作1就直接2分答案。
操作2因为最多10个,就直接暴力来一次
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <algorithm> using namespace std; typedef long long LL;
typedef pair<int,int> pii;
const int mod = 1e9+;
const int N = ;
#define X first
#define Y second int n , q , a[N] ; struct OK {
int vis[N] , l[N] , r[N] ;
void init() {
memset( vis , false , sizeof vis ) ;
for( int i = ; i <= n ; ++i ) l[i] = r[i] = i ;
}
int GetLen( int i ) {
return r[i] - l[i] + ;
}
void Relax( int i ) {
if( vis[i+] ) r[i] = r[i+];
if( vis[i-] ) l[i] = l[i-] , r[l[i-]] = r[i] ;
if( vis[i+] ) l[r[i+]] = l[i];
}
}e;
struct node{
int x , res , id ;
bool operator < ( const node &a ) const {
return x < a.x ;
}
}p[N]; void test() {
for( int i = ; i <= n ; ++i ) cout << e.l[i] << ' ' ; cout << endl ;
for( int i = ; i <= n ; ++i ) cout << e.r[i] << ' ' ; cout << endl ;
for( int i = ; i <= n ; ++i )
cout << p[i].x << ' ' << p[i].res << endl ;
} void Solve() {
for( int i = ; i <= n ; ++i ) {
p[i].x = a[i] , p[i].id = i ;
}
sort( p + , p + n + ) ;
e.init(); p[n+].res = ;
for( int i = n ; i > ; --i ) {
int id = p[i].id ;
e.vis[id] = true ;
e.Relax(id);
p[i].res = max( p[i+].res , e.GetLen( p[i].id ));
}
} int Find( int num ) { int l = , r = n , pos = ;
if( num > p[n].x ) return ;
while( l <= r ) {
int mid = (l+r)>>;
if( p[mid].x < num )
l = mid + ;
else
pos = mid , r = mid - ;
}
return p[pos].res;
} void Run() {
for( int i = ; i <= n ; ++i ) {
scanf("%d",&a[i]);
}
Solve();
// test();
while(q--){
int op , x , y ;
scanf("%d%d",&op,&x);
if( op == ){
printf("%d\n",Find(x));
}
else {
scanf("%d",&y);
a[x] = y ; Solve();
// test();
}
}
} int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif // LOCAL
while( scanf("%d%d",&n,&q)!=EOF )Run();
}
最新文章
- 关于js的闭包
- 自己写了个H5版本的俄罗斯方块
- springVS javaee
- android 列表开发 ListView
- (剑指Offer)面试题22:栈的压入、弹出序列
- Winform下实现图片切换特效的方法
- 查看buffer cache命中率
- 学习笔记之DB2 9 Fundamentals 730
- java学习笔记--1_常见输入输出语句熟悉篇章
- Android动画总结#补间动画(Tween Animation/View Animation) #帧动画(Frame Animation/Drawable Animation)#属性动画(PropertyAnimation)
- CASE WHEN的两种格式
- VS2010查看源码对应的汇编语言
- sql查询(转)
- Power BI数据网关
- Vue--父子组件之间的传值
- HTML5之IndexedDB使用详解
- java.lang.OutOfMemoryError 错误分类
- RoadFlow ASP.NET Core工作流引擎IIS部署
- PTA (Advanced Level) 1016 Phone Bills
- openresty 几个插件使用