2019牛客第七场E题 (Find the median) 思维

题意：给n个操作，每次和 （1e9范围内）即往数组里面插所有 的所有数，求每次操作后的中位数

题解：区间离散化然后二分答案，因为小于中位数的数字恰好有个，这显然具有单调性。那么问题就转化为如何求小于等于某个数x的数一共有多少个。

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

• 如果x不落在任何一个区间，那么答案显然是
• 否则假设x同时落在m个区间中，答案是

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

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

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int maxn = 400010;
const int N = maxn << 2;
int n,x[maxn],y[maxn],l[maxn],r[maxn];
int a1,b1,c1,a2,b2,c2,m1,m2;
int z[N];

class Fenwick_tree{
private:
    inline int lowbit(int x) { return x & (-x); }
    int bit[N];
public:

    void add(int x,int v){
        for (; x < N;x+=lowbit(x)){
            bit[x] += v;
        }
    }

    int query(int x){
        int res = 0;
        for (; x;x-=lowbit(x)){
            res += bit[x];
        }
        return res;
    }
};
Fenwick_tree bit1,bit2;

int32_t main(){
    int tot=0,cnt=0;
    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;
    for(int i=1;i<=n;i++){
        tot+=r[i]-l[i]+1;
        int L=lower_bound(z+1,z+cnt,l[i])-z;
        int R=lower_bound(z+1,z+cnt,r[i]+1)-z;
        bit1.add(L,-l[i]);
        bit1.add(R,r[i]+1);
        bit2.add(L,1);
        bit2.add(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;
            int tmp=bit1.query(q)+bit2.query(q)*(mid+1);
            if(tmp<(tot+1)/2){
                left=mid+1;
            }
            else{
                right=mid;
            }
        }
        cout<<left<<endl;
    }

}