首页 > 代码库 > A. LCIS

A. LCIS

2024-07-11 19:43:33   219人阅读

A. LCIS

2000ms
2000ms
32768KB
 
64-bit integer IO format: %I64d      Java class name: Main
 
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].
 

Input

T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
 

Output

For each Q, output the answer.
 

Sample Input

110 107 7 3 3 5 9 9 8 1 8 Q 6 6U 3 4Q 0 1Q 0 5Q 4 7Q 3 5Q 0 2Q 4 6U 6 10Q 0 9
 

Sample Output

11423125

解题思路：线段树的区间合并。哎。。。写了三四遍才过的！！！！！！！！int lt,rt,lx,rx,mx,wth;依次为左边界，右边界，左上升区间长度，右上升区间长度，lt rt中的最大上升区间长度。

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int maxn = 100010; 5 struct node{ 6     int lt,rt,lx,rx,mx,wth; 7 }tree[maxn<<2]; 8 int d[maxn]; 9 void fix(int v,int mid){10     tree[v].lx = tree[v<<1].lx;11     tree[v].rx = tree[v<<1|1].rx;12     if(d[mid] < d[mid+1]){13         tree[v].lx += tree[v].lx == tree[v<<1].wth?tree[v<<1|1].lx:0;14         tree[v].rx += tree[v].rx == tree[v<<1|1].wth?tree[v<<1].rx:0;15         tree[v].mx = max(tree[v<<1].mx,tree[v<<1|1].mx);16         tree[v].mx = max(tree[v].mx,tree[v<<1].rx+tree[v<<1|1].lx);17     }else tree[v].mx = max(tree[v<<1].mx,tree[v<<1|1].mx);18 }19 void build(int lt,int rt,int v){20     tree[v].lt = lt;21     tree[v].rt = rt;22     tree[v].wth = rt-lt+1;23     if(lt == rt){tree[v].lx = tree[v].rx = tree[v].mx = 1;return;}24     int mid = (lt+rt)>>1;25     build(lt,mid,v<<1);26     build(mid+1,rt,v<<1|1);27     fix(v,mid);28 }29 void update(int u,int val,int v){30     int mid = (tree[v].lt+tree[v].rt)>>1;31     if(tree[v].lt == tree[v].rt) {d[tree[v].lt] = val;return;}32     if(u <= mid) update(u,val,v<<1);33     else update(u,val,v<<1|1);34     fix(v,mid);35 }36 int query(int lt,int rt,int v){37     if(tree[v].lt == lt && tree[v].rt == rt) return tree[v].mx;38     int mid = (tree[v].lt+tree[v].rt)>>1;39     if(rt <= mid) return query(lt,rt,v<<1);40     else if(lt > mid) return query(lt,rt,v<<1|1);41     else{42         int temp = max(query(lt,mid,v<<1),query(mid+1,rt,v<<1|1));43         if(d[mid] < d[mid+1]){44             temp = max(min(mid-lt+1,tree[v<<1].rx)+min(rt-mid,tree[v<<1|1].lx),temp);45             //看看合并是否可以使取值更优46         }47         return temp;48     }49 }50 int main(){51     int ks,n,m,i,x,y;52     char op[5];53     scanf("%d",&ks);54     while(ks--){55         scanf("%d %d",&n,&m);56         for(i = 1; i <= n; i++)57             scanf("%d",d+i);58             build(0,n,1);59         for(i = 0; i < m; i++){60             scanf("%s%d%d",op,&x,&y);61             if(op[0] == ‘Q‘){62                 printf("%d\n",query(x+1,y+1,1));63             }else update(x+1,y,1);64         }65     }66     return 0;67 }
View Code

 


联系
我们