洛谷P4198 楼房重建 单调栈+线段树
正解:单调栈+线段树
解题报告:
首先考虑不修改的话就是个单调栈板子题昂,这个就是
然后这题的话,,,我怎么记得之前考试好像有次考到了类似的题目昂,,,?反正我总觉着这方法似曾相识的样子,,,想不起来辣,慢慢落实之前考题的时候再说趴QAQ
然后具体看到这道题的话,就是用个线段树,每个节点记录这个节点的最长序列和最大斜率
然后对于左右两个子节点合并
首先左节点直接保存下来就好
然后右节点,可以继续分半递归查找找到能合并的最左边节点
挺好理解的就是不太好表示,具体看代码算了QAQ
这样修改的复杂度就是log2n,然后查询的复杂度依然是logn
然后就欧克辣!
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define ll long long
#define lf long double
#define gc getchar()
#define rp(i,x,y) for(rg ll i=x;i<=y;++i)
const ll N=100000+10;
const lf eps=1e-18;
ll n,m;
struct tr{lf mx;ll lth;}tree[N<<2];
il ll read()
{
rg char ch=gc;rg ll x=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il ll query(ll nw,ll nw_l,ll nw_r,lf dat)
{
if(tree[nw].mx<=dat)return 0;if(nw_l==nw_r)return 1;ll mid=(nw_l+nw_r)>>1;
if(tree[ls(nw)].mx>=dat)return query(ls(nw),nw_l,mid,dat)+tree[nw].lth-tree[ls(nw)].lth;
return query(rs(nw),mid+1,nw_r,dat);
}
il void modify(ll nw,ll nw_l,ll nw_r,ll to,ll hei)
{
if(nw_l==nw_r){tree[nw].mx=(lf)hei/to,tree[nw].lth=1;return;}
ll mid=(nw_l+nw_r)>>1;
if(mid>=to)modify(ls(nw),nw_l,mid,to,hei);else modify(rs(nw),mid+1,nw_r,to,hei);
tree[nw].mx=max(tree[ls(nw)].mx,tree[rs(nw)].mx);tree[nw].lth=tree[ls(nw)].lth+query(rs(nw),mid+1,nw_r,tree[ls(nw)].mx);
}
int main()
{
// freopen("lfcj.in","r",stdin);freopen("lfcj.out","w",stdout);
n=read();m=read();rp(i,1,m){ll x=read(),y=read();modify(1,1,n,x,y);printf("%lld\n",tree[1].lth);}
return 0;
}