Game 7 of 2019 Niuke multi school training camp E - find the media - Discrete + tree array + dichotomy (tree array is a big treasure)

Original title site
First of all, this blog does not introduce discretization, binary search.
Want to see the solution of line tree Poke here
I don't mean to write two blogs with one title on purpose, maliciously improving my reading. First of all, I think the mathematical requirements of these two solutions are not high, but the ideas are different (well, most of them are the same). In fact, the main reason is that I didn't expect that I would write them again with tree array at first, and the method I began to understand was a little scary. There is a saying that I don't want to read all of them, because it is a line tree without brain (there is no special mathematical idea, besides the necessary processing of the problem data, the other is the normal processing of the written problems, why should I empty my mind to do the tree array). Later, I found that a blog introduced a very ingenious method (not line tree fast), I thought it had to be recorded. There's this blog.
It has to be mentioned that all the intervals are left closed and right open, in order to prevent the interval conflict after discretization.
First, analyze the key operations of the code.
Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 8e5+5;
const int INF = 1e9;
int N;
int X1,X2,Y1,Y2,A1,A2,B1,B2,C1,C2,M1,M2;
int L[maxn],R[maxn],disc[maxn<<1];
ll b1[maxn],b2[maxn],cnt = 0;
int lowbit(int x){
    return x&-x;
}

void Updata(ll a[],int pos,int value){
    while(pos <= cnt){
        a[pos] += value;
        pos += lowbit(pos);
    }
}
ll Query(ll a[],int x){
    ll ans = 0;
    while(x){
        ans += a[x];
        x -= lowbit(x);
    }
    return ans;
}
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);
	 L[1] = min(X1,Y1) + 1;
	 R[1] = max(X1,Y1) + 1;
	 L[2] = min(X2,Y2) + 1;
	 R[2] = max(X2,Y2) + 1;
	 ll x,y;
	 for(int i = 3;i <= N;i++){
		x = ((1ll*A1 * X2 % M1 + 1ll * B1 * X1 %M1)%M1 + C1)%M1;
		y = ((1ll*A2 * Y2 % M2 + 1ll * B2 * Y1 %M2)%M2 + C2)%M2;
		X1 = X2;X2 = x;
		Y1 = Y2;Y2 = y;
		L[i] = min(x,y) + 1;
		R[i] = max(x,y) + 1;
	}
		for(int i = 1;i <= N;i++){
		disc[++cnt] = L[i];
		disc[++cnt] = R[i] + 1;
	//	printf("%d %d\n",L[i],R[i]);
	}
	memset(b1,0,sizeof(b1));
	memset(b2,0,sizeof(b2));
	sort(disc + 1,disc + 1 + cnt);
	 cnt = unique(disc + 1,disc + 1 + cnt) - disc - 1;
	ll All = 0;
	for(int i = 1;i <= N;i++){
		int l,r;
		All += R[i] - L[i] + 1;
		l = lower_bound(disc + 1,disc + cnt + 1,L[i]) - disc;
		r = lower_bound(disc + 1,disc + cnt + 1,R[i] + 1) - disc; 
        Updata(b1,l,-L[i]);
        Updata(b1,r,R[i]+1);
        Updata(b2,l,1);
        Updata(b2,r,-1);
        int left = 1,right = INF;
        ll pd = (All + 1)/2;
        while(left < right){
            int mid = (left + right)>>1;
            int pos = upper_bound(disc + 1,disc + cnt + 1,mid) - disc - 1;
            ll tmp = Query(b1,pos) + Query(b2,pos)*(mid + 1);
            if(tmp < pd) left = mid + 1;
            else right = mid;
        }
        printf("%d\n",left);
	}
	
	return 0;
}

Key operations:

        Updata(b1,l,-L[i]);
        Updata(b1,r,R[i]+1);
        Updata(b2,l,1);
        Updata(b2,r,-1);
        &
        ll tmp = Query(b1,pos) + Query(b2,pos)*(mid + 1);

The key operation is to update the two tree arrays & the expression of interval sum.
We can see the first two updates (update of the first tree array)
Updata(b1,l, − L[i])Updata(b1,l,-L[i])Updata(b1,l, − L[i]) and Updata(b1,r,R[i]+1)Updata(b1,r,R[i]+1)Updata(b1,r,R[i]+1)
We know that the tree array sums the intervals.
We can know that if the complete interval is in the current interval, then the contribution of these two updated points to the interval sum is R[i] - L[i]+1R[i] - L[i] + 1R[i] - L[i]+1, perfect, which is exactly what we want. Code can be represented by Query(b1,pos)Query(b1,pos)Query(b1,pos)

If the complete interval is not in it, then the right endpoint must be missing.
Updata(b2,l,1)Updata(b2,l,1)Updata(b2,l,1) and Updata(b2,r, − 1)Updata(b2,r,-1)Updata(b2,r, − 1)
It solves the problem of endpoint missing perfectly.
We can also see from the code that if the interval is complete, the interval sum of b2 is 0. On the contrary, the interval sum represents several intervals without right endpoint. Obviously, the right endpoint should be added to make the actual interval sum complete. The right endpoint we want to add is the right endpoint of the interval we are currently querying. At this time, Query(b1,pos)+Query(b2,pos) * (mid+1) Query(b1,pos)+Query(b2,pos) * (mid+1) Query(b1,pos)+Query(b2,pos) * (mid+1) solves this problem very well.
At the same time, he also perfectly matches the previous questions.

At this time, everything is so reasonable and natural.

Added by devangel on Thu, 24 Oct 2019 16:57:35 +0300