差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:atcoder_beginner_contest_127_vp [2020/07/21 10:59]
wzx27
+++ 2020-2021:teams:wangzai_milk:atcoder_beginner_contest_127_vp [2020/07/21 11:14] (当前版本)
wzx27
@@ 行 1: / 行 1: @@
 比赛链接：[[https://atcoder.jp/contests/abc127|AtCoder Beginner Contest 127]]
-=== E - Cell Distance ===
+==== E - Cell Distance ====
-== 题意 ==
+=== 题意 ===
 给一个 $n\times m$ 的网格和一个整数 $k$ ，每次取 $k$ 个格子 $(x_i,y_i)$ 得到 $v = \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(|x_i-x_j|+|y_i-y_j|)$。求所有不同取法的 $\sum v$ 。
-== 数据范围 ==
+=== 数据范围 ===
-$2 \le n\times m \le 2e5$
+$2 \le n\times m \le 2\times 10^5$
 $2 \le k \le n\times m$
-== 题解 ==
+=== 题解 ===
-考虑两个格子 $(x_i,y_i)$ 和 $(x_j,y_j)$ 对答案的贡献为 $(|x_i-x_j|+|y_i-y_j|){nm-2 \choose k-2}$，所以只要求一遍两两 $|x_i-x_j|+|y_i-y_j|$ 的值即可。
+考虑两个格子 $(x_i,y_i)$ 和 $(x_j,y_j)$ 对答案的贡献为 $(|x_i-x_j|+|y_i-y_j|){k-2 \choose nm-2}$，所以只要求一遍两两 $|x_i-x_j|+|y_i-y_j|$ 的值即可。
 <hidden code> <code cpp>
@@ 行 64: / 行 64: @@
     return 0;
 }
-</hidden> </code>
+</code> </hidden>
+\\
+==== F - Absolute Minima ====
+=== 题意 ===
+$Q$ 次两种操作维护一个函数。一开始的函数为 $f(x) = 0$，每次操作给两个整数 $a,b$ 使得 $g(x)=f(x)+|x-a|+b$ 然后用 $g(x)$ 更新 $f(x)$ ，或者查询使得 $f(x)$ 最小的 $x$ 和这个最小的 $f(x)$ 如果有多个 $x$ 输出最小的。
+=== 数据范围 ===
+$1\le Q \le 2\times 10^5$
+$-10^9 \le a,b \le 10^9$
+=== 题解 ===
+最后的函数都是形如 $f(x) = \sum |x-a_i| + B$ 的，于是最小值的 $x$ 在这些$a_i$的中间取得，即对 $a_i$ 排序后，如果有奇数个则为 $a_{\frac {n+1}2}$ ,否则为 $a_{\frac n2}$。
+比赛的时候做法比较复杂，离线离散化 $a_i$ 后维护两棵线段树，一棵是权值线段树，另一棵是区间求和的线段树。每次查询时，通过权值线段树得到 $x = argmin \; f(x)$ ,然后通过区间求和得到 $\sum_{a_i \le x} a_i$ 和 $\sum_{a_i>x} a_i$，再结合 $B = \sum b_i$ 就可以得到 $f_{min}(x)$ 。
+<hidden code> <code cpp>
+#include<bits/stdc++.h>
+#define ALL(x) (x).begin(),(x).end()
+#define ll long long
+#define pii_ pair<int,int>
+#define mp_ make_pair
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=(a);i<=(b);i++)
+#define per(i,a,b) for(int i=(a);i>=(b);i--)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+const int maxn = 2e5+5;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+vector<pii_> op;
+vector<int> g;
+int tr[maxn<<2];
+ll sum[maxn<<2];
+void update(int id,int stl,int str,int pos)
+{
+    if(stl==str){
+        tr[id]++;return ;
+    }
+    int mid = (stl+str)>>1;
+    if(pos<=mid) update(id<<1,stl,mid,pos);
+    else update(id<<1|1,mid+1,str,pos);
+    tr[id] = tr[id<<1] + tr[id<<1|1];
+}
+int query(int id,int l,int r,int k)
+{
+    if(l==r){
+        return l;
+    }
+    int mid = (l+r)>>1;
+    if(tr[id<<1] >= k) return query(id<<1,l,mid,k);
+    else return query(id<<1|1,mid+1,r,k-tr[id<<1]);
+}
+void change(int id,int l,int r,int pos,int k)
+{
+    if(l==r){
+        sum[id] += k;
+        return ;
+    }
+    int mid = (l+r)>>1;
+    if(pos<=mid) change(id<<1,l,mid,pos,k);
+    else change(id<<1|1,mid+1,r,pos,k);
+    sum[id] = sum[id<<1] + sum[id<<1|1];
+}
+ll ask(int id,int stl,int str,int l,int r)
+{
+    if(stl==l && str==r) return sum[id];
+    int mid = (stl+str)>>1;
+    if(r<=mid) return ask(id<<1,stl,mid,l,r);
+    else if(l>mid) return ask(id<<1|1,mid+1,str,l,r);
+    else return ask(id<<1,stl,mid,l,mid) + ask(id<<1|1,mid+1,str,mid+1,r);
+}
+int main()
+{
+    fastio();
+    int q,o,a,b; cin>>q;
+    ll B = 0;
+    while(q--){
+        cin>>o;
+        if(o==1){
+            cin>>a>>b;
+            op.pb(mp_(a,b));
+            g.pb(a);
+        }else{
+            op.pb(mp_(-inf,-inf));
+        }
+    }
+    sort(ALL(g));
+    g.erase(unique(ALL(g)),g.end());
+    int n = g.size();
+    int cnt = 0;
+    for(auto x:op){
+        if(x.fi==-inf && x.se==-inf){
+            int id = query(1,1,n,(cnt+1)/2) - 1;
+            ll ans1 = g[id];
+            ll k = (cnt+1)/2;
+            ll ans2;
+            {
+                int L = 1,R = cnt,res=-1;
+                while(L<=R){
+                    int mid = (L+R)>>1;
+                    if(query(1,1,n,mid)>id+1) R=mid-1,res=mid;
+                    else L = mid+1;
+                }
+                if(res==-1) ans2 = ans1 * cnt - ask(1,1,n,1,id+1);
+                else{
+                    ll tmp = ask(1,1,n,1,id+1);
+                    ans2 = ans1 * (res-1) - tmp + sum[1] - tmp - ans1 * (cnt-res+1);
+                }
+            }
+            cout<<ans1<<" "<<ans2+B<<endl;
+        }else{
+            int pos = lower_bound(ALL(g),x.fi)-g.begin()+1;
+            update(1,1,n,pos);
+            change(1,1,n,pos,x.fi);
+            cnt++;
+            B += x.se;
+        }
+    }
+    return 0;
+}
+</code> </hidden>
+\\

CVBB ACM Team

用户工具

站点工具

差别

页面工具