首页 > 代码库 > hdu5141 线段树
hdu5141 线段树
这题说的是给了一串然后计算出这个串的最长递增子序列的长度，然后计算出有过少个子串[i,j] 他们的最长递增子序列和这整个子串的最长递增子序列相同，我们对于每个j最长递增子序列找出他在序列中的使成为最长序列的起始点，如果这个样的点存在多个那么尽量的选取靠右的，这样我们将他们离散后，然后每个线段的叶节点保存这个点的最高排位数是多少和形成他最高排位的最右端点，然后用线段树去维护这个序列， 因为知道优先会让这个点取最高位在选左区间的，这样我们只要枚举每个上升序列长度为LIS的最小区间就好了
#include <cstdio>#include <string.h>#include <algorithm>#include <iostream>using namespace std;const int maxn = 100005;typedef long long ll;int cL, cR, cH, cloc, op;struct Itree{ int H[maxn*4],loc[maxn*4]; void build(int o, int L, int R){ memset(H,0,sizeof(H)); memset(loc,0,sizeof(loc)); } void query(int o, int L, int R){ if(cL<=L&&R<=cR){ if(op==0){ op=1; cH=H[o]; cloc=loc[o]; }else { if( H[o] > cH || ( H[o] == cH &&loc[o]>cloc)){ cH=H[o]; cloc=loc[o]; } } return ; } int mid=(L+R)>>1; if(cL<=mid) query(o*2,L,mid); if(cR>mid) query(o*2+1,mid+1,R);}void maintain(int o){ if(H[o*2]>H[o*2+1]||(H[o*2] == H[o*2+1] && loc[o*2] > loc[o*2+1] ) ){ H[o]=H[o*2]; loc[o]=loc[o*2]; }else{ H[o]=H[o*2+1] ; loc[o]=loc[o*2+1]; }}void update(int o , int L, int R){ if(L==R){ // if(cH>H[o]||(cH==H[o]&&cloc>loc[o])){ H[o]=cH;loc[o]=cloc; //} return ; } int mid = (L+R)>>1; if(op <= mid) update( o * 2 , L , mid ); else update( o * 2 + 1 , mid + 1 , R ); maintain(o); }}T;int H[maxn];int Loc[maxn];struct seg{ int L, R,d;}P[maxn];int main(){ int n; while(scanf("%d",&n)==1){ for(int i=0; i<n; ++i) { scanf("%d",&H[i]); Loc[i]=H[i]; } sort(Loc,Loc+n); int num=unique(Loc,Loc+n)-Loc; for( int i = 0 ; i < n; ++ i ) H[i] = lower_bound(Loc,Loc+num,H[i])-Loc+1; int ge=1; T.build(1,0,num); int g=0; for(int i=0; i<n; ++i){ op=0; cL=0; cR=H[i]-1; T.query(1,0,num); cH++; if( cH == 1 ){ cloc = i; } P[g].L=cloc; P[g].R=i;P[g].d=cH; g++; ge=max(ge,cH); op=H[i]; T.update(1,0,num); } ll ans=0,L=n; for(int i=g-1; i>=0; --i) if(P[i].d==ge){ ans += (P[i].L+1)*(L-P[i].R); L=P[i].R; } printf("%I64d\n",ans); } return 0;}
hdu5141 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。