uestc 1425——Another LCIS

本文主要是介绍uestc 1425——Another LCIS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线段树

跟上次做的0 1 反转基本相同

http://acm.uestc.edu.cn/problem.php?pid=1425

注意：sample输出是没输出case数，害我wa了好多次。。。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((t[rt].l+t[rt].r)>>1)
#define maxn 100100
int n,m;
struct tree
{
int l,r;
int lval,rval;
int lmax,rmax,max;
int len,lazy;
tree(){}
tree(int a,int b,int c,int d):l(a),r(b),len(c),lazy(d){}
}t[maxn<<2];
void pushup(int rt)
{
t[rt].lval=t[ls].lval;
t[rt].rval=t[rs].rval;
if(t[ls].rval<t[rs].lval)
{
t[rt].lmax=(t[ls].len==t[ls].lmax?t[ls].lmax+t[rs].lmax:t[ls].lmax);
t[rt].rmax=(t[rs].len==t[rs].rmax?t[rs].rmax+t[ls].rmax:t[rs].rmax);
t[rt].max=max(max(t[ls].max,t[rs].max),t[ls].rmax+t[rs].lmax);
}
else
{
t[rt].lmax=t[ls].lmax;
t[rt].rmax=t[rs].rmax;
t[rt].max=max(t[ls].max,t[rs].max);
} 
}
void pushdown(int rt)
{
if(t[rt].lazy!=0)
{
int k=t[rt].lazy;
t[ls].rval+=k;t[ls].lval+=k;
t[rs].lval+=k;t[rs].rval+=k;
t[ls].lazy+=k;t[rs].lazy+=k;
t[rt].lazy=0;
}
}
void build(int rt,int l,int r)
{
t[rt]=tree(l,r,r-l+1,0);
if(l==r)
{
scanf("%d",&t[rt].lval);
t[rt].rval=t[rt].lval;
t[rt].lmax=t[rt].rmax=t[rt].max=1;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
int query(int rt,int l,int r)
{
if(l==t[rt].l&&r==t[rt].r)
return t[rt].max;
pushdown(rt);
if(r<=mid)
return query(ls,l,r);
else if(l>mid)
return query(rs,l,r);
else
{
int a=query(ls,l,mid);
int b=query(rs,mid+1,r);
int ans=max(a,b);
int k=0;
if(t[ls].rval<t[rs].lval)
k=min(mid-l+1,t[ls].rmax)+min(r-mid,t[rs].lmax);
return max(ans,k);
}
}
void add(int rt,int l,int r,int k)
{
if(t[rt].l==l&&t[rt].r==r)
{
t[rt].rval+=k;
t[rt].lval+=k;
t[rt].lazy+=k;
return;
}
pushdown(rt);
if(r<=mid)
add(ls,l,r,k);
else if(l>mid)
add(rs,l,r,k);
else
{
add(ls,l,mid,k);
add(rs,mid+1,r,k);
}
pushup(rt);
}
int main()
{
int t;
int cnt=0;
scanf("%d",&t);
while(t--)
{
printf("Case #%d:\n",++cnt);
scanf("%d%d",&n,&m);
build(1,1,n);
char s[10];
int l,r,val;
while(m--)
{
scanf("%s",s);
if(s[0]=='q')
{
scanf("%d%d",&l,&r);
int ans=query(1,l,r);
printf("%d\n",ans);
}
else
{
scanf("%d%d%d",&l,&r,&val);
add(1,l,r,val);
}
}
}
return 0;
}

 

这篇关于uestc 1425——Another LCIS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---