[线段树最长上升序列] BZOJ 2957 楼房重建

2019-11-06 08:35:34

字体：大中小

来源：转载

供稿：网友

这个显然可以分块但实际上线段树是这个模型的经典解法考虑T[x] $T[x]$ 为仅考虑这个区间上升序列的长度那么T[x] $T[x]$ 肯定包含T[lsx] $T[ls_x]$ 关键是怎么接上rsx $rs_x$ 的那一部分关键在于这个函数 find(x,v) $find(x,v)$ 表示x $x$ 这个区间左边接一个v $v$ 上升序列的长度是多少

如果当前左儿子最大值M[lsx]<=v $M[ls_x]<=v$ 区间左儿子一定会被这个v完全挡住左儿子贡献一定是0 递归计算右儿子的贡献。如果当前左儿子最大值M[lsx]>v $M[ls_x]>v$ 那么左儿子至少贡献了最大值而右儿子接在左儿子后的贡献已经计算即T[x]−T[lsx] $T[x]-T[ls_x]$ 递归计算区间的左儿子

复杂度O(nlog2n) $O(n/log^2n)$

#include<cstdio>#include<cstdlib>#include<algorithm>#include<map>using namespace std;typedef pair<int,int> abcd;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;}const int N=100005;int T[N<<2]; double M[N<<2]; int l[N<<2],r[N<<2];inline void Build(int x,int _l,int _r){ l[x]=_l; r[x]=_r; T[x]=1; M[x]=0; if (l[x]==r[x]) return; int mid=(_l+_r)>>1; Build(x<<1,_l,mid); Build(x<<1|1,mid+1,_r);}inline int find(int x,double v){ if (l[x]==r[x]) return v<M[x]; if (M[x<<1]<v) return find(x<<1|1,v); else return find(x<<1,v)+T[x]-T[x<<1];}inline void update(int x){ M[x]=max(M[x<<1],M[x<<1|1]); T[x]=T[x<<1]+find(x<<1|1,M[x<<1]);}inline void modify(int x,int t,double a){ if (l[x]==r[x]) { T[x]=1; M[x]=a; return; } int mid=(l[x]+r[x])>>1; if (t<=mid) modify(x<<1,t,a); else modify(x<<1|1,t,a); update(x);}int n,m;int main(){ int Q,x,y; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(Q); Build(1,1,n); while (Q--){ read(x); read(y); modify(1,x,(double)y/x); PRintf("%d/n",find(1,0)); } return 0;}

上一篇：Ubuntu下安装arm-linux-gcc交叉编译链

下一篇：Andrew Ng Deep Learning Tutorial中Softmax分类器梯度求导过程