Joseph问题（线段树）

Joseph问题似乎是入门题，就是那个报数出圈的问题，不过它暴力模拟的复杂度是O（nm）的，如果题目的数据范围达到了30000，那就超时了。怎么用线段树维护呢？

我们可以这么考虑，每次我们其实要查询在当前这个点过了m个人是哪一个人。我们需要维护一下当前序列中一共有多少人，还需要维护每个人实际的位置在哪（因为人们出圈了之后他就不占位置了）

我们可以用一棵权值线段树来完成。

首先是修改，这个没什么好说的，直接单点修改改成0就行，然后同时返回修改的位置，这是一个人出圈的位置。不过怎么找到这个位置呢？我们可以首先确定下来这个人在当前序列的第几位，那么我们直接在线段树上二分就可以了，然后返回那个位置。

一开始我们要query一下从1到上一次停留位置有几个人，然后把这个值+m-1，mod现在所有的人数再+1就是当前位置，找一下那个人在哪就可以了。

看一下代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<queue>

#include<set>

#define lowbit(x) x & (-x)

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = ;

const ll INF = ;

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

        if(ch == '-') op = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

        ans *= ;

        ans += ch - '';

        ch = getchar();

    }

    return ans * op;

}

struct seg

{

    int v;

} t[M<<];

int n,m,last,g;

void build(int p,int l,int r)

{

    if(l == r)

    {

        t[p].v = ;

        return;

    }

    int mid = (l+r) >> ;

    build(p<<,l,mid),build(p<<|,mid+,r);

    t[p].v = t[p<<].v + t[p<<|].v;

}

int query(int p,int l,int r,int pos)

{

    if(l == r) return t[p].v = ,l;

    int mid = (l+r) >> ,cur;

    if(pos <= t[p<<].v) cur = query(p<<,l,mid,pos);

    else cur = query(p<<|,mid+,r,pos-t[p<<].v);

    t[p].v = t[p<<].v + t[p<<|].v;

    return cur;

}

int count(int p,int l,int r,int kl,int kr)

{

    if(kl > kr) return ;

    if(l == kl && r == kr) return t[p].v;

    int mid = (l+r) >> ;

    if(kr <= mid) return count(p<<,l,mid,kl,kr);

    else if(kl > mid) return count(p<<|,mid+,r,kl,kr);

    else return count(p<<,l,mid,kl,mid) + count(p<<|,mid+,r,mid+,kr);

}

int main()

{

    n = read(),m = read();

    build(,,n);

    rep(i,,n) printf("%d ",last = query(,,n,(count(,,n,,last)+m-)%t[].v+));

    return ;

}

巴特西

Joseph问题（线段树）

最新文章

热门文章

巴特西

Joseph问题 （线段树）

最新文章

热门文章

Joseph问题（线段树）