UESTC 1425 求任意区间的LIS 线段树区间更新区间查询
Description#include <stdio.h>#include <string.h>#include <iostream>#include <math.h>#include <queue>#define N 201000#define M 2000100#define inf64 0x7ffffff#define inf 0x7ffffff#define ll int#define LL(x) (x<<1)#define RR(x) (x<<1|1)#define MID(x,y) (x+y)>>1using namespace std;inline ll Min(ll a,ll b){return a>b?b:a;}inline ll Max(ll a,ll b){return a>b?a:b;}struct node { int lft,rht; int lmx,rmx,mx; int lval,rval,add; void fun(int tmp) { add+=tmp; lval+=tmp; rval+=tmp; } int len(){return rht-lft+1;} int mid(){return MID(lft,rht);} void init(){ lmx=rmx=mx=add=0; } }; int y[N],n,m; struct Segtree { node tree[N*4]; void down(int ind) //向下更新,lazy,{ if(tree[ind].add) { tree[LL(ind)].fun(tree[ind].add); tree[RR(ind)].fun(tree[ind].add); tree[ind].add=0; } } void up(int ind) //向上更新{ tree[ind].lmx=tree[LL(ind)].lmx; tree[ind].rmx=tree[RR(ind)].rmx; tree[ind].lval=tree[LL(ind)].lval; tree[ind].rval=tree[RR(ind)].rval; tree[ind].mx=max(tree[LL(ind)].mx,tree[RR(ind)].mx); if(tree[LL(ind)].rval<tree[RR(ind)].lval) { if(tree[LL(ind)].lmx==tree[LL(ind)].len()) tree[ind].lmx+=tree[RR(ind)].lmx; if(tree[RR(ind)].rmx==tree[RR(ind)].len()) tree[ind].rmx+=tree[LL(ind)].rmx; tree[ind].mx=max(tree[ind].mx,tree[LL(ind)].rmx+tree[RR(ind)].lmx); } tree[ind].mx=max(tree[ind].mx,max(tree[ind].lmx,tree[ind].rmx)); } void build(int lft,int rht,int ind) { tree[ind].lft=lft; tree[ind].rht=rht; tree[ind].init(); if(lft==rht) { tree[ind].lval=tree[ind].rval= y[lft]; //把y数组更新进来 tree[ind].lmx=tree[ind].rmx=tree[ind].mx=1; } else { int mid=tree[ind].mid(); build(lft,mid,LL(ind)); build(mid+1,rht,RR(ind)); up(ind); } } void updata(int st,int ed,int ind,int valu) //区间更新{ int lft=tree[ind].lft,rht=tree[ind].rht; if(st<=lft&&rht<=ed) tree[ind].fun(valu); else { down(ind); int mid=tree[ind].mid(); if(st<=mid) updata(st,ed,LL(ind),valu); if(ed> mid) updata(st,ed,RR(ind),valu); up(ind); } } int query(int st,int ed,int ind) //区间询问{ int lft=tree[ind].lft,rht=tree[ind].rht; if(st<=lft&&rht<=ed) return tree[ind].mx; else { down(ind); int mid=tree[ind].mid(); if(ed<=mid) return query(st,ed,LL(ind)); else if(st>mid) return query(st,ed,RR(ind)); else { int mid=tree[ind].mid(); int mx1=query(st,ed,LL(ind)); int mx2=query(st,ed,RR(ind)); int tmp1=0,tmp2=0; if(tree[LL(ind)].rval<tree[RR(ind)].lval) { tmp1=min(mid-st+1,tree[LL(ind)].rmx); tmp2=min(ed-mid,tree[RR(ind)].lmx); } return max(max(mx1,mx2),tmp1+tmp2); } } } }seg; //---------------线段树区间lazy更新，区间查询，LIS模版 ---------------int main(){int n,a,b,i,T,Cas=1,que;char c;scanf("%d",&T);while(T--){scanf("%d %d",&n,&que);for(i=1;i<=n;i++)scanf("%d",&y[i]);seg.build( 1, n, 1);printf("Case #%d:\n",Cas++);while(que--){c=getchar();while(c!='a' && c!='q')c=getchar();scanf("%d %d",&a,&b);if(c=='q')printf("%d\n",seg.query(a,b,1));else {scanf("%d",&i);seg.updata(a,b,1,i);}}}return 0;}
