网站开发 组织架构,做网站可以用电脑当服务器吗,科技公司介绍,做英语手抄报 什么网站输入一串数字#xff0c;有两个操作#xff1a;Q a b 查询a到b区间内严格递增子串的最大长度 #xff1b; U a b 把第a位数字替换成b 。注意输入的编号是从0开始 解法#xff1a;线段树维护区间的严格递增子串的最大长度即可。注意细节。 #include iostream
#inclu…输入一串数字有两个操作Q a b 查询a到b区间内严格递增子串的最大长度 U a b 把第a位数字替换成b 。注意输入的编号是从0开始 解法线段树维护区间的严格递增子串的最大长度即可。注意细节。 #include iostream
#include algorithm
#include cstdio
#include cstringusing namespace std;
struct Tree{int l,r;int valuel,valuer,value;int ld,rd;}nod[1000202];
int n,m;
int w[1000020] ;void Pushup(int k)
{nod[k].valuel nod[k].valuer 1;if(nod[k1].rd nod[k1|1].ld){nod[k].valuemax(nod[k1].valuernod[k1|1].valuel,max(nod[k1].value,nod[k1|1].value));if(nod[k1].valuel nod[k1].r-nod[k1].l1 ){nod[k].valuelnod[k1].valuelnod[k1|1].valuel ;}if(nod[k1|1].valuer nod[k1|1].r-nod[k1|1].l1){nod[k].valuernod[k1|1].valuernod[k1].valuer;}nod[k].valuelmax(nod[k].valuel,nod[k1].valuel) ;nod[k].valuermax(nod[k].valuer,nod[k1|1].valuer) ;//coutnod[2].valuerendl;}else{nod[k].valuemax(nod[k1].value,nod[k1|1].value) ;nod[k].valuel nod[k1].valuel ;nod[k].valuer nod[k1|1].valuer ;}nod[k].ldnod[k1].ld , nod[k].rdnod[k1|1].rd ;
}void Build(int l,int r,int k)
{nod[k].ll,nod[k].rr , nod[k].ldw[nod[k].l] , nod[k].rdw[nod[k].r] ;if(nod[k].l nod[k].r){nod[k].value nod[k].valuel nod[k].valuer 1;return ;}int mid (lr)1 ;Build(l,mid,k1);Pushup(k) ;Build(mid1,r,k1|1);Pushup(k);
}int Query(int l,int r,int k)
{int ans 0;if(nod[k].ll nod[k].rr ){return nod[k].value ;}int mid(nod[k].l nod[k].r)1 ;if(rmid){return Query(l,r,k1) ;}else if(lmid){return Query(l,r,k1|1) ;}else{if(nod[k1].rd nod[k1|1].ld ){ans max(Query(l,mid,k1) , Query(mid1,r,k1|1)) ;int temp min(mid-l1,nod[k1].valuer)min(r-(mid1)1,nod[k1|1].valuel) ;ansmax(ans,temp);}else{ans max(Query(l,mid,k1),Query(mid1,r,k1|1)) ;}}return ans ;}void Update(int l,int k,int value)
{if(nod[k].lnod[k].r nod[k].l l){nod[k].ld nod[k].rd value ;w[nod[k].r]value ;nod[k].valuel nod[k].valuer nod[k].value 1 ;return ;}int mid(nod[k].l nod[k].r)1 ;if(lmid){Update(l,k1,value);}else{Update(l,k1|1,value) ;}Pushup(k);return ;}
int main()
{int t;scanf(%d,t) ;while(t--){scanf(%d%d,n,m) ;memset(w,0,sizeof w) ;for(int i1;in;i){scanf(%d,w[i]) ;}//getchar() ;
Build(1,n,1) ;/*for(int i1;i30;i){couti nod[i].value nod[i].valuel nod[i].valuerendl;}cout-------------------------------------endl;*/for(int i0;im;i){char c;int a,b;cinc;scanf(%d%d,a,b);//coutcendl;if(cQ){a,b;if(ab){swap(a,b) ;}int ans Query(a,b,1);//coutcendl;printf(%d\n,ans) ;}else{a;Update(a,1,b) ;/*for(int i1;i30;i){couti nod[i].value nod[i].valuel nod[i].valuerendl;}cout-------------------------------------endl;*/}}}return 0;
} 转载于:https://www.cnblogs.com/Scale-the-heights/p/4707336.html
