G. Raffles
time limit per test：5 seconds
memory limit per test：256 megabytes
input：standard input
output：standard output
Johnny is at a carnival which has n raffles. Raffle i has a prize with value pi. Each participant can put tickets in whichever raffles they choose (they may have more than one ticket in a single raffle). At the end of the carnival, one ticket is selected at random from each raffle, and the owner of the ticket wins the associated prize. A single person can win multiple prizes from different raffles.
However, county rules prevent any one participant from owning more than half the tickets in a single raffle, i.e. putting more tickets in the raffle than all the other participants combined. To help combat this (and possibly win some prizes), the organizers started by placing a single ticket in each raffle, which they will never remove.
Johnny bought t tickets and is wondering where to place them. Currently, there are a total of li tickets in the i-th raffle. He watches as other participants place tickets and modify their decisions and, at every moment in time, wants to know how much he can possibly earn. Find the maximum possible expected value of Johnny's winnings at each moment if he distributes his tickets optimally. Johnny may redistribute all of his tickets arbitrarily between each update, but he may not place more than t tickets total or have more tickets in a single raffle than all other participants combined.
Input
The first line contains two integers n, t, and q (1 ≤ n, t, q ≤ 200 000) — the number of raffles, the number of tickets Johnny has, and the total number of updates, respectively.
The second line contains n space-separated integers pi (1 ≤ pi ≤ 1000) — the value of the i-th prize.
The third line contains n space-separated integers li (1 ≤ li ≤ 1000) — the number of tickets initially in the i-th raffle.
The last q lines contain the descriptions of the updates. Each description contains two integers tk, rk (1 ≤ tk ≤ 2, 1 ≤ rk ≤ n) — the type of the update and the raffle number. An update of type 1 represents another participant adding a ticket to raffle rk. An update of type 2 represents another participant removing a ticket from raffle rk.
It is guaranteed that, after each update, each raffle has at least 1 ticket (not including Johnny's) in it.
Output
Print q lines, each containing a single real number — the maximum expected value of Johnny's winnings after the k-th update. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if
.
Examples
2 1 3
4 5
1 2
1 1
1 2
2 1 1.666666667
1.333333333
2.000000000 3 20 5
6 8 10
6 6 6
1 1
1 2
1 3
2 3
2 3 12.000000000
12.000000000
11.769230769
12.000000000
12.000000000 Note
In the first case, Johnny only has one ticket to distribute. The prizes are worth 4 and 5, and the raffles initially have 1 and 2 tickets, respectively. After the first update, each raffle has 2 tickets, so Johnny has expected value
of winning by placing his ticket into the second raffle. The second update adds a ticket to the second raffle, so Johnny can win
in the first raffle. After the final update, Johnny keeps his ticket in the first raffle and wins
In the second case, Johnny has more tickets than he is allowed to spend. In particular, after the first update, there are 7, 6, and 6 tickets in each raffle, respectively, so Johnny can only put in 19 tickets, winning each prize with probability
. Also, note that after the last two updates, Johnny must remove a ticket from the last raffle in order to stay under
the tickets in the third raffle.
題目連結：http://codeforces.com/contest/626/problem/G
題意：
給n個獎池，t張彩票，q次操作。
每個獎池的獎金為pi。
每個獎池現有的彩票的數量為ai，保證ai>=1；
q次操作，每次有兩種，第i個獎池的現有彩票數量加一，或減一。
不允許投票的數量多于獎池數量的二分之一。
保證：
n,t,q<=2e5
ai<=1000 pi<=1000
求在采用最佳政策的前提下獲得獎金的期望。
思路：
首先要證明貪心的正确性，即把某張票投入某獎池之後其下一張票給期望做出的貢獻要小于上一張彩票...
把式子寫一下，求導，發現導數是單調遞減的...
然後是對于每次操作的處理。
一開始一直糾結如何處理從某獎池拿出的虧損。因為按照貢獻差來說第一個和後來的是有差別的，而且還要處理是否超票的問題。
但是看了卿學姐的思路...
其實思路是很簡潔的，大概的内容是維護一個虧損的線段樹一個盈利的線段樹，虧損的意思是從某一獎池拿出一張票我們期望的減少，盈利的意思是往某一獎池投入一張票期望的增加。其實獎池的投遞數量不用限制的，隻要把盈利控制為0就可以了。而對于減少某獎池現有彩票的數量，直接對上限和投遞數量的數組進行處理，然後更新維護這個獎池的盈利和虧損就可以了。因為虧損和盈利是可以直接根據這兩個資料确定的。
下面給出AC代碼：【卿學姐的代碼，參考一下，待補】
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 2e5+6;
4 inline int read()
5 {
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
9 return x*f;
10 }
11 int x[maxn],y[maxn],p[maxn];
12 struct treenode
13 {
14 int L , R ;
15 double Up,Down,Max,Min,ans;
16 void updata()
17 {
18 ans=1.0*p[L]*min(1.0*x[L]/(x[L]+y[L]),0.5);
19 if(x[L]>=y[L])Up=0;
20 else
21 {
22 Up=1.0*p[L]*(x[L]+1.0)/(x[L]+y[L]+1.0);
23 Up-=1.0*p[L]*x[L]/(x[L]+y[L]);
24 }
25 if(x[L])
26 {
27 if(x[L]>y[L])Down=0;
28 else
29 {
30 Down=1.0*p[L]*x[L]/(x[L]+y[L]);
31 Down-=1.0*p[L]*(x[L]-1.0)/(x[L]-1.0+y[L]);
32 }
33 }
34 else
35 Down=1e18;
36 }
37 };
38 treenode tree[maxn*4];
39 inline void push_up(int o)
40 {
41 tree[o].ans=tree[o<<1].ans+tree[o<<1|1].ans;
42 tree[o].Up=max(tree[o<<1].Up,tree[o<<1|1].Up);
43 tree[o].Down=min(tree[o<<1].Down,tree[o<<1|1].Down);
44 if(tree[o<<1].Up>tree[o<<1|1].Up)
45 tree[o].Max=tree[o<<1].Max;
46 else
47 tree[o].Max=tree[o<<1|1].Max;
48 if(tree[o<<1].Down<tree[o<<1|1].Down)
49 tree[o].Min=tree[o<<1].Min;
50 else
51 tree[o].Min=tree[o<<1|1].Min;
52 }
53
54 inline void build_tree(int L , int R , int o)
55 {
56 tree[o].L = L , tree[o].R = R, tree[o].ans=0;
57 if(L==R)
58 tree[o].Min=tree[o].Max=L,tree[o].updata();
59 if (R > L)
60 {
61 int mid = (L+R) >> 1;
62 build_tree(L,mid,o*2);
63 build_tree(mid+1,R,o*2+1);
64 push_up(o);
65 }
66 }
67
68 inline void updata(int QL,int o)
69 {
70 int L = tree[o].L , R = tree[o].R;
71 if (L==R)
72 {
73 tree[o].updata();
74 }
75 else
76 {
77 int mid = (L+R)>>1;
78 if (QL <= mid) updata(QL,o*2);
79 else updata(QL,o*2+1);
80 push_up(o);
81 }
82 }
83 int main()
84 {
85 int n,t,q,mx,mi;
86 scanf("%d%d%d",&n,&t,&q);
87 for(int i=1;i<=n;i++)
88 p[i]=read();
89 for(int i=1;i<=n;i++)
90 y[i]=read();
91 build_tree(1,n,1);
92 while(t--)mx=tree[1].Max,x[mx]++,updata(mx,1);
93 while(q--)
94 {
95 int type,r;type=read(),r=read();
96 if(type==1)y[r]++;else y[r]--;
97 updata(r,1);
98 while(1)
99 {
100 int mx = tree[1].Max;
101 int mi = tree[1].Min;
102 if(tree[1].Up<=tree[1].Down)break;
103 x[mx]++,x[mi]--;
104 updata(mx,1);
105 updata(mi,1);
106 }
107 printf("%.12f\n",tree[1].ans);
108 }
109 } 作 者：Angel_Kitty
出 處：https://www.cnblogs.com/ECJTUACM-873284962/
關于作者：阿裡雲ACE，目前主要研究方向是Web安全漏洞以及反序列化。如有問題或建議，請多多賜教！
版權聲明：本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連結。
特此聲明：所有評論和私信都會在第一時間回複。也歡迎園子的大大們指正錯誤，共同進步。或者直接私信我
聲援部落客：如果您覺得文章對您有幫助，可以點選文章右下角【推薦】一下。您的鼓勵是作者堅持原創和持續寫作的最大動力！
歡迎大家關注我的微信公衆号IT老實人(IThonest)，如果您覺得文章對您有很大的幫助，您可以考慮賞部落客一杯咖啡以資鼓勵，您的肯定将是我最大的動力。thx.
我的公衆号是IT老實人(IThonest)，一個有故事的公衆号，歡迎大家來這裡讨論，共同進步，不斷學習才能不斷進步。掃下面的二維碼或者收藏下面的二維碼關注吧(長按下面的二維碼圖檔、并選擇識别圖中的二維碼)，個人QQ和微信的二維碼也已給出，掃描下面👇的二維碼一起來讨論吧！！！
歡迎大家關注我的Github，一些文章的備份和平常做的一些項目會存放在這裡。