这个区间离散化把我调死了。。
总之用vector来离散化，然后叶子节点维护的是一段区间，记录下每个叶子结点的起点+长度
千万要注意下标不能弄错！
#include<bits/stdc++.h>
#define MAXN 400005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int N;
int X[MAXN],Y[MAXN],L[MAXN],R[MAXN];
vector<int> v;
int X1,X2,Y1,Y2,A1,A2,B1,B2,C1,C2,M1,M2;
struct segtree
{
ll sum[*MAXN];
int lazy[*MAXN],len[*MAXN];
void pushup(int k)
{
sum[k]=sum[k*]+sum[k*+];
}
void pushdown(int k)
{
if(!lazy[k]) return;
for(int i=k*;i<=k*+;i++)
{
lazy[i]+=lazy[k];
sum[i]+=lazy[k]*len[i];
}
lazy[k]=;
return;
}
void build(int k,int l,int r)
{
if(l==r)
{
len[k]=v[l]-v[l-];
return;
}
int mid=(l+r)/;
build(k*,l,mid); build(k*+,mid+,r);
pushup(k);
len[k]=len[k*]+len[k*+];
}
void update(int k,int l,int r,int x,int y)
{
if(x>r||l>y) return;
if(l>=x&&r<=y)
{
lazy[k]++;
sum[k]+=len[k];
return;
}
pushdown(k);
int mid=(l+r)/;
update(k*,l,mid,x,y); update(k*+,mid+,r,x,y);
pushup(k);
}
int query(int k,int l,int r,ll x)
{
if(l==r)
{
int cnt=sum[k]/len[k];
int id=(x-)/cnt;
return v[l-]+id;
}
pushdown(k);
int mid=(l+r)/;
if(sum[k*]>=x) return query(k*,l,mid,x); else return query(k*+,mid+,r,x-sum[k*]);
}
}seg;
int main()
{
scanf("%d",&N);
scanf("%d%d%d%d%d%d",&X1,&X2,&A1,&B1,&C1,&M1);
scanf("%d%d%d%d%d%d",&Y1,&Y2,&A2,&B2,&C2,&M2);
X[]=X1; X[]=X2; Y[]=Y1; Y[]=Y2;
for(int i=;i<=N;i++)
{
X[i]=(1LL*A1*X[i-]+1LL*B1*X[i-]+C1)%M1;
Y[i]=(1LL*A2*Y[i-]+1LL*B2*Y[i-]+C2)%M2;
}
for(int i=;i<=N;i++)
{
L[i]=min(X[i],Y[i])+;
R[i]=max(X[i],Y[i])+; R[i]++;
v.push_back(L[i]); v.push_back(R[i]);
} sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end()); int sz=(int)v.size()-;
seg.build(,,sz);
ll sum=;
for(int i=;i<=N;i++)
{
int posl=lower_bound(v.begin(),v.end(),L[i])-v.begin();
int posr=lower_bound(v.begin(),v.end(),R[i])-v.begin();
posl++;
seg.update(,,sz,posl,posr);
sum+=R[i]-L[i];
printf("%d\n",seg.query(,,sz,(sum+)/));
}
return ;
}
update:其实用数组离散化也可以，，只是我的数组开小了一直不知道错在哪里。。
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define maxn 800005
#define MAXN 800005
#define ll long long
ll x[maxn],y[maxn],l[maxn],r[maxn];
ll n,a1,a2,b1,b2,c1,c2,m1,m2,m;
vector<ll>v;
ll h[maxn]; #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
//叶子结点l代表第l个区间，即起点为v[l-1],长度为v[l]-v[l-1]
ll sum[maxn<<],lazy[maxn<<],len[maxn<<];
void pushup(int rt){
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void pushdown(int rt){
if(lazy[rt]){
for(int i=(rt<<);i<=(rt<<|);i++){
lazy[i]+=lazy[rt];
sum[i]+=lazy[rt]*len[i];
}
lazy[rt]=;
}
}
void build(int l,int r,int rt){
if(l==r){
len[rt]=h[l+]-h[l];
return;
}
int m=l+r>>;
build(lson);build(rson);
len[rt]=len[rt<<]+len[rt<<|];
}
void update(int L,int R,int l,int r,int rt){
if(L>R)return;
if(L<=l && R>=r){
lazy[rt]++;
sum[rt]+=len[rt];
return;
}
pushdown(rt);
int m=l+r>>;
if(L<=m)update(L,R,lson);
if(R>m)update(L,R,rson);
pushup(rt);
}
ll query(ll k,int l,int r,int rt){
if(l==r){
int tmp=sum[rt]/len[rt];
int tmp2=(k-)/tmp;
return h[l]+tmp2;
}
pushdown(rt);
int m=l+r>>;
if(k<=sum[rt<<])return query(k,lson);
else return query(k-sum[rt<<],rson);
}
int main(){
cin>>n;
cin>>x[]>>x[]>>a1>>b1>>c1>>m1;
cin>>y[]>>y[]>>a2>>b2>>c2>>m2;
for(int i=;i<=n;i++){
x[i]=(a1*x[i-]+b1*x[i-]+c1)%m1;
y[i]=(a2*y[i-]+b2*y[i-]+c2)%m2;
}
for(int i=;i<=n;i++){
l[i]=min(x[i],y[i])+;
r[i]=max(x[i],y[i])+;
r[i]++;
h[++m]=l[i];h[++m]=r[i];
}
sort(h+,h++m);
m=unique(h+,h++m)-h-;
build(,m-,); ll sum=;
for(int i=;i<=n;i++){
int posl=lower_bound(h+,h+m+,l[i])-h;
int posr=lower_bound(h+,h+m+,r[i])-h;
posr--;
sum+=r[i]-l[i];
update(posl,posr,,m-,);
cout<<query((sum+)/,,m-,)<<'\n';
}
}