zoj 3606 Lazy Salesgirl (线段树，单点更新，区间合并)
题意：有个小女孩卖火柴,有n个人会来买，分别在时间t[i]，以价格p[i]，买的火柴个数为1+(k-1)%3,其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴，小女孩就会睡着。小女孩睡着后如果有人来买火柴，那小女孩就会醒过来，但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。
思路： 显然，w应该是某2个顾客的来访时间只差（而不是什么任意值）.
因此我们可以通过枚举相邻访问时间的顾客的访问之间之差。
我们可以从小到大枚举w，这样就可以保证得到的最大营业额的对应w最小。
构造一颗线段树，维护4个域，cnt表示区间中，确实购买了火柴的顾客的人数，sum[i] (i属于0..2) 表示一个区间中最左边的顾客购买了i+1根火柴后，该区间的最大利润。
所以其实这道题类似hdu4288解题报告
维护sum[i]的时候，右一点绕，需要注意对于tree[rt].sum[i]，我们只是说该区间的最左边的人买了(i+1)根火柴，该区间的其他人买了几根火柴无所谓，我们只想知道该区间的利润。
wa了一次。。因为虽然我们分析出w一定是某2个连续的时间的差值，一定是整数值，但是为了迷惑人。。题目还是要以6位小数输出。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月26日 星期二 18时32分43秒
4File Name :3606.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int n;
36int total;
37struct node
38{
39 int p,t;
40 int id;
41 bool operator < (const node &b) const
42 {
43 return t<b.t;
44 }
45}a[N],b[N];
46
47struct Tree
48{
49 LL sum[3];//sum[i]表示当区间最左边的人买了i+1个面包时，该段区间的总销售额
50 int cnt;
51}tree[N<<2];
52
53void PushUp(int rt)
54{
55 tree[rt].cnt = tree[rt<<1].cnt + tree[rt<<1|1].cnt;
56 int len = tree[rt<<1].cnt;
57 for ( int i = 0 ; i < 3 ; i++)
58 {
59 tree[rt].sum[i] = tree[rt<<1].sum[i] + tree[rt<<1|1].sum[(i+len)%3];
60 //区间合并有点绕
61 //将区间rt<<1和rt<<1|1合并到rt的时候，需要注意，我们只规定了区间rt的最左端的人是买了i+1个面包。
62 //rt<<1|1区间的人买了几个面包无所谓，我们只要求这个销售额。
63 }
64
65}
66void update( int x,int l,int r,int rt)
67{
68 if (l==r)
69 {
70 for ( int i = 0 ; i < 3 ; i++) tree[rt].sum[i] = 1LL*(i+1)*a[x].p;//printf("i:%d x:%d a[x]:%d sum[i]:%lld \n",i,x,a[x].p,tree[rt].sum[i]);
71 tree[rt].cnt=1;
72 return;
73 }
74 int m = (l+r)>>1;
75 if (x<=m) update(x,lson);
76 else update(x,rson);
77 PushUp(rt);
78}
79int main()
80{
81 #ifndef ONLINE_JUDGE
82 freopen("./in.txt","r",stdin);
83 #endif
84 int T;
85 cin>>T;
86 while (T--)
87 {
88 total = 0 ;
89 ms(tree,0);
90 scanf("%d",&n);
91 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i].p);
92 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i].t);
93 sort(a+1,a+n+1);
94
95 a[0].t=0;
96 for ( int i = 1 ; i <= n ; i++)
97 {
98 b[i].t = a[i].t-a[i-1].t;
99 b[i].p = a[i].p;
100 b[i].id = i ;
101 }
102 sort(b+1,b+n+1);
103 /*
104 for ( int i = 1 ; i <= n ; i++)
105 {
106 printf("id:%d w:%d p:%d\n",b[i].id,b[i].t,b[i].p);
107 }
108 */
109
110 double mx = 0.0;
111 double ans_w;
112 for ( int i=1,j=1; i <= n ; i=j)
113 {
114 while (b[i].t==b[j].t&&j<=n) //一样的要一起处理，否则可能得到不合理的平均值。
115 {
116 total++;
117 update(b[j].id,1,n,1);
118 // cout<<tree[1].sum[0]<<endl;
119 j++;
120 }
121 double ave = tree[1].sum[0]*1.0/total;
122 //cout<<"total:"<<total<<endl;
123 if (ave>mx)
124 {
125 mx = ave;
126 ans_w = b[j-1].t;
127 }
128 }
129 printf("%.6f %.6f\n",ans_w,mx);
130 }
131
132 #ifndef ONLINE_JUDGE
133 fclose(stdin);
134 #endif
135 return 0;
136}