抽奖 / Lottery JOI Open 2025

[JOI Open 2025] 抽奖 / Lottery

有 nn 个盒子，第 ii 个盒子有 XiX_i 个红球和 YiY_i 个蓝球。

定义一次试验的结果如下：

  • 取出区间 [l,r][l,r]，满足区间长度偶数；
  • 多次操作，每次操作可以选择 r−l+12\frac{r-l+1}{2} 个盒子，取出其中的红球，并对于剩下的盒子，取出蓝球。直到某一个盒子为空为止。
  • 你能进行的最多的操作次数就是这次试验的结果。

多次询问，每次给一个区间，求试验结果。

n≤105,Xi,Yi≤109n\le 10^5,X_i,Y_i\le 10^9。

看起来没什么头绪。

不妨设 l=1,r=nl=1,r=n，考虑二分答案，那么问题就变成判定 kk 轮操作是否能经行。

设 aia_i 表示最终 ii 盒子取了多少个红球，那么显然要满足 max⁡{0,Yi−k}≤ai≤min⁡{Xi,K}\max\{0,Y_i-k\}\le a_i\le \min\{X_i,K\}；设 mni=max⁡{0,Yi−k},mxi=min⁡{K,Xi}mn_i=\max\{0,Y_i-k\},mx_i=\min\{K,X_i\}。

然后注意到如下事实：能进行 kk 轮操作，充要于 ∑mni≤nk2≤∑mxi\sum mn_i\le \frac{nk}{2}\le \sum mx_i。

证明：

充分性显然，下证必要性：

不妨构造一组合法的 aia_i，显然构造十分简单。

然后每次我们对最大的 n2\frac{n}{2} 的 aia_i 执行 ai←ai−1a_i\leftarrow a_i-1；那么归纳可证最终一定存在一种合法操作方式使得最终所有 ai=0a_i=0。

将上述操作逆过来即可得到合法序列。

剩下的就简单了，将条件拆分为 33 个：

  • k≤min⁡{Xi+Yi}k\le \min\{X_i+Y_i\}。
  • k≤∑min⁡{Xi,k}k\le \sum \min\{X_i,k\}。
  • k≤∑max⁡{Yi,k}k\le \sum \max\{Y_i,k\}。

使用主席树或者 Wavelet 维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
using ll=long long;
int n,lg[N];
ll st[18][N];
struct Bitset{
    ll cnt[N],b[N];
    Bitset(){}
    Bitset(ll t[],ll t2[],int n){
        for(int i=0;i<n;i++)b[i]=t[i],cnt[i]=t2[i];
        for(int i=1;i<n;i++)b[i]+=b[i-1],cnt[i]+=cnt[i-1];
    }
    ll ask(int k){return k?b[k-1]:0;}
    ll asks(int k){return k?cnt[k-1]:0;}
};
struct Wavelet{
    ll am[N],ss,n,t[N],p[N],t2[N];
    Bitset b[18];
    void init(vector<int>a){
        ss=0;
        n=a.size();
        for(int u:a)am[++ss]=u;
        sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1;
        for(int &u:a)u=lower_bound(am+1,am+1+ss,u)-am;
        for(int i=17;~i;i--){
            int x=0,y=0;
            for(int j=0;j<n;j++)t[j]=(a[j]>>i&1),t2[j]=a[j]>>i&1?0:am[a[j]];
            b[i]=Bitset(t,t2,n);
            for(int j=0;j<n;j++)if(a[j]>>i&1)t[y++]=a[j];else a[x++]=a[j];
            p[i]=x;
            for(int j=0;j<y;j++)a[x+j]=t[j];
        }
    }
    ll query(int l,int r){
        ll res=0,sum=0,cnt=-(r-l+1>>1);--l;
        for(int i=17;~i;i--){
            ll ql=b[i].ask(l),qr=b[i].ask(r);
            ll sl=b[i].asks(l),sr=b[i].asks(r);
            if((res|1<<i)<=ss&&sum+sr-sl+(cnt+qr-ql)*am[res|(1<<i)]>=0)
                res|=(1<<i),sum+=sr-sl,l=p[i]+ql,r=p[i]+qr;
            else cnt+=qr-ql,l-=ql,r-=qr;
        }
        return -(sum+(r-l)*am[res])/cnt;
    }
}tx,ty;
void init(int N,int Q,vector<int>x,vector<int>y){
    n=N;
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++)st[0][i]=x[i-1]+y[i-1];
    for(int i=1;i<=17;i++)for(int j=1;j+(1<<i)-1<=n;j++)
        st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
    tx.init(x),ty.init(y);
}
int max_prize(int l,int r){
    l++,r++;
    int k=lg[r-l+1];
    return min({st[k][l],st[k][r-(1<<k)+1],tx.query(l,r),ty.query(l,r)});
}