[TJOI2013]最长上升子序列
题目大意：
给定一个序列，初始为空。将\(1\sim n(n\le10^5)\)的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字后输出LIS长度。
思路：
首先用线段树（或rope）求出最终状态的序列，然后就变成了普通的LIS问题。
源代码：
线段树：
#include#include #include inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x;}const int N=1e5+1;int n,p[N];class SegmentTree { #define _left <<1 #define _right <<1|1 #define mid ((b+e)>>1) private: int val[N<<2]; void push_up(const int &p) { val[p]=val[p _left]+val[p _right]; } public: int find(const int &p,const int &b,const int &e,const int &x) { if(b==e) return x==b-val[p]?b:0; if(mid-val[p _left]<=x) { const int ret=find(p _right,mid+1,e,x+val[p _left]); if(ret) return ret; } return find(p _left,b,mid,x); } void add(const int &p,const int &b,const int &e,const int &x) { val[p]++; if(b==e) return; if(x<=mid) add(p _left,b,mid,x); if(x>mid) add(p _right,mid+1,e,x); push_up(p); } #undef _left #undef _right #undef mid};SegmentTree sgt;class FenwickTree { private: int val[N]; int lowbit(const int &x) const { return x&-x; } public: void modify(int p,const int &x) { for(;p<=n;p+=lowbit(p)) { val[p]=std::max(val[p],x); } } int query(int p) const { int ret=0; for(;p;p-=lowbit(p)) { ret=std::max(ret,val[p]); } return ret; }};FenwickTree bit;int main() { n=getint(); for(register int i=1;i<=n;i++) { p[i]=getint(); } for(register int i=n;i>=1;i--) { p[i]=sgt.find(1,1,n,p[i])+1; sgt.add(1,1,n,p[i]); } int ans=0; for(register int i=1;i<=n;i++) { const int tmp=bit.query(p[i])+1; bit.modify(p[i],tmp); ans=std::max(ans,tmp); printf("%d\n",ans); } return 0;}
rope：
#include#include #include inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x;}const int N=1e5+1;int n,ans[N];__gnu_cxx::rope s;class FenwickTree { private: int val[N]; int lowbit(const int &x) const { return x&-x; } public: void modify(int p,const int &x) { for(;p<=n;p+=lowbit(p)) { val[p]=std::max(val[p],x); } } int query(int p) const { int ret=0; for(;p;p-=lowbit(p)) { ret=std::max(ret,val[p]); } return ret; }};FenwickTree bit;int main() { n=getint(); for(register int i=1;i<=n;i++) { s.insert(getint(),i); } for(register int i=0;i