[BOJ1168] 조세퍼스 문제2

N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다.

합을 저장하는 세그먼트트리를 구현한 후   합을 출력하는 squery 와  해당번쨰를 가리키는 값을 출력하는 query 를 구현한다.

환형임을 생각해야하므로  %modi  를 해주며 제거할 때 마다 인원수가 감소하므로 modi-- 를 해준다.

따라서 해당 위치를 제거해가며  res 배열에 답을 담아 출력한다.

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
int n, m;
const int MAX_N = 100020;
int seg[MAX_N * 4];
 
int update(int pos, int val, int node, int x, int y) {
    if (pos < x || y < pos)    return seg[node];
    if (x == y) return seg[node] = val;
    int mid = (x + y) >> 1;
    update(pos, val, node*2, x, mid);
    update(pos, val, node * 2+1, mid + 1, y);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
 
int query(int val, int node, int x, int y) {
    if (x == y)    return x;
    int mid = (x + y) >> 1;
    if (val <= seg[node * 2])
        return query(val, node * 2, x, mid);
    else
        return query(val - seg[node*2], node*2+1, mid + 1, y);
}
int squery(int lo, int hi, int node, int x, int y) {
    if (hi < x || y < lo)    return 0;
    if (lo <= x && y <= hi)    return seg[node];
    int mid = (x + y) >> 1;
    return squery(lo, hi, node * 2, x, mid) + squery(lo, hi, node * 2 + 1, mid + 1, y);
}
vector<int> res;
int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &m);
    res.push_back(m);
    int modi = n-1;
    for (int i = 1; i <= n; i++) {
        update(i, 1, 1, 1, n);
    }
    update(res.back(), 0, 1, 1, n);
    for (int i = 0; i < n-1; i++) {
        int x = (squery(1,res.back(),1,1,n) + m) % modi;
        if (!x) x = modi;
        res.push_back(query(x, 1, 1, n));
        update(res.back(), 0, 1, 1, n);
        modi--;
    }
    printf("<");
    for (int i = 0; i < n; i++)
    {
        
        if (i == n - 1)
            printf("%d>\n",res[i]);
        else
        printf("%d, ", res[i]);
    }
    
 
}