https://ac.nowcoder.com/acm/contest/887/E

树状数组做法（代码有注释）

#include
      
       using namespace std;typedef long long ll;const int M=4e5+5;int x[M],y[M],l[M],r[M],ans[M<<1],tot;ll bit1[M<<3],bit2[M<<3];int lowbit(int x){    return x&(-x);}void add(ll bit[], int p, int x) {    while(p<=tot){        bit[p]+=x;        p+=lowbit(p);    }}ll query(ll bit[], int p) {    ll ans = 0;    while(p>0){        ans+=bit[p];        p-=lowbit(p);    }    return ans;}int main(){    int n;    scanf("%d",&n);    ll a1,a2,b1,b2,c1,c2,m1,m2;    scanf("%lld%lld%lld%lld%lld%lld",&x[1],&x[2],&a1,&b1,&c1,&m1);    scanf("%lld%lld%lld%lld%lld%lld",&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;        ans[++tot]=l[i];        ans[++tot]=r[i]+1;     }    ///离散化处理    sort(ans+1,ans+tot+1);    tot=unique(ans+1,ans+tot+1)-ans-1;    ll nownum=0;    for(int i=1;i<=n;i++){                 nownum+=(r[i]-l[i]+1);///加上当前区间数的数目 ，为了达到用数目找中位数的目的        int L=lower_bound(ans+1,ans+tot+1,l[i])-ans;///找到l r分别在离散化后的位置        int R=lower_bound(ans+1,ans+tot+1,r[i]+1)-ans;        ///bit1 记录的是总共数的数目的前缀和，所以左右端点就那样赋值，前缀和起来就是总数：r[i]-l[i]+1;        add(bit1,L,-l[i]);        add(bit1,R,r[i]+1);        //bit2 记录L的数目的前缀和        add(bit2,L,1);        add(bit2,R,-1);        ///二分找        L=1,R=1e9;        while(L
       
        >1;            int pos=upper_bound(ans+1,ans+tot+1,midd)-ans-1;            ///若查询到query(bit2)不等于0，说明midd前面有若干个左区间端点 没有对应的右区间端点，即query(bit1)算不完全，所以要加还给temp；            ll tmp=query(bit1,pos)+query(bit2,pos)*(midd+1);            if(tmp<(nownum+1)/2){
    ///用数目找中位数                L=midd+1;            }else{                R=midd;            }        }        printf("%d\n",L);    }    return 0;}