2019 우 객 여름 다 교 훈련소 (7 차 전) E Governing sand [나무 모양 수조 + 이산 화] 【 2 점 】

제목:
여기 있 습 니 다.
x1, x2, y1, y2, a1, a2,  b1,  b2,  c1,  c2,  m1,  m2;
다음 x 와 y 를 유도 합 니 다.  
Xi = (a1 * Xi-1   + b1 * Xi-2 + c1) % m1
Yi = (a2 * Yi-1   + b2 * Yi-2 + c2) % m2
Ri = max(Xi, Yi)
Li = min(Xi, Yi)
n 차 조작   시퀀스 에 추가 (초기 비어 있 음)  Li ~ Ri   (Ri - Li + 1) 개수  현재 중위 수 를 얼마나 구 합 니까?  짝수 개
제목 링크:
https://ac.nowcoder.com/acm/contest/887/E
문제 풀이:
먼저 모든 L, R 을 이산 화 합 니 다.
두 개의 나무 모양 배열 을 짓다.
그리고 2 분 매 거 중위 수.
트 리 배열 과 앞 에 몇 개의 숫자 가 있 습 니까?
첫 번 째 bit 1 트 리 배열 의 요 구 는 틀 렸 을 것 입 니 다. 왜냐하면 앞 에 L 이 여러 개 있 으 면...  R 보다 많다
그러면 저희 가 R 을 뒤에 넣 어 줘 야 돼 요.
그래서 비트 2 는 앞 에 L 이 몇 개 있 는 지 기록 하고 있 습 니 다.
AC_code:

#include
using namespace std;
#define maxn 400010
#define ll long long
int n, x[maxn], y[maxn], l[maxn], r[maxn];
ll a1,a2, b1, b2, c1, c2, m1, m2;
int z[maxn<<1], cnt;
ll bit1[maxn], bit2[maxn];
int lowbit(int x) {
	return x&(-x);
}
void add(ll bit[], int p, int x) {
	for(int i = p; i <= cnt; i += lowbit(i)) {
		bit[i] += x;
	}
}
ll query(ll bit[], int p) {
	ll ans = 0;
	for(int i = p; i > 0; i -= lowbit(i)) {
		ans += bit[i];
	}
	return ans;
}
int main() {
	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 - 1;
	ll t = 0;
	for(int i = 1; i <= n; i++){
		t += r[i] - l[i] + 1;
		int L = lower_bound(z+1, z+cnt+1, l[i]) - z;
		int R = lower_bound(z+1, z+cnt+1, r[i]+1) - z;
		add(bit1, L, -l[i]);
		add(bit1, R, r[i]+1);
		add(bit2, L, 1);
		add(bit2, R, -1);
		L = 1, R = 1e9;
		while(L < R){
			int mid = (L + R) / 2;
			int pos = upper_bound(z+1, z+cnt+1, mid) -z - 1;
			ll tmp = query(bit1, pos) + query(bit2, pos) * (mid + 1);
			if(tmp < (t+1)/2){
				L = mid + 1;
			}else {
				R = mid;
			}
		}
		printf("%d
", L);
	}

	return 0;
}