2019牛客暑期多校训练营（第七场）E-Find the median（思维+树状数组+离散化+二分）

>传送门<

题意：给n个操作，每次和（1e9范围内）即往数组里面插所有 $x \in [L_i,R_i]$ 的所有数，求每次操作后的中位数
思路：区间离散化然后二分答案，因为小于中位数的数字恰好有个，这显然具有单调性。那么问题就转化为如何求小于等于某个数x的数一共有多少个。

考虑以下两种情况：假设左端点小于等于x的区间一共有q个

如果x不落在任何一个区间，那么答案显然是 $\sum_{i=1}^q (R_i-L_i+1)$
否则假设x同时落在m个区间中，答案是 $\sum_{i=1}^{q-m}(R_i-L_i+1)+\sum_{i=q-m+1}^q (x+1-L_i)$

做一点点数学上的变换：令

$\sum_{i=1}^{q-m}(R_i-L_i+1)+\sum_{i=q-m+1}^q (x+1-L_i)=\sum_{N_i\le x}N_i-\sum_{L_i\le x}L_i+m(x+1)$

注意到在第一种情况下m=0，所以我们就成功归约到只有一种情况。对区间的左右端点离散化，用两个树状数组分别维护的前缀和和m以后，我们就能够 $O(\log N)$ 地判断一个解是否可行。总复杂度 $O(N\log N\log M)$ ，M是因为取值范围是1e9

Code

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 400010;

ll n, cnt, tot;

ll x[maxn], y[maxn], l[maxn], r[maxn];

int a1, b1, c1, a2, b2, c2, m1, m2;

ll z[maxn<<1], bit1[maxn<<1], bit2[maxn<<1];

void add(ll a[], int i, int x) {

    while (i<=cnt) {

        a[i] += x;

        i += i&(-i);

    }

}

ll query(ll a[], int i){

    ll res = 0;

    while (i>0) {

        res += a[i];

        i -= i&(-i);

    }

    return res;

}

void read() {

    cin>>n;

    cin>>x[1]>>x[2]>>a1>>b1>>c1>>m1;

    cin>>y[1]>>y[2]>>a2>>b2>>c2>>m2;

    for(int i = 1; i <= n; i++){

        if(i>2){

            x[i] = (a1*x[i-1]+b1*x[i-2]+c1)%m1;

            y[i] = (a2*y[i-1]+b2*y[i-2]+c2)%m2;

        }

        l[i] = min(x[i],y[i])+1;

        r[i] = max(x[i],y[i])+1;

        z[++cnt] = l[i]; z[++cnt] = r[i]+1;

    }

    sort(z+1,z+cnt+1);

    cnt = unique(z+1,z+cnt+1)-z-1;

} 

int main()

{

    read();

    for(int i = 1; i <= n; i++) {

        tot += r[i]-l[i]+1;

        int L=lower_bound(z+1,z+cnt+1,l[i])-z, R=lower_bound(z+1,z+cnt+1,r[i]+1)-z;

        add(bit1,L,-l[i]), add(bit1,R,r[i]+1);

        add(bit2,L,1), add(bit2,R,-1);

        //二分查找

        int left = 1, right = 1e9;

        while(left<right) {

            int mid = (left+right)/2;

            int q = upper_bound(z+1,z+cnt,mid)-z-1;

            ll tmp = query(bit1, q)+query(bit2, q)*(mid+1);

            if(tmp<(tot+1)/2) left = mid+1;

            else right = mid;

        }

        cout<<left<<endl;

    }

    return 0;

}

有的地方没用long long 就WA了，在蕊芬学姐的指导下改过来了~

巴特西

2019牛客暑期多校训练营（第七场）E-Find the median（思维+树状数组+离散化+二分）

最新文章

热门文章