任意区间的最长连续递增子序列，最大连续子序列和

hdu3308

给n个数，有m个操作

U a b 表示将第a个数改成b

Q a b 表示询问区间[a,b]的最长连续递增子序列。

区间询问问题且带修改，一般是用线段树来解决

那么要维护

Llen[rt], Lval[rt][2] 表示rt所对应的区间[l,r] 以l开头的最长连续递增子序列的长度， Lval[rt][0]表示子序列的最左边的值，Lval[rt][1]表示子序列最右边的值

Rlen[rt],Rval[rt][2] 表示rt所对应的区间[l,r]以r结尾的最长连续递增子序列的长度， Rval[rt][0] 表示子序列最左边的值，Rval[rt][1]表示子序列最右边的值

Mlen[rt] 表示rt所对应的区间[l,r]最长连续递增子序列的长度

那么Llen[rt] 可能是左区间的Llen[rt<<1] ，也有可能是跨越左右两个孩子

Rlen[rt] 可能是右区间的Rlen[rt<<1|1], 页有可能是跨越左右两个孩子

Mlen[rt] 可能是左区间的Mlen[rt<<1],或者右区间的Mlen[rt<<1|1], 也有可能跨越左右两个区间

上面的状态转移时，也要注意一下val的改变。

具体的转移见代码

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 using namespace std;
  5 
  6 /*
  7 
  8 
  9 */
 10 const int N = 100000 + 10;
 11 int a[N];
 12 int Llen[N*4],Lval[N*4][2],Rlen[N*4],Rval[N*4][2],Mlen[N*4];
 13 
 14 void pushUp(int rt, int l, int r)
 15 {
 16     int mid = (l+r)>>1;
 17     int tmp = 0;
 18     if(Rval[rt<<1][1] < Lval[rt<<1|1][0])
 19         tmp = Rlen[rt<<1] + Llen[rt<<1|1];
 20     Mlen[rt] = max(tmp,max(Mlen[rt<<1],Mlen[rt<<1|1]));
 21     if(Llen[rt<<1]==mid-l+1 &&Lval[rt<<1][1] <Lval[rt<<1|1][0])
 22     {
 23         Llen[rt] = Llen[rt<<1] + Llen[rt<<1|1];
 24         Lval[rt][0] = Lval[rt<<1][0];
 25         Lval[rt][1] = Lval[rt<<1|1][1];
 26     }
 27     else
 28     {
 29         Llen[rt] = Llen[rt<<1];
 30         Lval[rt][0] = Lval[rt<<1][0];
 31         Lval[rt][1] = Lval[rt<<1][1];
 32     }
 33     if(Rlen[rt<<1|1]==r-mid && Rval[rt<<1|1][0]>Rval[rt<<1][1])
 34     {
 35         Rlen[rt] = Rlen[rt<<1] + Rlen[rt<<1|1];
 36         Rval[rt][0] = Rval[rt<<1][0];
 37         Rval[rt][1] = Rval[rt<<1|1][1];
 38     }
 39     else
 40     {
 41         Rlen[rt] = Rlen[rt<<1|1];
 42         Rval[rt][0] = Rval[rt<<1|1][0];
 43         Rval[rt][1] = Rval[rt<<1|1][1];
 44     }
 45 
 46 }
 47 void build(int l, int r, int rt)
 48 {
 49     if(l==r)
 50     {
 51         Llen[rt] = Rlen[rt] = Mlen[rt] = 1;
 52         Lval[rt][0] = Lval[rt][1] = Rval[rt][0] = Rval[rt][1] =  a[l];
 53         return ;
 54     }
 55     int mid = (l+r)>>1;
 56     build(l,mid,rt<<1);
 57     build(mid+1,r,rt<<1|1);
 58     pushUp(rt,l,r);
 59 }
 60 void update(int l, int r, int rt, int pos)
 61 {
 62     if(l==r)
 63     {
 64         Lval[rt][0] = Lval[rt][1] = Rval[rt][0] = Rval[rt][1] = a[l];
 65         return;
 66     }
 67     int mid = (l+r)>>1;
 68     if(pos<=mid)
 69         update(l,mid,rt<<1,pos);
 70     else
 71         update(mid+1,r,rt<<1|1,pos);
 72     pushUp(rt,l,r);
 73 }
 74 
 75 int llen,rlen,mlen,lval[2],rval[2];
 76 bool f;
 77 void query(int l, int r, int rt, int L, int R)
 78 {
 79     if(L<=l &&R>=r)
 80     {
 81        if(f)
 82        {
 83            f = false;
 84            llen = Llen[rt];
 85            rlen = Rlen[rt];
 86            mlen = Mlen[rt];
 87            lval[0] = Lval[rt][0];
 88            lval[1] = Lval[rt][1];
 89            rval[0] = Rval[rt][0];
 90            rval[1] = Rval[rt][1];
 91        }
 92        else
 93        {
 94             int tmp = 0;
 95             if(rval[1]<Lval[rt][0])
 96                 tmp = rlen + Llen[rt];
 97             mlen = max(max(mlen,Mlen[rt]),tmp);
 98             if(llen==l-L && lval[1] < Lval[rt][0])
 99             {
100                 llen = llen + Llen[rt];
101                 lval[1] = Lval[rt][1];
102             }
103 
104             if(Rlen[rt]==r-l+1 && Rval[rt][0]>rval[1])
105             {
106                 rlen = Rlen[rt] + rlen;
107                 rval[1] = Rval[rt][1];
108             }
109             else
110             {
111                 rlen = Rlen[rt];
112                 rval[0] = Rval[rt][0];
113                 rval[1] = Rval[rt][1];
114             }
115 
116        }
117         return;
118     }
119     int mid = (l+r)>>1;
120     if(L<=mid)
121         query(l,mid,rt<<1,L,R);
122     if(R>mid)
123         query(mid+1,r,rt<<1|1,L,R);
124 }
125 int main()
126 {
127     int t,n,m;
128     char ch[3];
129     int A,B;
130     scanf("%d",&t);
131     while(t--)
132     {
133         scanf("%d%d",&n,&m);
134         for(int i=1;i<=n;++i)
135             scanf("%d",&a[i]);
136         build(1,n,1);
137         while(m--)
138         {
139             scanf("%s%d%d",ch,&A,&B);
140             if(ch[0]=='U')
141             {
142                 a[A+1] = B;
143                 update(1,n,1,A+1);
144             }
145             else
146             {
147                 f = true;
148                 llen = rlen = mlen = 0;
149                 lval[0] = lval[1] = rval[0] = rval[1] = 0;
150                 query(1,n,1,A+1,B+1);
151                 printf("%d
",max(max(llen,rlen),mlen));
152             }
153         }
154     }
155     return 0;
156 }

View Code

同理，最大连续子序列和，和上面的思路差不多

更难一点的题目就是把上述的两个问题放到树上，那么就要用到树链剖分。