题意

每次插入区间\([L_i,R_i]\)之间的数，查询中位数。

分析

把区间离散化为点，就可以用线段树来支持更新和查询了。

我们将区间右端点+1，那么一个区间的长度就是右端点减去左端点，然后我们将所有端点离散化一下用线段树维护就行了。

例如区间\([1,2],[2,4]\)

区间右端点+1后变成\([1,3),[2,5)\)

离散化后\(1,2,3,4\)

\(1\)代表区间\([1,2)\)，\(2\)代表区间\([2,3)\)，\(3\)代表区间\([3,5)\)，\(4\)不表示任何区间。

  • 更新区间\([l,r)\)（右端点加+1后的r）时，因为点\(r-1\)代表的区间是\([r-1,r)\)，所以我们更新区间\([l,r-1]\)的点就可以了。
  • 查询时在树上二分找到中位数所在区间的点，然后计算一下是区间中哪个数就行了。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=8e5+10;
const int N=1e9;
int n,m;
ll X1,X2,A1,B1,C1,M1,Y1,Y2,A2,B2,C2,M2;
int L[maxn],R[maxn],b[maxn];
ll a[maxn<<2],tag[maxn<<2];
void up(int dl,int dr,int l,int r,int p){
    a[p]+=b[dr+1]-b[dl];
    if(l==dl&&r==dr) return tag[p]++,void();
    int mid=l+r>>1;
    if(dr<=mid) up(dl,dr,lson);
    else if(dl>mid) up(dl,dr,rson);
    else up(dl,mid,lson),up(mid+1,dr,rson);
}
int qy(int l,int r,int p,ll x,ll k){
    if(l==r){
        ll g=a[p]/(b[l+1]-b[l])+k;
        return b[l]+(x+g-1)/g-1;
    }
    int mid=l+r>>1;
    ll res=a[p<<1]+(k+tag[p])*(b[mid+1]-b[l]);
    if(x<=res) return qy(lson,x,k+tag[p]);
    else return qy(rson,x-res,k+tag[p]);
}
int main(){
    //ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    scanf("%d",&n);
    cin>>X1>>X2>>A1>>B1>>C1>>M1;
    cin>>Y1>>Y2>>A2>>B2>>C2>>M2;
    ll X=X1,Y=Y1,K=0;
    for(int i=1;i<=min(n,2);i++){
        if(i==2) X=X2,Y=Y2;
        L[i]=min(X,Y)+1,R[i]=max(X,Y)+1;
        b[++m]=L[i];b[++m]=R[i]+1;
    }
    for(int i=3;i<=n;i++){
        X=(A1*X2%M1+B1*X1%M1+C1)%M1;
        Y=(A2*Y2%M2+B2*Y1%M2+C2)%M2;
        L[i]=min(X,Y)+1,R[i]=max(X,Y)+1;
        b[++m]=L[i];b[++m]=R[i]+1;
        X1=X2;X2=X;
        Y1=Y2;Y2=Y;
    }
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    for(int i=1;i<=n;i++){
        L[i]=lower_bound(b+1,b+m+1,L[i])-b;
        R[i]=lower_bound(b+1,b+m+1,R[i]+1)-b;
        K+=b[R[i]]-b[L[i]];
        up(L[i],R[i]-1,1,m,1);
        printf("%d\n",qy(1,m,1,(K+1)/2,0));
    }
    return 0;
}