2021暑假 HDU中超第九场 1006

Guess the weight

*Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 235 Accepted Submission(s): 55*

题意

有一个初始含 \(n\) 张牌的牌堆，每张牌的费用 \(a_i \le 2\times10^5\)

有一种法术：从牌堆中抽取一张牌，然后猜测下一张牌的费用大于它还是小于它，若猜中即可抽取第二张牌（等于算没猜中）

现在有 \(q\) 个操作，分两种：

往牌堆里塞 \(x\) 张费用为 \(w\) 的牌，\(w\le 2\times10^5\)
使用法术，要求输出能抽到第二张牌的概率（最简分数形式）

Sample Input

Sample Output

0/1
2/3
2/3
1/1
5/6
201/3502

\(\quad\)

常数爆炸并且最后也没卡过去的思路：

~~这部分写着留念一下愿天下没有卡常~~

因为牌的费用在 \(2\times 10^5\)?? 之内，所以可以考虑维护一个 \(cnt\) 序列，加入 \(x\)? 张费用为 \(w\)? 的牌就是在序列第 \(w\)? 位上加 \(x\)?

查询的时候，显然我们会比较第一张牌的费用左边和右边那边牌数更多，选择较多的那一边

显然存在一个分界线，抽中左边都猜大于，抽中右边都猜小于

当抽到第一张牌的费用为 \(w\)????????? 时，选小于猜中概率即为 \((sum(w)-cnt(w)) /(cnt_总-1)\)????????? ，\(sum\)??????? 表示前缀和，选大于同理。选择这张牌的概率是 \(cnt(w)/cnt_总\)??

计算答案时分母的 \(cnt_总\times(cnt_总-1)\) 保持不变，只需计算所有位置的 \((sum(w)-cnt(w))\times cnt(w)\) 之和

考虑用线段树维护

线段树维护区间?卡牌总数，区间前缀和之和，后缀和之和，区间所有点的答案之和

把修改操作分成三部分：单点修改，右边前缀和区间加，左边后缀和区间加

为了便于查找分界线（前缀和大于后缀和的第一个位置），还需要维护区间前缀和的最小值和后缀和的最大值

10M输入的大样例测完是对的，可惜这题卡常。。（代码扔最后）

\(\quad\)

正解：

上面这种思路完全想复杂了属于是

从总情况数的角度考虑，从 \(n\) 张牌里抽两张有 \(n \times(n-1)\)? 种方案

还是把牌按费用分成左右两份，策略为：第一张牌在左时，猜大于；第一张牌在右则猜小于

那么：

两张牌分别在左右两边，一定能猜对
两张牌费用相同，一定猜错
两张牌在同一边，并且费用不相同时，有一半能猜对

前两种很好理解，第三种就是两张牌离 \(mid\) 远的先出现就能猜对，否则猜错

先二分找到前缀和大于后缀和的第一个位置，按此划分之后计算就好了

维护前缀和，计算重复数个数方法有很多，树状数组就可以（话说这个 \(O(nlog^2_n)\)? 都过了，上面那棵 \(nlogn\) 的线段树还TLE，~~果然人傻常数大~~）

\(\quad\)

AC代码（轻度压行）：

#include
using namespace std;
#define ll long long
const ll maxn = 200100;

ll a[maxn], mxn = 200001, cnt = 0;
struct BitTree{
    ll t[2*maxn];
    ll lb(int x) {return x&-x;}
    void add(int p, ll ad){for(int i=p;i<=mxn*2;i+=lb(i)) t[i]+=ad;}
    ll sum(int p){ return p?t[p] + sum(p-lb(p)):0;}//ps:迭代比递归快，卡常时勿贪压行
    void clear(){memset(t, 0, sizeof(t));}
}bt, btcf;

int get_mid(){//前缀和大于后缀和的第一个位置
    int l = 1, r = mxn, mid;
    while(l < r){
        mid = (l + r)/2;
        if(bt.sum(mid)*2 > cnt+a[mid]) r = mid;
        else l = mid + 1;
    } return r;
}
ll gcd(ll x, ll y){ return (y==0) ? x : gcd(y, x%y);}
inline void add(int p, ll d){
    bt.add(p, d), btcf.add(p, 2*a[p]*d + d*d - d);
    a[p] += d, cnt += d;
}

signed main(){
    ll T = 1, n, Q, opt, x, w;
    cin >> T;
    while(T--){
        for(int i=1;i<=mxn;i++) a[i] = 0;
        bt.clear(); btcf.clear(); cnt = 0;
        cin >> n >> Q;
        for(int i=1;i<=n;i++) scanf("%d", &x), add(x, 1);
        for(int i=1;i<=Q;i++){
            cin >> opt;
            if(opt == 1) scanf("%d%d", &x, &w), add(w, x);
            else{
                int mid = get_mid();
                ll l = bt.sum(mid - 1), r = cnt - l;
                ll lf = btcf.sum(mid - 1), rf = btcf.sum(mxn) - lf;
                ll fm = cnt * (cnt - 1);
                ll fz = fm - (l * (l - 1) + lf)/2 - (r * (r - 1) + rf)/2;
                ll g = gcd(fz, fm);
                cout << fz/g << '/' << fm/g << '\n';
            }
        }
    }
}

\(\quad\)

TLE代码：

int n, q;
int mxn = 2e5 + 10;

struct SegTree{
    int l, r;
    ll sw, sum[2];//区间左右前缀答案
    ll sl[2];//单点前后缀，区间最小前缀和最大后缀
    int tg[2];//前缀和加tag
}t[maxn<<2];

inline void push_up(int p){
    t[p].sum[0] = t[p<<1].sum[0] + t[p<<1|1].sum[0];
    t[p].sum[1] = t[p<<1].sum[1] + t[p<<1|1].sum[1];
    t[p].sl[0] = min(t[p<<1].sl[0], t[p<<1|1].sl[0]);
    t[p].sl[1] = max(t[p<<1].sl[1], t[p<<1|1].sl[1]);
    t[p].sw = t[p<<1].sw + t[p<<1|1].sw;
}
inline void push_sum(int p, int ad, int dir){
    t[p].sl[dir] += ad;
    t[p].sum[dir] += ad * t[p].sw;
    t[p].tg[dir] += ad;
}
inline void push_down(int p){
    if(t[p].tg[0]){
        push_sum(p<<1, t[p].tg[0], 0);
        push_sum(p<<1|1, t[p].tg[0], 0);
        t[p].tg[0] = 0;
    }
    if(t[p].tg[1]){
        push_sum(p<<1, t[p].tg[1], 1);
        push_sum(p<<1|1, t[p].tg[1], 1);
        t[p].tg[1] = 0;
    }
}

void build(int p, int l, int r){
    t[p].l = l; t[p].r = r;
    t[p].sw = t[p].sum[0] = t[p].sum[1] = 0;
    t[p].tg[0] = t[p].tg[1] = t[p].sl[0] = t[p].sl[1] = 0;
    if(l == r) return;
    int mid = (l+r)/2;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    push_up(p);
}

void add_w(int p, int pos, int w){
    if(t[p].l == t[p].r){
        t[p].sw += w;
        t[p].sl[0] += w; t[p].sl[1] += w;
        t[p].sum[0] = (t[p].sl[0] - t[p].sw) * t[p].sw;
        t[p].sum[1] = (t[p].sl[1] - t[p].sw) * t[p].sw;
        return;
    }
    push_down(p);
    int mid = (t[p].l + t[p].r)/2;
    if(pos <= mid) add_w(p<<1, pos, w);
    else add_w(p<<1|1, pos, w);
    push_up(p);
}

void add_sum(int p, int l, int r, int ad, int dir){//区间前缀和加
    if(l > r) return;
    if(l <= t[p].l && t[p].r <= r){
        push_sum(p, ad, dir);
        return;
    }
    push_down(p);
    int mid = (t[p].l + t[p].r)/2;
    if(l <= mid) add_sum(p<<1, l, r, ad, dir);
    if(mid < r) add_sum(p<<1|1, l, r, ad, dir);
    push_up(p);
}

ll ask_sum(int p, int l, int r, int dir){
    if(l > r) return 0;
    if(l <= t[p].l && t[p].r <= r) return t[p].sum[dir];
    push_down(p);
    ll res = 0, mid = (t[p].l + t[p].r)/2;
    if(l <= mid) res += ask_sum(p<<1, l, r, dir);
    if(mid < r) res += ask_sum(p<<1|1, l, r, dir);
    return res;
}

int find_mid(int p){//寻找前缀小于后缀的第一个位置
    if(t[p].l == t[p].r) return t[p].l;
    push_down(p);
    if(t[p<<1|1].sl[0] >= t[p<<1|1].sl[1]) return find_mid(p<<1);//右边能满足走左边
    else return find_mid(p<<1|1);//右边不满足走右边
}

ll gcd(ll x, ll y){
    while(y > 0){
        swap(x, y);
        y = y%x;
    }
    return x;
}

void solve(){
    cin >> n >> q;
    build(1, 1, mxn);
    for(int i=1;i<=n;i++){
        int x; cin >> x;
        add_w(1, x, 1);
        add_sum(1, x+1, mxn, 1, 0);
        add_sum(1, 1, x-1, 1, 1);
    }
    for(int i=1;i<=q;i++){
        int opt, x, w;
        cin >> opt;
        if(opt == 1){
            cin >> x >> w;
            add_w(1, w, x);
            add_sum(1, w+1, mxn, x, 0);
            add_sum(1, 1, w-1, x, 1);
        }else{
            int r = find_mid(1);
            ll fz = 0, fm = 1ll * t[1].sw * (t[1].sw - 1);
            fz += ask_sum(1, 1, r, 1);
            fz += ask_sum(1, r+1, mxn, 0);
            ll g = gcd(fz, fm);
            cout << fz/g << '/' << fm/g << '\n';
        }
    }
}

补题题解卡常线段树树状数组 ACM

2021暑假 HDU中超第九场 1006