HeinzHuang

Eudaimonia

0%

俄罗斯套娃（JOISC 2016 Day 1）

Posted on Edited on In

俄罗斯套娃（JOISC 2016 Day 1）

题目描述

你开了一家卖俄罗斯套娃的店。因此，你向厂家订购了 \(N\)个俄罗斯套娃，这些娃娃被编号为 \(1\) 到 \(N\)，其中第 \(i\) 个套娃是一个的直径为 \(R_i\) 高度为 \(H_i\) 的直♂柱体 。每个俄罗斯套娃都只能套高和直径严格比他小的套娃。同时只要满足条件，俄罗斯套娃可以嵌套多次。

有一天，你收到了厂家的来电，告诉你你预定的 \(N\) 个娃娃不能一次性全部做完。所以第一批只会送达直径大于等于 \(A\) 并且高度小于等于 \(B\) 的所有套娃。你需要预先安排出一个方案，使送来的套娃经过若干次嵌套后，没有被套的套娃数量最小。

由于厂家经常搞大新闻，所以他会改变 \(A\) 和 \(B\) 的值，总共 \(Q\) 次，因此你需要对每对 \((A,B)\) 都作出回答，询问之间互不干扰。 ## 输入

第一行有两个整数 \(N\)和 \(Q\) ，表示套娃的个数和 \((A,B)\) 的对数； 之后的 \(N\) 行，每行两个数 \(R_i\) 与 \(H_i\) 表示第$ i$ 个数的直径和高度； 之后的 \(Q\) 行，每行两个数 \(A_i\) 与 \(B_i\) 表示第 \(i\) 个询问， \(A_i\) 与 \(B_i\) 的意思如上所示。

输出

一个整数，表示符合条件的方案个数。

思路

重要结论

这题每个套娃都是二维的，于是可以用\(xy​\)坐标轴表示所有的套娃，任意一个点只要在另一个点的右上方就可以把那点（娃娃）装进去

（横坐标为R,纵坐标为H）

这题根据人类的智慧可以得到

（直接）甩结论：最少的没被套的娃娃个数=最长的\(R\)递增，\(H\)递减的序列长度

这个可以感性理解一下，所有不在该序列上的点都必定会在一个点的右上方，所以就相当于所有多出来的点都是可以被装进另一个点中的。

离线+离散

知道这个后就去考虑每个询问，对于每个询问，若逐个计算每次的答案，用一个树状数组其中一维，显然要将一维进行离散。那么剩下的一位直接考虑进行离线处理，那么复杂度就被用优化成\(O((n+q)log_(n+q))\),可以开两个数组分别表示娃娃和询问，不过放一个数组里面一起排序会简单一些，不过注意在遇到询问和娃娃的两个值完全相同时，一定要先更新娃娃在回答询问（当时就被这个卡了。。。）

代码

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
#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l),END=(r);i<=END;i++)
#define DOR(i,r,l) for(int i=(r),END=(l);i>=END;i--)
#define loop(i,n) for(int i=0,END=(n);i<END;i++)
#define sf scanf
#define pf printf
#define pb push_back
#define pii pair<int,int>
#define R first
#define H second
#define mms(a,x) memset(a,x,sizeof a)
using namespace std;
typedef long long ll;
typedef long double db;
template<typename A,typename B>inline void chkmax(A &x,const B y){if(x<y)x=y;}
template<typename A,typename B>inline void chkmin(A &x,const B y){if(x>y)x=y;}
const int N=2e5+5;
int n,q;
pii doll[N];
struct Pt2{
	struct node{
		int x,y,id;
		bool operator<(const node &A)const{
			if(x!=A.x)return x>A.x;
			if(y!=A.y)return y<A.y;
			return id<A.id;
		}
	}A[N<<1];
	int b[N<<1],ans[N],ct;
	struct Binary_Indexed_Tree{
		#define lowbit(x) (x&-(x))
		static const int M=4e5;
		int c[N<<1];
		void update(int x,int val){while(x<=M)chkmax(c[x],val),x+=lowbit(x);}
		int query(int x){int ret=0;while(x)chkmax(ret,c[x]),x-=lowbit(x);return ret;}
	}BIT;
	void solve(){
		FOR(i,1,n)b[++ct]=doll[i].H,A[i]=(node){doll[i].R,doll[i].H,0};;
		FOR(i,1,q){
			sf("%d%d",&A[n+i].x,&A[n+i].y);
			A[n+i].id=i,b[++ct]=A[n+i].y;
		}
		sort(b+1,b+ct+1);
		ct=unique(b+1,b+ct+1)-b-1;
		sort(A+1,A+n+q+1);
		FOR(i,1,n+q)A[i].y=lower_bound(b+1,b+ct+1,A[i].y)-b;
		FOR(i,1,n+q){
			if(A[i].id)ans[A[i].id]=BIT.query(A[i].y);
			else {
				int nw=BIT.query(A[i].y);
				BIT.update(A[i].y,nw+1);
			}
		}
		FOR(i,1,q)pf("%d\n",ans[i]);
	}
}Pt_2;