2019牛客暑期多校训练营（第七场）E-Find the median（思维+树状数组+离散化+二分）...

╰半橙微兮° 2021-10-29 12:48 179阅读 0赞

[>传送门<][Link 1]

**题意：**给n个操作，每次![L\_i][L_i]和![R\_i][R_i] （1e9范围内）即往数组里面插所有![x \\in \[L\_i,R\_i\]][x _in _L_i_R_i] 的所有数，求每次操作后的中位数  
**思路：**区间离散化然后二分答案，因为小于中位数的数字恰好有![tot/2][tot_2]个，这显然具有单调性。那么问题就转化为如何求小于等于某个数x的数一共有多少个。

考虑以下两种情况：假设左端点小于等于**x**的区间一共有**q**个

*  如果x不落在任何一个区间，那么答案显然是![\\sum\_\{i=1\}^q (R\_i-L\_i+1)][sum_i_1_q _R_i-L_i_1]
 *  否则假设x同时落在m个区间中，答案是![\\sum\_\{i=1\}^\{q-m\}(R\_i-L\_i+1)+\\sum\_\{i=q-m+1\}^q (x+1-L\_i)][sum_i_1_q-m_R_i-L_i_1_sum_i_q-m_1_q _x_1-L_i]

做一点点数学上的变换：令![N\_i=R\_i+1][N_i_R_i_1]

*  ![1610347-20190811183717655-298306087.png][]
 *  ![\\sum\_\{i=1\}^\{q-m\}(R\_i-L\_i+1)+\\sum\_\{i=q-m+1\}^q (x+1-L\_i)=\\sum\_\{N\_i\\le x\}N\_i-\\sum\_\{L\_i\\le x\}L\_i+m(x+1)][sum_i_1_q-m_R_i-L_i_1_sum_i_q-m_1_q _x_1-L_i_sum_N_i_le x_N_i-_sum_L_i_le x_L_i_m_x_1]

注意到在第一种情况下**m=0**，所以我们就成功归约到只有一种情况。对区间的左右端点离散化，用两个树状数组分别维护![N\_i,L\_i][N_i_L_i] 的前缀和和m以后，我们就能够![O(\\log N)][O_log N]地判断一个解是否可行。总复杂度![O(N\\log N\\log M)][O_N_log N_log M] ，M是因为取值范围是1e9

**Code**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn = 400010;
    
    ll n, cnt, tot;
    ll x[maxn], y[maxn], l[maxn], r[maxn];
    int a1, b1, c1, a2, b2, c2, m1, m2;
    ll z[maxn<<1], bit1[maxn<<1], bit2[maxn<<1];
     
    void add(ll a[], int i, int x) {
        while (i<=cnt) {
            a[i] += x;
            i += i&(-i);
        }
    }
    ll query(ll a[], int i){
        ll res = 0;
        while (i>0) {
            res += a[i];
            i -= i&(-i);
        }
        return res;
    }
    void read() {
        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;
    } 
    
    int main()
    {
        read();
        for(int i = 1; i <= n; i++) {
            tot += r[i]-l[i]+1;
            int L=lower_bound(z+1,z+cnt+1,l[i])-z, 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);
            //二分查找
            int left = 1, right = 1e9;
            while(left<right) {
                int mid = (left+right)/2;
                int q = upper_bound(z+1,z+cnt,mid)-z-1;
                ll tmp = query(bit1, q)+query(bit2, q)*(mid+1);
                if(tmp<(tot+1)/2) left = mid+1;
                else right = mid;
            }
            cout<<left<<endl;
        }
        return 0;
    }

*有的地方没用long long 就WA了，在蕊芬学姐的指导下改过来了~*

转载于:https://www.cnblogs.com/wizarderror/p/11335953.html

[Link 1]: https://ac.nowcoder.com/acm/contest/887/E
[L_i]: https://math.jianshu.com/math?formula=L_i
[R_i]: https://math.jianshu.com/math?formula=R_i
[x _in _L_i_R_i]: https://math.jianshu.com/math?formula=x%20%5Cin%20%5BL_i%2CR_i%5D
[tot_2]: https://math.jianshu.com/math?formula=tot%2F2
[sum_i_1_q _R_i-L_i_1]: https://math.jianshu.com/math?formula=%5Csum_%7Bi%3D1%7D%5Eq%20%28R_i-L_i%2B1%29
[sum_i_1_q-m_R_i-L_i_1_sum_i_q-m_1_q _x_1-L_i]: https://math.jianshu.com/math?formula=%5Csum_%7Bi%3D1%7D%5E%7Bq-m%7D%28R_i-L_i%2B1%29%2B%5Csum_%7Bi%3Dq-m%2B1%7D%5Eq%20%28x%2B1-L_i%29
[N_i_R_i_1]: https://math.jianshu.com/math?formula=N_i%3DR_i%2B1
[1610347-20190811183717655-298306087.png]: /images/20211029/049d4d77ce69496784301073dbe47118.png
[sum_i_1_q-m_R_i-L_i_1_sum_i_q-m_1_q _x_1-L_i_sum_N_i_le x_N_i-_sum_L_i_le x_L_i_m_x_1]: https://math.jianshu.com/math?formula=%5Csum_%7Bi%3D1%7D%5E%7Bq-m%7D%28R_i-L_i%2B1%29%2B%5Csum_%7Bi%3Dq-m%2B1%7D%5Eq%20%28x%2B1-L_i%29%3D%5Csum_%7BN_i%5Cle%20x%7DN_i-%5Csum_%7BL_i%5Cle%20x%7DL_i%2Bm%28x%2B1%29
[N_i_L_i]: https://math.jianshu.com/math?formula=N_i%2CL_i
[O_log N]: https://math.jianshu.com/math?formula=O%28%5Clog%20N%29
[O_N_log N_log M]: https://math.jianshu.com/math?formula=O%28N%5Clog%20N%5Clog%20M%29
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/b411505ff746468995c4c0accd64bc0d.png