fork(1) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. mt19937 mrand(random_device{}());
  15. const ll mod=1000000007;
  16. int rnd(int x) { return mrand() % x;}
  17. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  18. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  19. // head
  20.  
  21.  
  22. const int N=101000;
  23. typedef double db;
  24.  
  25. db dp[N],ldp[N];
  26. int p1[N],p2[N];
  27. int sp[N],lsp[N],n;
  28.  
  29. db calc(int x,int y) {
  30. db val=dp[x]+dp[y]+min(x,y)+x+y;
  31. db bp=0;
  32. db pr=1;
  33. rep(i,1,x+1) {
  34. pr=pr*(x+1-i)/(x+y+1-i);
  35. bp+=pr;
  36. if (pr<1e-10) break;
  37. }
  38. pr=1;
  39. rep(i,1,y+1) {
  40. pr=pr*(y+1-i)/(x+y+1-i);
  41. bp+=pr;
  42. if (pr<1e-10) break;
  43. }
  44. val-=bp;
  45. // printf("%.10f\n",bp);
  46. return val;
  47. }
  48.  
  49. db lcalc(int x,int y) {
  50. db val=ldp[x]+dp[y]+min(x,y)+x+y-p1[x];
  51. db bp=0;
  52. db pr=1;
  53. rep(i,1,x+1) {
  54. pr=pr*(x+1-i)/(x+y+1-i);
  55. bp+=pr;
  56. if (pr<1e-10) break;
  57. }
  58. pr=1;
  59. rep(i,1,y+1) {
  60. pr=pr*(y+1-i)/(x+y+1-i);
  61. bp+=pr;
  62. if (pr<1e-10) break;
  63. }
  64. val-=bp;
  65. // printf("%d %d %d\n",x,y,p1[x]);
  66. return val;
  67. }
  68.  
  69. int pans=0;
  70. int cnt[N],perm[N],ins[N],rd[N];
  71. int totQ;
  72.  
  73. int Query(int u) {
  74. ++totQ;
  75. if (ins[u]) {
  76. cnt[perm[u]]--;
  77. if (cnt[perm[u]]==0) pans--;
  78. } else {
  79. cnt[perm[u]]++;
  80. if (cnt[perm[u]]==1) pans++;
  81. }
  82. ins[u]^=1;
  83. return pans;
  84. }
  85.  
  86. int pre,pins[N];
  87. VI x,y;
  88.  
  89. struct RNG {
  90. int operator() (int n) {
  91. return rnd(n);
  92. }
  93. };
  94.  
  95. void query(int u) {
  96. pre=Query(rd[u]);
  97. }
  98.  
  99. bool inside(int u) {
  100. int cur=pre;
  101. pre=Query(rd[u]);
  102. return pre==cur;
  103. }
  104.  
  105. void Answer(int u,int v) {
  106. assert(perm[u]==perm[v]);
  107. }
  108.  
  109. void prec(int n) {
  110. rep(i,0,2*n) perm[i+1]=i/2;
  111. random_shuffle(perm+1,perm+2*n+1);
  112. }
  113.  
  114. int bp=0;
  115.  
  116. void gao(int l,int r,VI c,bool f) {
  117. int n=r-l+1,md=0;
  118. if (n==1) { Answer(rd[x[l]],rd[c[0]]); return; }
  119. if (f) {
  120. md=r-sp[n];
  121. rep(i,md+1,r+1) query(x[i]);
  122. } else {
  123. md=l+sp[n]-1;
  124. rep(i,l,md+1) query(x[i]);
  125. }
  126. VI fl,fr;
  127. random_shuffle(all(c),RNG());
  128. rep(i,0,SZ(c)) {
  129. if (SZ(fl)==md-l+1) fr.pb(c[i]);
  130. else if (SZ(fr)==r-md) fl.pb(c[i]);
  131. else if (l==0&&pins[c[i]]<=md) fl.pb(c[i]);
  132. else if (inside(c[i])) fl.pb(c[i]);
  133. else fr.pb(c[i]);
  134. }
  135. gao(l,md,fl,1);
  136. gao(md+1,r,fr,0);
  137. }
  138.  
  139. void Solve(int nn) {
  140. n=nn;
  141. prec(n);
  142. rep(i,1,2*n+1) rd[i]=i;
  143. random_shuffle(rd+1,rd+2*n+1,RNG());
  144. rep(i,1,2*n+1) {
  145. if (inside(i)) {
  146. pins[i]=SZ(x)-1;
  147. p1[SZ(x)]++;
  148. p2[SZ(x)]+=1./SZ(x);
  149. y.pb(i);
  150. } else {
  151. x.pb(i);
  152. }
  153. }
  154. rep(i,1,n+1) p1[i]+=p1[i-1];
  155. per(i,1,n+1) p2[i]+=p2[i+1];
  156. rep(i,2,n+1) {
  157. dp[i]=1e9;
  158. int pl=max(1,sp[i-1]);
  159. db fval=calc(pl,i-pl);
  160. while (pl<i/2) {
  161. db gval=calc(pl+1,i-pl-1);
  162. if (fval>gval) fval=gval,++pl;
  163. else break;
  164. }
  165. dp[i]=fval; sp[i]=pl;
  166. }
  167. gao(0,n-1,y,1);
  168. printf("%d\n",totQ);
  169. }
  170.  
  171. int main() {
  172. Solve(44000);
  173. }
Success #stdin #stdout 0.08s 20376KB
stdin
Standard input is empty
stdout
995527