楼房重建

Source and Judge

bzoj2957

Record

1h

Analysis

请先思考后再展开

一开始的想法:
求一个最顶上,斜率递增的面
然后分块维护,询问的时候,加入第i个块的时候前面不会被修改,后面就二分一下接在上面,复杂度为 $O(n\sqrt{n log})$
显然不能过……

正解:
vali=yi/xi,则求上升序列,这样就好做多了,我连这个都没转化
注意到修改只会修改一个位置,我们要尽量利用已有的信息去剪枝
考虑分治,设计一个函数solve(l,r,left)表示只考虑这段区间时候的答案,然后左边被left挡住
分类讨论一下,如果left挡住左区间的mx,则solve(mid+1,r,left)
否则,solve(l,mid,left)+solve(mid+1,r,lmx)
注意到右边那个,通过线段树是可以保存的(线段树减少区间个数为2n)
设cnt为只考虑本区间的答案,cnt2是上面说的那个东东,只用于右区间
根据等差数列公式,时间复杂度为 $O(nlog^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
const int MAX_N=110000;
struct SegmentTree
{
double mx[MAX_N*4];int cnt[MAX_N*4],cnt2[MAX_N*4];
#define lc 2*x
#define rc 2*x+1
void build(int x,int l,int r)
{
mx[x]=0;cnt[x]=1;cnt2[x]=1;
if(l==r) return;
int mid=(l+r)/2;
build(lc,l,mid);build(rc,mid+1,r);
}
int calc(int x,int l,int r,double left)
{
if(left>=mx[x]) return 0;
if(l==r) return mx[x]>left;
int mid=(l+r)>>1;
if(left>=mx[lc]) return calc(rc,mid+1,r,left);
return calc(lc,l,mid,left)+cnt2[rc];
}
void change(int x,int l,int r,int pos,double val)
{
if(l==r) {mx[x]=val;return;}
int mid=(l+r)>>1;
if(pos<=mid) change(lc,l,mid,pos,val);
else change(rc,mid+1,r,pos,val);
mx[x]=max(mx[lc],mx[rc]);
cnt2[rc]=calc(rc,mid+1,r,mx[lc]);
cnt[x]=cnt[lc]+cnt2[rc];
}
}sgt;
void main()
{
int n,m;scanf("%d%d",&n,&m);
sgt.build(1,1,n);
while(m--)
{
int x,y;scanf("%d%d",&x,&y);
sgt.change(1,1,n,x,(double)y/x);
printf("%d\n",sgt.calc(1,1,n,0));
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4690.html
转载请注明出处,谢谢!