正解:单调栈+线段树
解题报告:
首先考虑不修改的话就是个单调栈板子题昂,这个就是
然后这题的话,,,我怎么记得之前考试好像有次考到了类似的题目昂,,,?反正我总觉着这方法似曾相识的样子,,,想不起来辣,慢慢落实之前考题的时候再说趴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=+;
const lf eps=1e-;
ll n,m;
struct tr{lf mx;ll lth;}tree[N<<]; il ll read()
{
rg char ch=gc;rg ll x=;rg bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),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 ;if(nw_l==nw_r)return ;ll mid=(nw_l+nw_r)>>;
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+,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=;return;}
ll mid=(nw_l+nw_r)>>;
if(mid>=to)modify(ls(nw),nw_l,mid,to,hei);else modify(rs(nw),mid+,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+,nw_r,tree[ls(nw)].mx);
} int main()
{
// freopen("lfcj.in","r",stdin);freopen("lfcj.out","w",stdout);
n=read();m=read();rp(i,,m){ll x=read(),y=read();modify(,,n,x,y);printf("%lld\n",tree[].lth);}
return ;
}
放下代码QwQ