BZOJ 2957 楼房重建

发表于 | 更新于

Link

Solution

可以看出，一个点对于它左边的区间的答案是不会产生影响的，而对右边的区间的影响是遮住了所有与原点连线的斜率比它小的。 于是脑中模模糊糊地浮现出一棵线段树，那棵树上的每个节点长着一棵Treap。 插入一个新节点，把它右边的区间中比它左边区间中斜率最大值大，而又比新插入的点斜率值小的点从右区间的答案中删去。 删除一个节点，把它右边区间中比它的斜率小但比它左边区间中最大值大的点加入答案。 ↑\uparrow口胡做法不一定对

最后发现，正解的做法非常巧妙。 大致思路差不多，但在更新答案的时候只需要在线段树上走即可。 首先，把新值赋到线段树的对应节点上。回溯的时候考虑已经知道了左半区间和右半区间的答案，如何得到整个区间的答案。思路就是，左半区间的答案不会改变，可以直接累加，而右半区间需要把比左半区间最大值小的点删掉。 对于右半区间[mid,r][mid,r]递归处理，设左半区间的最大值为msms。 假如[mid,r][mid,r]左半区间的最大值 <ms< ms，那左半区间就别想了，只需要统计右半区间有多少>ms> ms的点。 ==ms==ms，那左半区间就别想了，直接返回右半区间的答案对答案的贡献，即pos->cnt-pos->son[0]->cnt >ms> ms，那就不会影响右半区间的答案，只需要统计左半区间有多少>ms> ms的点，加上右半区间的答案即可。 很神奇的思路。每次操作只会走一条到叶节点的路径。单点的修改，把所有的路径长度累加，是1+2+...+logn1+2+...+\log n，也就是logn(1+logn)2\dfrac {\log n(1+\log n)}2，即总O(log2n)O(\log^2 n) 再加上线段树本来的复杂度，总O(nlog2n)O(n\log^2 n)，常数很小，跑得很快。

Tips

依旧是分析问题性质是最重要的，通过左右区间的影响关系的彻底分析，才得出这种很好写跑得快的方法。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+10;
typedef long double ld;
using std::max;
namespace iSeg
{
	const int SIZE=MAXN<<2;
	struct Node
	{
		Node *son[2];
		ld ms;int cnt;
		void up();
		bool isleaf();
		Node(){son[0]=son[1]=0;ms=cnt=0;}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root=null;
	Node *newNode(ld slope=0)
	{
		static Node* cur;cur=ME++;
		cur->son[0]=cur->son[1]=null;cur->ms=slope;
		return cur;
	}
	bool Node::isleaf(){return son[0]==son[1] && son[0]==null;}
	int Count(Node *pos,ld s)
	{
		if(pos==null) return 0;
		if(pos->isleaf()) return pos->ms>s;
		if(pos->son[0]->ms<s) return Count(pos->son[1],s); 
		else if(pos->son[0]->ms==s) return pos->cnt-pos->son[0]->cnt;
		else return pos->cnt-pos->son[0]->cnt+Count(pos->son[0],s);
	}
	void Node::up()
	{
		ms=max(son[0]->ms,son[1]->ms);
		cnt=son[0]->cnt+Count(son[1],son[0]->ms);
	}
	void Edit(Node *&pos,int L,int R,int goal,ld s)
	{
		if(pos==null) pos=newNode();
		if(L==R) pos->ms=s,pos->cnt=1;
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Edit(pos->son[0],L,MID,goal,s);
			else Edit(pos->son[1],MID+1,R,goal,s);
			pos->up();
		}
	}
}using namespace iSeg;
int main()
{
	int n,m;get(n),get(m);
	for(int i=1;i<=m;i++)
	{
		int x,y;get(x),get(y);
		Edit(root,1,n,x,(ld)y/x);
		printf("%d\n",root->cnt);
	}
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */