【HDU】3308 LCIS

 1 #include<cstdio>
 2 #define MAXN 100010
 3 struct node
 4 {
 5     int left,right,val;
 6 };
 7 int a[MAXN];
 8 node tree[MAXN<<2];
 9 inline int MAX(int x,int y)
10 {
11     return x>y?x:y;
12 }
13 inline int MIN(int x,int y)
14 {
15     return x>y?y:x;
16 }
17 inline void PushUp(int mid,int L,int R,int rt)
18 {
19     tree[rt].left=tree[rt<<1].left;
20     tree[rt].right=tree[rt<<1|1].right;
21     tree[rt].val=MAX(tree[rt<<1].val,tree[rt<<1|1].val);
22     if(a[mid]<a[mid+1])
23     {
24         if(tree[rt].left==mid-L+1)
25             tree[rt].left+=tree[rt<<1|1].left;
26         if(tree[rt].right==R-mid)
27             tree[rt].right+=tree[rt<<1].right;
28         tree[rt].val=MAX(tree[rt].val,tree[rt<<1].right+tree[rt<<1|1].left);
29     }
30 }
31 void Build(int L,int R,int rt)
32 {
33     if(L==R)
34     {
35         scanf("%d",&a[L]);
36         tree[rt].left=tree[rt].val=tree[rt].right=1;
37     }
38     else
39     {
40         int mid=(L+R)>>1;
41         Build(L,mid,rt<<1);
42         Build(mid+1,R,rt<<1|1);
43         PushUp(mid,L,R,rt);
44     }
45 }
46 void Update(int x,int val,int L,int R,int rt)
47 {
48     if(L==R)
49         a[L]=val;
50     else
51     {
52         int mid=(L+R)>>1;
53         if(mid>=x)
54             Update(x,val,L,mid,rt<<1);
55         else
56             Update(x,val,mid+1,R,rt<<1|1);
57         PushUp(mid,L,R,rt);
58     }
59 }
60 int Query(int x,int y,int L,int R,int rt)
61 {
62     if(x<=L&&R<=y)
63         return tree[rt].val;
64     int mid=(L+R)>>1,ans=0;
65     if(mid>=x)
66         ans=MAX(ans,Query(x,y,L,mid,rt<<1));
67     if(y>mid)
68         ans=MAX(ans,Query(x,y,mid+1,R,rt<<1|1));
69     if(a[mid]<a[mid+1])
70         ans=MAX(ans,MIN(mid-x+1,tree[rt<<1].right)+MIN(y-mid,tree[rt<<1|1].left));
71     return ans;
72 }
73 int main()
74 {
75     char ch;
76     int c,n,m,x,y;
77     scanf("%d",&c);
78     while(c--)
79     {
80         scanf("%d%d",&n,&m);
81         Build(1,n,1);
82         while(m--)
83         {
84             scanf(" %c%d%d",&ch,&x,&y);
85             if(ch=='U')
86                 Update(x+1,y,1,n,1);
87             else
88                 printf("%d\n",Query(x+1,y+1,1,n,1));
89         }
90     }
91     return 0;
92 }
新博客：www.zhixiangli.com