codeforces 777E-Hanoi Factory 排序+树状数组+dp

题意：有n个圆环，每个圆环有一个外直径b、一个内直径a和一个高度h。一个圆环能放在另外一个圆环上面有两个条件，一是上面圆环的外直径b1小于等于下面圆环的外直径b2，二是上面圆环的外直径b1大于下面圆环的内直径a2。现在让你选出其中的一些圆盘，使得他们能叠的最高。

思路：这个题真的不太好想。最开始想到的思路是排序加二分，但是不管怎么想都不能保证其序列能从“能放的环”到”不能放的环”，所以也就不具有有序性，不能二分。（然而网上有人想出了纯排序的方法……b从小到大，a也从小到大，b为第一关键词，然后模拟就行……orz）但是我们可以把两个条件割裂开来。将所有环的内圈直径a从小到大排序然后离散化到树状数组（线段树）上，然后将环根据外直径从大到小，内直径从大到小（注意内直径也是从大到小，因为相同外直径肯定可以互相放，将内直径最小的在最后放是最优的情况）将所有环排序。对于每个环，因为已经遍历过的环外直径都大于等于当前环，所以只要考虑内环就行了，在离散化后的树状数组中找到当前环外直径刚刚好大于等于的位置，那么这之前的都是能放的，找一个最大的加上去然后更新当前点就行。其实就是线段树维护的lis。

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
76
77
78
79
80
81
82
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
	long long x,y;
	long long h;
}a[100005];
long long tree[100005]; 
int n,cnt;
int lowbit(int x)
{
	return x&-x;
}
void update(int x,long long val)
{
	for(int i=x;i<=cnt;i+=lowbit(i))
	{
		tree[i]=max(tree[i],val);
	}
}
long long getsum(int x)
{
	long long rt=0;
	for(int i=x;i>=1;i-=lowbit(i))
	{
		rt=max(rt,tree[i]);
	}
	return rt;
}
int cmp(node a,node b)
{
	if(a.y==b.y)return a.x>b.x;
	 else return a.y>b.y; 
}
long long q[100005];
long long qq[100005];
int main()
{
	memset(tree,0,sizeof(tree));
  	scanf("%d",&n);
  	for(int i=1;i<=n;i++)
  	{
  		scanf("%I64d%I64d%I64d",&a[i].x,&a[i].y,&a[i].h);
  		q[i]=a[i].x;
	  }
	sort(q+1,q+1+n);
   cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(q[i]!=q[i-1])qq[++cnt]=q[i];
	}
	//if(n==100000)printf("%d\n",cnt);
	sort(a+1,a+1+n,cmp);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		a[i].x=lower_bound(qq+1,qq+1+cnt,a[i].x)-qq;
	    a[i].y=lower_bound(qq+1,qq+1+cnt,a[i].y)-qq;
	}
    for(int i=1;i<=n;i++)
	{
		//if(n==100000)printf("i:%d\n",i);
		//a[i].x=lower_bound(qq+1,qq+1+cnt,a[i].x)-qq;
		long long temp=0;
		int pos=a[i].y-1;//=lower_bound(qq+1,qq+1+cnt,a[i].y)-qq-1;
		if(pos<=0)temp=a[i].h;
		   else temp=getsum(pos)+a[i].h;
		if(ans<temp)ans=temp;   
		update(a[i].x,temp);
	}
	//long long ans=getsum(cnt);
	printf("%I64d\n",ans);
	return 0;	  
 }