Find the median(2019年牛客多校第七场E题+左闭右开线段树)

题目链接

传送门

题意

每次往集合里面添加一段连续区间的数，然后询问当前集合内的中位数。

思路

思路很好想，但是卡内存。

当时写的动态开点线段树没卡过去，赛后机房大佬用动态开点过了，\(tql\)。

卡不过去就只能离散化加左闭右开线段树写了。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson (rt<<1),L,mid
#define rson (rt<<1|1),mid + 1,R
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    lazy[rt<<1] += x, lazy[rt<<1|1] += x;
    sum[rt<<1] += 1LL * x * (num[mid+1]-num[l]);
    sum[rt<<1|1] += 1LL * x * (num[r+1]-num[mid+1]);
}

void update(int l, int r, int rt, int L, int R) {
    if(l <= L && R <= r) {
        sum[rt] += num[R+1] - num[L];
        ++lazy[rt];
        return;
    }
    push_down(rt, L, R);
    int mid = (L + R) >> 1;
    if(r <= mid) update(l, r, lson);
    else if(l > mid) update(l, r, rson);
    else {
        update(l, mid, lson);
        update(mid + 1, r, rson);
    }
    push_up(rt);
}

int query(LL all, int rt, int L, int R) {
    if(L == R) {
        LL pos = sum[rt] / (num[R+1] - num[L]);
        pos = num[L] + (all - 1) / pos;
        return pos;
    }
    push_down(rt, L, R);
    int mid = (L + R) >> 1;
    if(sum[rt<<1] >= all) return query(all, lson);
    else return query(all - sum[rt<<1], rson);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%d", &n);
    scanf("%d%d%d%d%d%d", &x, &xx, &a1, &b1, &c1, &m1);
    scanf("%d%d%d%d%d%d", &y, &yy, &a2, &b2, &c2, &m2);
    L[1] = min(x, y) + 1, R[1] = max(x, y) + 1;
    L[2] = min(xx, yy) + 1, R[2] = max(xx, yy) + 1;
    num[++tot] = L[1], num[++tot] = R[1] + 1;
    num[++tot] = L[2], num[++tot] = R[2] + 1;
    for(int i = 3; i <= n; ++i) {
        int num1 = ((1LL * a1 * xx % m1 + 1LL * b1 * x % m1) % m1 + c1) % m1;
        int num2 = ((1LL * a2 * yy % m2 + 1LL * b2 * y % m2) % m2 + c2) % m2;
        L[i] = min(num1, num2) + 1, R[i] = max(num1, num2) + 1;
        x = xx, xx = num1;
        y = yy, yy = num2;
        num[++tot] = L[i], num[++tot] = R[i] + 1;
    }
    sort(num + 1, num + tot + 1);
    tot = unique(num + 1, num + tot + 1) - num - 1;
    LL all = 0;
    for(int i = 1; i <= n; ++i) {
        all += R[i] - L[i] + 1;
        L[i] = lower_bound(num + 1, num + tot + 1, L[i]) - num;
        R[i] = lower_bound(num + 1, num + tot + 1, R[i] + 1) - num;
        update(L[i], R[i]-1, 1, 1, tot);
        printf("%d\n", query((all + 1) /2, 1, 1, tot));
    }
    return 0;
}
迷之线段树比赛题解感想

相关

标签