楼房重建
先搞清楚题目要求的是什么。令 \(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]\) 的答案。
update on 2023.4.9
有人告诉我原来这个就是兔队线段树，get新知识了
点击查看代码
#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;
}
[FJOI2016]神秘数
先忽略其它条件，考虑一个集合 \(s\) 怎么做。若 \(x\) 为当前可以得到的最大值，往 \(s\) 中加入一个数 \(y\)，当且仅当 \(y\le x\) 时，\(x\) 会变大。
题目就转化为：
- 将 \(ans\) 赋为 \(1\)。
- 求出区间内值在 \(1-ans\) 内所有数的和 \(res\)。
- 将 \(ans\) 赋为 \(res+1\)
- 重复操作 \(2,3\)。
模拟可知最劣情况增量是一个斐波那契数列，最多操作次数在 \(log\) 级别。
用可持久化线段树维护即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#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=1e5+10,Lg=31,inf=1e9;
int n,q,cnt,rt[N];
namespace Seg_Tree{
struct node{
int ch[2],val;
}tr[N*Lg];
#define ls(p) tr[p].ch[0]
#define rs(p) tr[p].ch[1]
void update(int &p,int pre,int l,int r,int pos,int val){
p=++cnt;
tr[p]=tr[pre];
tr[p].val+=val;
if(l==r){
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
update(ls(p),ls(pre),l,mid,pos,val);
}
else{
update(rs(p),rs(pre),mid+1,r,pos,val);
}
}
int query(int a,int b,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return tr[a].val-tr[b].val;
}
int mid=(l+r)>>1;
int res=0;
if(q_l<=mid){
res+=query(ls(a),ls(b),l,mid,q_l,q_r);
}
if(q_r>mid){
res+=query(rs(a),rs(b),mid+1,r,q_l,q_r);
}
return res;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int n;
read(n);
for(int i=1;i<=n;i++){
int x;
read(x);
Seg_Tree::update(rt[i],rt[i-1],1,inf,x,x);
}
read(q);
while(q--){
int l,r;
read(l),read(r);
int ans=1;
while(1){
int res=Seg_Tree::query(rt[r],rt[l-1],1,inf,1,ans);
if(res>=ans){
ans=res+1;
}
else{
break;
}
}
write_endl(ans);
}
return 0;
}
