楼房重建
先搞清楚题目要求的是什么。令 \(k_0=0,k_i=\frac{h_i}{i}\)，则题目求的一个从 \(0\) 开始的单调上升序列的长度减一。
最暴力的做法就是直接维护上升的序列，修改后从修改处开始重新维护，但时间复杂度不对，考虑优化。
先忽略从 \(0\) 开始的限制条件。
令 \(mx_{\left[l,r\right]}\) 表示区间 \(\left[l,r\right]\) 内的最大值，对于区间 \(\left[l,k\right]\) 和 \(\left[k+1,r\right]\) 可以发现当 \(mx_{\left[l,k\right]}<mx_{\left[k+1,r\right]}\) 时，区间 \(\left[l,r\right]\) 的答案是区间 \(\left[l,k\right]\) 的答案合并而来的。对于不满足上述条件的区间，可以在 \(\left[k+1,r\right]\) 上找到第一个大于 \(mx_{\left[l,k\right]}\) 的数的位置 \(x\)，得到 \(\left[x,r\right]\) 的答案，区间 \(\left[l,r\right]\) 的答案也可以转移得到。既然可以区间合并，考虑线段树。
对于区间 \(\left[l,r\right]\)，若 \(l=r\)，则有值答案赋为 \(1\)，没值答案赋为 \(0\)。否则考虑两个区间最大值之间的关系，按照上述方法合并，只需要找到 \(x\) 就可以了。对于 \(\left[x,y\right]\)，因为所有子区间的答案都知道了，若左区间最大值大于要求的值，则右区间对 \(\left[x,y\right]\) 的答案的贡献可以直接计入，再往左区间递归寻找，否则往右区间递归寻找。每次修改之后重新维护答案即可，答案为区间 \(\left[1,n\right]\) 的答案。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define LD long double
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,q;
namespace Seg_Tree{
struct node{
int tot;
LD mx;
}tr[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
int query(int p,int l,int r,LD mx){
if(l==r){
return tr[p].mx>mx;
}
int mid=(l+r)>>1;
if(tr[ls(p)].mx<=mx){
return query(rs(p),mid+1,r,mx);
}
else{
return query(ls(p),l,mid,mx)+tr[p].tot-tr[ls(p)].tot;
}
}
void update(int p,int l,int r,int pos,LD val){
if(l==r){
tr[p].tot=1;
tr[p].mx=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
update(ls(p),l,mid,pos,val);
}
else{
update(rs(p),mid+1,r,pos,val);
}
tr[p].mx=max(tr[ls(p)].mx,tr[rs(p)].mx);
tr[p].tot=tr[ls(p)].tot+query(rs(p),mid+1,r,tr[ls(p)].mx);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(q);
while(q--){
int pos,h;
read(pos),read(h);
Seg_Tree::update(1,1,n,pos,1.0L*h/pos);
write_endl(Seg_Tree::tr[1].tot);
}
return 0;
}