題意：給n個(gè)操作扇调，每次和
（1e9范圍內(nèi)）即往數(shù)組里面插所有
的所有數(shù)，求每次操作后的中位數(shù)
題解：區(qū)間離散化然后二分答案抢肛，因?yàn)樾∮谥形粩?shù)的數(shù)字恰好有個(gè)狼钮，這顯然具有單調(diào)性。那么問題就轉(zhuǎn)化為如何求小于等于某個(gè)數(shù)x的數(shù)一共有多少個(gè)捡絮。
考慮以下兩種情況：假設(shè)左端點(diǎn)小于等于x的區(qū)間一共有q個(gè)
- 如果x不落在任何一個(gè)區(qū)間熬芜，那么答案顯然是
- 否則假設(shè)x同時(shí)落在m個(gè)區(qū)間中，答案是
做一點(diǎn)點(diǎn)數(shù)學(xué)上的變換：令
注意到在第一種情況下m=0福稳，所以我們就成功歸約到只有一種情況涎拉。對(duì)區(qū)間的左右端點(diǎn)離散化，用兩個(gè)樹狀數(shù)組分別維護(hù) 的前綴和和m以后的圆，我們就能夠
地判斷一個(gè)解是否可行曼库。總復(fù)雜度
略板，M是因?yàn)槿≈捣秶?e9
#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;
}
}
