首页 > 代码库 > FZU 2059 MM
FZU 2059 MM
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+7;const int N = 100005 ;#define X first#define Y secondint n , q , a[N] ;struct OK { int vis[N] , l[N] , r[N] ; void init() { memset( vis , false , sizeof vis ) ; for( int i = 1 ; i <= n ; ++i ) l[i] = r[i] = i ; } int GetLen( int i ) { return r[i] - l[i] + 1 ; } void Relax( int i ) { if( vis[i+1] ) r[i] = r[i+1]; if( vis[i-1] ) l[i] = l[i-1] , r[l[i-1]] = r[i] ; if( vis[i+1] ) l[r[i+1]] = 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 = 1 ; i <= n ; ++i ) cout << e.l[i] << ‘ ‘ ; cout << endl ; for( int i = 1 ; i <= n ; ++i ) cout << e.r[i] << ‘ ‘ ; cout << endl ; for( int i = 1 ; i <= n ; ++i ) cout << p[i].x << ‘ ‘ << p[i].res << endl ;}void Solve() { for( int i = 1 ; i <= n ; ++i ) { p[i].x = a[i] , p[i].id = i ; } sort( p + 1 , p + n + 1 ) ; e.init(); p[n+1].res = 0 ; for( int i = n ; i > 0 ; --i ) { int id = p[i].id ; e.vis[id] = true ; e.Relax(id); p[i].res = max( p[i+1].res , e.GetLen( p[i].id )); }}int Find( int num ) { int l = 1 , r = n , pos = 0 ; if( num > p[n].x ) return 0; while( l <= r ) { int mid = (l+r)>>1; if( p[mid].x < num ) l = mid + 1 ; else pos = mid , r = mid - 1 ; } return p[pos].res;}void Run() { for( int i = 1 ; i <= n ; ++i ) { scanf("%d",&a[i]); } Solve();// test(); while(q--){ int op , x , y ; scanf("%d%d",&op,&x); if( op == 1 ){ 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();}
FZU 2059 MM
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。