当前位置 博文首页 > ttoobne:2019牛客暑期多校训练营(第七场)E Find the median

    ttoobne:2019牛客暑期多校训练营(第七场)E Find the median

    作者:[db:作者] 时间:2021-08-30 10:34

    题目链接

    题解:

    由于区间范围较大,考虑离线将区间离散化,那么可以利用线段树存左闭右开区间,每次更新时为两个操作:将 L?~ R - 1 区间更新,将 R 单点更新。

    代码:

    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f3f3f3f3f
    #define P pair<int, int>
    #define fastio ios::sync_with_stdio(false), cin.tie(0)
    const int mod = 998244353;
    const int M = 1000000 + 10;
    const int N = 800000 + 10;
     
    int n;
    int x[N], y[N], a[3], b[3], c[3], m[3];
    int cp[N], cnt, tot;
    int num[N<<2], add[N<<2], tim[N<<2];
     
    void push(int l, int r, int rt)
    {
        if(add[rt]) {
            int mid = (l + r) >> 1;
            num[rt << 1] += add[rt] * (cp[mid + 1] - cp[l]);
            num[rt << 1 | 1] += add[rt] * (cp[r + 1] - cp[mid + 1]);
            add[rt << 1] += add[rt];
            add[rt << 1 | 1] += add[rt];
            tim[rt << 1] += add[rt];
            tim[rt << 1 | 1] += add[rt];
            add[rt] = 0;
        }
    }
     
    void update(int L, int R, int l = 1, int r = cnt, int rt = 1)
    {
        if(L <= l && r <= R) {
            num[rt] += cp[r + 1] - cp[l];
            add[rt] ++;
            tim[rt] ++;
            return ;
        }
     
        push(l, r, rt);
        int mid = (l + r) >> 1;
        if(L <= mid) update(L, R, l, mid, rt << 1);
        if(mid < R) update(L, R, mid + 1, r, rt << 1 | 1);
     
        num[rt] = num[rt << 1] + num[rt << 1 | 1];
    }
     
    void single(int pos, int l = 1, int r = cnt, int rt = 1)
    {
        if(l == r) {
            num[rt] ++;
            return ;
        }
     
        push(l, r, rt);
        int mid = (l + r) >> 1;
        if(pos <= mid) single(pos, l, mid, rt << 1);
        else single(pos, mid + 1, r, rt << 1 | 1);
     
        num[rt] = num[rt << 1] + num[rt << 1 | 1];
    }
     
    int query(int val, int l = 1, int r = cnt, int rt = 1)
    {
        if(l == r) {
            int len = cp[r + 1] - cp[l];
            if(num[rt] - (tim[rt] * (len - 1)) >= val) return cp[l];
            val -= num[rt] - (tim[rt] * (len - 1));
            return cp[l] + val / tim[rt] + (val % tim[rt] ? 1 : 0);
        }
     
        push(l, r, rt);
        int mid = (l + r) >> 1;
        if(num[rt << 1] >= val) return query(val, l, mid, rt << 1);
        return query(val - num[rt << 1], mid + 1, r, rt << 1 | 1);
    }
     
    int l[N], r[N];
     
    signed main()
    {
        scanf("%lld", &n);
        scanf("%lld %lld %lld %lld %lld %lld", &x[1], &x[2], &a[1], &b[1], &c[1], &m[1]);
        scanf("%lld %lld %lld %lld %lld %lld", &y[1], &y[2], &a[2], &b[2], &c[2], &m[2]);
        for(int i = 1; i <= n; i ++) {
            if(i >= 3) {
                x[i] = (a[1] * x[i - 1] + b[1] * x[i - 2] + c[1]) % m[1];
                y[i] = (a[2] * y[i - 1] + b[2] * y[i - 2] + c[2]) % m[2];
            }
            l[i] = min(x[i], y[i]) + 1;
            r[i] = max(x[i], y[i]) + 1;
            cp[i] = l[i], cp[i + n] = r[i];
        }
     
        sort(cp + 1, cp + 1 + n + n);
        cnt = unique(cp + 1, cp + 1 + n + n) - cp - 1;
     
        for(int i = 1; i <= n; i ++) {
            tot += r[i] - l[i] + 1;
            l[i] = lower_bound(cp + 1, cp + 1 + cnt, l[i]) - cp;
            r[i] = lower_bound(cp + 1, cp + 1 + cnt, r[i]) - cp;
            if(l[i] != r[i]) update(l[i], r[i] - 1);
            single(r[i]);
            printf("%lld\n", query((tot + 1) / 2));
        }
     
        return 0;
    }
     
    /*
     
      Rejoicing in hope, patient in tribulation.
     
    */

    经队友指点可以更加简单的方法更新,每次更新前直接将区间右端点 R 加上 1,那么直接一次操作更新区间 L ~ R - 1 即可。

    代码:

    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f3f3f3f3f
    #define P pair<int, int>
    #define fastio ios::sync_with_stdio(false), cin.tie(0)
    const int mod = 998244353;
    const int M = 1000000 + 10;
    const int N = 800000 + 10;
     
    int n;
    int x[N], y[N], a[3], b[3], c[3], m[3];
    int cp[N], cnt, tot;
    int num[N<<2], add[N<<2];
     
    void push(int l, int r, int rt)
    {
        if(add[rt]) {
            int mid = (l + r) >> 1;
            num[rt << 1] += add[rt] * (cp[mid + 1] - cp[l]);
            num[rt << 1 | 1] += add[rt] * (cp[r + 1] - cp[mid + 1]);
            add[rt << 1] += add[rt];
            add[rt << 1 | 1] += add[rt];
            add[rt] = 0;
        }
    }
     
    void update(int L, int R, int l = 1, int r = cnt, int rt = 1)
    {
        if(L <= l && r <= R) {
            num[rt] += cp[r + 1] - cp[l];
            add[rt] ++;
            return ;
        }
     
        push(l, r, rt);
        int mid = (l + r) >> 1;
        if(L <= mid) update(L, R, l, mid, rt << 1);
        if(mid < R) update(L, R, mid + 1, r, rt << 1 | 1);
     
        num[rt] = num[rt << 1] + num[rt << 1 | 1];
    }
     
    int query(int val, int l = 1, int r = cnt, int rt = 1)
    {
        if(l == r) {
            int len = cp[r + 1] - cp[l], temp;
            temp = num[rt] / len;
            return cp[l] - 1 + val / temp + (val % temp ? 1 : 0);
        }
     
        push(l, r, rt);
        int mid = (l + r) >> 1;
        if(num[rt << 1] >= val) return query(val, l, mid, rt << 1);
        return query(val - num[rt << 1], mid + 1, r, rt << 1 | 1);
    }
     
    int l[N], r[N];
     
    signed main()
    {
        scanf("%lld", &n);
        scanf("%lld %lld %lld %lld %lld %lld", &x[1], &x[2], &a[1], &b[1], &c[1], &m[1]);
        scanf("%lld %lld %lld %lld %lld %lld", &y[1], &y[2], &a[2], &b[2], &c[2], &m[2]);
        for(int i = 1; i <= n; i ++) {
            if(i >= 3) {
                x[i] = (a[1] * x[i - 1] + b[1] * x[i - 2] + c[1]) % m[1];
                y[i] = (a[2] * y[i - 1] + b[2] * y[i - 2] + c[2]) % m[2];
            }
            l[i] = min(x[i], y[i]) + 1;
            r[i] = max(x[i], y[i]) + 2;
            cp[i] = l[i], cp[i + n] = r[i];
        }
     
        sort(cp + 1, cp + 1 + n + n);
        cnt = unique(cp + 1, cp + 1 + n + n) - cp - 1;
     
        for(int i = 1; i <= n; i ++) {
            tot += r[i] - l[i];
            l[i] = lower_bound(cp + 1, cp + 1 + cnt, l[i]) - cp;
            r[i] = lower_bound(cp + 1, cp + 1 + cnt, r[i]) - cp;
            update(l[i], r[i] - 1);
            printf("%lld\n", query((tot + 1) / 2));
        }
     
        return 0;
    }
     
    /*
     
      Rejoicing in hope, patient in tribulation.
     
    */

    ?

    cs