题目大意
给定数轴上
n
个形如(ai,bi)的开区间，令
C(m)
表示所有包含实数
m+0.5
的区间编号排序而成的列表。 一个列表，如果存在一个
m
使得它能够表示成C(m)，那么它就是合法的。 给定
K
，你需要输出字典序第K大的非空合法列表。
1≤n≤105,0≤ai<bi≤109
，给定的
K
保证有解。
题目分析
注意到本质不同的合法的非空列表只有O(n)个，考虑将它们全部列出来然后使用nth_element找到第
K
大。
那么我们要解决两个问题：如何储存这么多列表？如何快速比较两个列表的字典序大小？
只需要可持久化线段树就能解决上面的问题。我们开一棵可持久化权值线段树，然后扫描线，每次遇到边界就在对应位置插入删除，然后储存一个新列表只需要储存对应的版本的根节点。可是这样有可能会有一些本质相同的被储存。因此我们需要对这个列表哈希来判重，这个可以使用线段树来维护。
至于比较大小，我们可以利用线段树上的哈希值来快速找到两个列表第一个不同的位置，然后瞎判断一下就好了。
时间复杂度O(nlogn)。
代码实现
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <map>
using namespace std;
int read()
{
int x=
0,f=
1;
char ch=getchar();
while (!
isdigit(ch)) f=ch==
'-'?-
1:f,ch=getchar();
while (
isdigit(ch)) x=x*
10+ch-
'0',ch=getchar();
return x*f;
}
int buf[
30];
void write(
int x)
{
if (x<
0)
putchar(
'-'),x=-x;
for (;x;x/=
10) buf[++buf[
0]]=x%
10;
if (!buf[
0]) buf[++buf[
0]]=
0;
for (;buf[
0];
putchar(
'0'+buf[buf[
0]--]));
}
const int MOD=
998244353;
const int P1=
67;
const int P2=
23;
const int N=
100050;
const int M=N<<
1;
const int LGN=
17;
const int S=M*LGN;
typedef pair<
int,
int> P;
#define mkp(a,b) make_pair(a,b)
#define ft first
#define sd second
P
operator+(P x,P y){
return mkp((x.ft+y.ft)%MOD,(x.sd+y.sd)%MOD);}
P
operator-(P x,P y){
return mkp((x.ft-y.ft+MOD)%MOD,(x.sd-y.sd+MOD)%MOD);}
P
operator*(P x,P y){
return mkp(
1ll*x.ft*y.ft%MOD,
1ll*x.sd*y.sd%MOD);}
map<P,bool> exist;
P POW[N];
struct data
{
int x,id;
bool tp;
data (
int x_=
0,
int id_=
0,
bool tp_=
0){x=x_,id=id_,tp=tp_;}
bool operator<(data
const d)
const{
return x<d.x;}
}srt[M];
int n,m,cnt,idx,K;
bool fir;
struct segment_tree
{
int son[S][
2];
int size[S];
P hash[S];
int tot;
void update(
int x){hash[x]=hash[son[x][
0]]+hash[son[x][
1]];}
void insert(
int &rt,
int rt0,
int x,
int l,
int r)
{
size[rt=++tot]=size[rt0]+
1,son[rt][
0]=son[rt0][
0],son[rt][
1]=son[rt0][
1];
if (l==r)
{
hash[rt]=POW[l];
return;
}
int mid=l+r>>
1;
if (x<=mid) insert(son[rt][
0],son[rt0][
0],x,l,mid);
else insert(son[rt][
1],son[rt0][
1],x,mid+
1,r);
update(rt);
}
void erase(
int &rt,
int rt0,
int x,
int l,
int r)
{
if (size[rt0]==
1)
{
rt=
0;
return;
}
size[rt=++tot]=size[rt0]-
1,son[rt][
0]=son[rt0][
0],son[rt][
1]=son[rt0][
1];
int mid=l+r>>
1;
if (x<=mid) erase(son[rt][
0],son[rt0][
0],x,l,mid);
else erase(son[rt][
1],son[rt0][
1],x,mid+
1,r);
update(rt);
}
bool cmp(
int rt1,
int rem1,
int rt2,
int rem2)
{
if (!rem2||hash[rt1]==hash[rt2])
return 0;
if (!rem1)
return 1;
if (!rt1)
return 0;
if (!rt2)
return 1;
if (hash[son[rt1][
0]]==hash[son[rt2][
0]])
return cmp(son[rt1][
1],rem1-size[son[rt1][
0]],son[rt2][
1],rem2-size[son[rt2][
0]]);
else return cmp(son[rt1][
0],rem1,son[rt2][
0],rem2);
}
void display(
int rt,
int l,
int r)
{
if (!rt)
return;
if (l==r)
{
if (!fir)
putchar(
' ');
write(l),fir=
0;
return;
}
int mid=l+r>>
1;
display(son[rt][
0],l,mid),display(son[rt][
1],mid+
1,r);
}
}t;
struct sequence
{
int rt,total;
sequence (
int rt_=
0,
int total_=
0){rt=rt_,total=total_;}
bool operator<(sequence
const s)
const{
return t.cmp(rt,t.size[rt],s.rt,t.size[s.rt]);}
}seq[M];
void solve()
{
sort(srt+
1,srt+
1+m),cnt=
0;
int ptr=
1,root=
0,rt;
for (;ptr<=m;)
{
if (ptr-
1&&!exist[t.hash[root]]&&t.size[root]) seq[++cnt]=sequence(root,srt[ptr].x-srt[ptr-
1].x),exist[t.hash[root]]=
1;
for (
int cur=ptr;ptr<=m&&srt[cur].x==srt[ptr].x;root=rt,++ptr)
if (srt[ptr].tp) t.erase(rt,root,srt[ptr].id,
1,n);
else t.insert(rt,root,srt[ptr].id,
1,n);
}
nth_element(seq+
1,seq+K,seq+
1+cnt);
write(t.size[seq[K].rt]),
putchar(
'\n'),fir=
1,t.display(seq[K].rt,
1,n),
putchar(
'\n');
}
int main()
{
freopen(
"list.in",
"r",stdin),freopen(
"list.out",
"w",stdout);
n=read(),K=read(),m=
0;
POW[
0]=mkp(
1,
1);
for (
int i=
1,l,r;i<=n;++i) l=read(),r=read(),srt[++m]=data(l,i,
0),srt[++m]=data(r,i,
1),POW[i]=POW[i-
1]*mkp(P1,P2);
solve();
fclose(stdin),fclose(stdout);
return 0;
}
