#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node
{
int cnt;
int xmin;
int poz;
int lazy;
};
int n;
int cnt;
vector<int> v[100005];
int dp[100005];
int last[100005];
Node segtree[400005];
int INF = (1 << 30);
Node combine(Node left, Node right)
{
Node nou;
nou.lazy = 0;
if(left.cnt < right.cnt)
{
nou.cnt = left.cnt;
nou.xmin = left.xmin;
nou.poz = left.poz;
}
else if(left.cnt > right.cnt)
{
nou.cnt = right.cnt;
nou.xmin = right.xmin;
nou.poz = right.poz;
}
else
{
nou.cnt = left.cnt;
if(left.xmin <= right.xmin)
{
nou.xmin = left.xmin;
nou.poz = left.poz;
}
else
{
nou.xmin = right.xmin;
nou.poz = right.poz;
}
}
return nou;
}
void update_lazy(int node, int left, int right)
{
if(segtree[node].lazy != 0)
{
segtree[node].cnt += segtree[node].lazy;
if(left != right)
{
segtree[2*node].lazy += segtree[node].lazy;
segtree[2*node+1].lazy += segtree[node].lazy;
}
segtree[node].lazy = 0;
}
}
void update_point(int node, int left, int right, int poz)
{
update_lazy(node, left, right);
if(left == right)
{
segtree[node] = {0, dp[left - 1], left, 0}; //pun cnt = 0, pt ca dau update +1 pe tot prefixul 1..i
return;
}
int mij = (left + right) / 2;
if(poz <= mij)
{
update_point(2*node, left, mij, poz);
}
else
{
update_point(2*node+1, mij+1, right, poz);
}
update_lazy(2*node, left, mij);
update_lazy(2*node+1, mij+1, right);
segtree[node] = combine(segtree[2*node],
segtree[2*node+1]);
}
void update_range(int node, int left, int right, int qleft, int qright, int val)
{
update_lazy(node, left, right);
if(qright < left || right < qleft)
{
return;
}
if(qleft <= left && right <= qright)
{
segtree[node].lazy += val;
update_lazy(node, left, right);
return;
}
int mij = (left + right) / 2;
update_range(2*node, left, mij, qleft, qright, val);
update_range(2*node+1, mij+1, right, qleft, qright, val);
segtree[node] = combine(segtree[2*node],
segtree[2*node+1]);
}
Node query(int node, int left, int right, int qleft, int qright)
{
update_lazy(node, left, right);
if(qright < left || right < qleft)
{
return {INF, INF, INF, 0};
}
if(qleft <= left && right <= qright)
{
return segtree[node];
}
int mij = (left + right) / 2;
return combine(query(2*node, left, mij, qleft, qright),
query(2*node+1, mij+1, right, qleft, qright));
}
vector<int> partition_players(int N, int M, vector<int> X, vector<int> Y)
{
n = N;
for(int i = 0; i<M; i++)
{
X[i]++;
Y[i]++;
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
dp[0] = 0;
for(int i = 1; i<=n; i++)
{
dp[i] = INF;
update_point(1, 1, n, i);
update_range(1, 1, n, 1, i, +1);
for(auto it: v[i])
{
if(it < i)
{
update_range(1, 1, n, 1, it, -1);
}
}
Node qr = query(1, 1, n, 1, i);
if(qr.cnt != 1)
{
exit(1);
}
dp[i] = qr.xmin + 1;
last[i] = (i - qr.poz + 1);
}
vector<int> ans;
int cur = n;
while(cur != 0)
{
ans.push_back(last[cur]);
cur -= last[cur];
}
reverse(ans.begin(), ans.end());
return ans;
}
