HDU 3308 最长上升连续子序列 （线段树）
[cpp] view plaincopy
题意不用说了，此题是传说中的 “傻仔哥” 出的，虽然不知教主真名，但是还是看着他的线段树长大的....
Code：
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define manx 100050
using namespace std;
int root[manx<<2],lm[manx<<2],rm[manx<<2],a[manx];
void up(int l,int r,int rt){
lm[rt] = lm[rt<<1];
rm[rt] = rm[rt<<1|1];
root[rt] = max(root[rt<<1],root[rt<<1|1]);
int mid = (l+r)>>1;
if(a[mid+1]>a[mid]){
if(lm[rt<<1] == mid-l+1) lm[rt] += lm[rt<<1|1];
if(rm[rt<<1|1] == r-mid) rm[rt] += rm[rt<<1];
root[rt] = max(root[rt],lm[rt<<1|1]+rm[rt<<1]);
}
}
void make(int l,int r,int rt){
if(l==r){
lm[rt] = rm[rt] = root[rt] = 1;
return ;
}
int mid = (l+r)>>1;
make(lson);
make(rson);
up(l,r,rt);
// cout<<l<<" "<<r<<" "<<rt<<" "<<root[rt]<<endl;
}
int query(int l,int r,int rt,int ll,int rr){
if(ll<=l && rr>=r){
return root[rt];
}
int mid=(l+r)>>1;
if(rr<=mid) return query(lson,ll,rr);
else if(ll>mid) return query(rson,ll,rr);
else {
int t1 = query(lson,ll,mid);
int t2 = query(rson,mid+1,rr);
int t = max(t1,t2);
if(a[mid] < a[mid+1]){
t1 = min(rm[rt<<1],mid-ll+1); //// 防止越界的情况发生
t2 = min(lm[rt<<1|1],rr-mid);
t1 += t2;
}
return max(t,t1);
}
}
void update(int l,int r,int rt,int p,int q){
if(l==r && r==p){
a[l] = q;
return ;
}
int mid = (l+r)>>1;
if(p<=mid) update(lson,p,q);
else update(rson,p,q);
up(l,r,rt);
}
int main(){
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
make(1,n,1);
int p,q;
char ch[5];
for(int i=1;i<=m;i++){
scanf("%s%d%d",ch,&p,&q);
if(ch[0]=='Q'){
p++,q++;
int flag = query(1,n,1,p,q);
printf("%d\n",flag);
}
if(ch[0]=='U'){
p++;
update(1,n,1,p,q);
}
}
}
}
补充：软件开发 , C++ ,
