每个叶子结点表示 大于等于当前这个点小于后面一个点的 区间，对这些点建线段树，查询区间第 (n 1)/2 大
代码语言：javascript复制#include <bits/stdc .h>
#define ll long long
using namespace std;
const int N = 4e5 10;
struct No{
int rt,lazy,cnt;
ll sum;
}no[N<<3];
int x[N], y[N], A[3], B[3], C[3], M[3], L[N], R[N];
int pre[N<<1],n,tot;
ll num[N<<3];
void spread(int rt,int l,int r){
int tp,mid;
if(no[rt].lazy){
tp = no[rt].lazy; mid = ( l r ) >> 1;
no[rt].lazy = 0;
no[rt<<1].cnt =tp; no[rt<<1|1].cnt =tp;
no[rt<<1].lazy =tp; no[rt<<1|1].lazy =tp;
no[rt<<1].sum = 1ll*(pre[mid] - pre[l-1])*tp;
no[rt<<1|1].sum =1ll*(pre[r] - pre[mid])*tp;
}
}
void update(int rt,int l,int r,int L,int R){
if(L<=l&&R>=r){
no[rt].lazy ; no[rt].cnt ;
no[rt].sum =( pre[r] - pre[l-1]);
return ;
}
spread(rt,l,r);
int mid = (l r)>>1;
if(L<=mid)update(rt<<1,l,mid,L,R);
if(R>mid)update(rt<<1|1,mid 1,r,L,R);
no[rt].sum = no[rt<<1].sum no[rt<<1|1].sum;
}
int query(int rt,int l,int r,ll k){
if(l==r){
return num[l] (k-1)/no[rt].cnt;
}
spread(rt,l,r);
int mid = ( l r )>>1;
if(no[rt<<1].sum<k) return query(rt<<1|1,mid 1,r,k-no[rt<<1].sum);
return query(rt<<1,l,mid,k);
}
int main()
{
cin >> n;
cin >> x[1] >> x[2] >> A[1] >> B[1] >> C[1] >> M[1];
cin >> y[1] >> y[2] >> A[2] >> B[2] >> C[2] >> M[2];
for(int i = 1; i <= n; i) {
if(i >= 3) {
x[i] = (1LL * A[1] * x[i - 1] 1LL * B[1] * x[i - 2] C[1]) % M[1];
y[i] = (1LL * A[2] * y[i - 1] 1LL * B[2] * y[i - 2] C[2]) % M[2];
}
L[i] = min(x[i],y[i]) 1;
R[i] = max(x[i],y[i]) 2;
num[i*2-1] = L[i];
num[i*2] = R[i];
}
sort(num 1,num 2*n 1);
tot = unique(num 1,num 2*n 1) - num - 1;
num[tot 1] = num[tot];
for(int i=1;i<=tot; i){
pre[i] = pre[i-1] num[i 1] - num[i];
}
ll now = 0;
for(int i=1;i<=n; i){
L[i] = lower_bound(num 1,num tot 1,L[i]) - num;
R[i] = lower_bound(num 1,num tot 1,R[i]) - num - 1;
now =pre[R[i]] - pre[L[i]-1];
update(1,1,tot,L[i],R[i]);
printf("%dn",query(1,1,tot,(now 1)/2));
}
return 0;
}
