bzoj 2957 楼房重建

Posted on | Views:

分块.

简单转化一下题意,就是求有多少个位置的斜率,在对应前缀中是严格最大的.

每一块维护 $len(x)$ 表示若第一个选中的是块内第 $x​$ 个元素,则该块内总共被选的个数.

为了找出块内是哪个元素被选中,还要对每一块维护前 $x​$ 个数中的最大值 $mx(x)​$ .

修改时将那一块重构一下,回答询问时从第一块开始跳,二分找出下一块中第一个选中的位置.

每跳一块,当前的数就会和块内的最大值取 $\max$ .

设块的大小为 $S$ ,则单次操作的时间复杂度为 $O(S+\frac{n}{S}\cdot\log_2 S)$ ,需要手动调下参数.

为了避免精度出现问题,可以把分子分母记下来,每次比较的时候比较两个分数.

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10,S=1024;
int n,m,B,bel[MAXN];
int lp[S],rp[S],cnt[S][S];
double k[MAXN],mx[S][S];
void ReBuild(int x)
{
	int tot=0;
	double cur=0;
	for(int i=lp[x];i<=rp[x];++i)
	{
		cnt[x][i-lp[x]+1]=tot;
		if(k[i]>cur)
			cur=k[i],++tot;
		mx[x][i-lp[x]+1]=cur;
	}
	for(int i=lp[x];i<=rp[x];++i)
		cnt[x][i-lp[x]+1]=tot-cnt[x][i-lp[x]+1];
}
int main()
{
	n=read(),m=read();
	B=1000;
	for(int i=1;i<=n;++i)
	{
		bel[i]=(i-1)/B+1;
		lp[bel[i]]=(bel[i]-1)*B+1;
		rp[bel[i]]=bel[i]*B;
	}	
	rp[bel[n]]=n;
	for(int t=1;t<=m;++t)
	{
		int x=read(),y=read();
		k[x]=(double)(y)/(double)(x);
		ReBuild(bel[x]);
		int ans=0;
		double tmp=0;
		for(int i=1;i<=bel[n];++i)
		{
			int pos=0,L=1,R=rp[i]-lp[i]+1;
			while(L<=R)
			{
				int mid=(L+R)>>1;
				if(mx[i][mid]>tmp)
					pos=mid,R=mid-1;
				else
					L=mid+1;
			}
			if(pos)
			{
				ans+=cnt[i][pos];
				tmp=mx[i][rp[i]-lp[i]+1];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}