cf1132G 线段树解分区间LIS（一种全新的线段树解LIS思路）+单调栈

/* 给定n个数的数列，要求枚举长为k的区间，求出每个区间的最长上升子序列长度 首先考虑给定n个数的数列的LIS求法：从左往右枚举第i点作为最大点的贡献， 那么往左找到第一个比a[i]大的数，设这个数下标l，那么[l+1,i-1]的后继显然是i 那么[l+1,i-1]区间，和包括第i个数的LIS都可以+1，处理完所有点后求[1,n]区间的最大值即可 区间更新显然用线段树解决，线段树叶子结点维护第i个位置被加次数，即以第i个结点为起点的LIS长度 本题是枚举长为k的区间，求每个区间的LIS，那么只要在更新时查询区间[i-k+1,i]的最大值即可 要先预处理出第一个比a[i]大的a[i]左边的数的下标 : 单调栈 */ #include<bits/stdc++.h> #include<stack> using namespace std; #define maxn 1200006 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int n,k,a[maxn],l[maxn]; int Max[maxn<<2],lazy[maxn<<2]; inline void pushup(int rt){ Max[rt]=max(Max[rt<<1],Max[rt<<1|1]); } inline void pushdown(int rt){ if(lazy[rt]){ lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; Max[rt<<1]+=lazy[rt]; Max[rt<<1|1]+=lazy[rt]; lazy[rt]=0; } } void update(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ lazy[rt]++;Max[rt]++; return; } pushdown(rt); int m=l+r>>1; if(L<=m)update(L,R,lson); if(R>m)update(L,R,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r)return Max[rt]; pushdown(rt); int m=l+r>>1,res=0; if(L<=m)res=max(res,query(L,R,lson)); if(R>m)res=max(res,query(L,R,rson)); return res; } stack<int>stk; int main(){ cin>>n>>k; for(int i=1;i<=n;i++)scanf("%d",&a[i]); a[0]=0x3f3f3f3f; stk.push(0); for(int i=1;i<=n;i++){ while(a[i]>a[stk.top()]) stk.pop(); l[i]=stk.top(); stk.push(i); } /* for(int i=1;i<=n;i++) cout<<l[i]<<" ";*/ for(int i=1;i<=n;i++){ update(l[i]+1,i,1,n,1); if(i-k+1>=1) cout<<query(i-k+1,i,1,n,1)<<" "; } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10486318.html

相关资源：各显卡算力对照表！