题目链接

题意

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

思路

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

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

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

代码

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> 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"=["<<x<<"]" <<endl

#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)

#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;

const int mod = 1000000007;

const int maxn = 800000 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n, tot, x, y, xx, yy, m1, m2, a1, a2, b1, b2, c1, c2;

int L[maxn], R[maxn], num[maxn*2], lazy[maxn*4];

LL sum[maxn*4];

void push_up(int rt) {

    sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void push_down(int rt, int l, int r) {

    if(!lazy[rt]) return;

    int x = lazy[rt];

    lazy[rt] = 0;

    int mid = (l + r) >> 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;

}

巴特西

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

题目链接

题意

思路

代码

最新文章

热门文章