有若干个区间，C(m)表示所有包含m这个点的区间编号排序后的序列。 求本质不同的非空字典序第k小的序列。
先离散化，因为本质不同不会超过2n个序列。 接下来顺序扫，并维护每个位置的hash值。 遇到之前出现过的hash值就叉掉。 然后接下来枚举按字典序枚举，每次看看往字典序末尾加入i会有多少种可能。 对于k,如果它不在答案序列中，不能选择它区间所包含的m。 对于k，如果它在答案序列中，只能选择它区间所包含的m。 所以需要线段树。 还要注意每次要检查当前答案序列后面能不能不放东西了，这个也可以线段树。
#include<cstdio> #include<algorithm> #include<map> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; const int maxn=100000+10,inf=10000000,mo1=1000000007,mo2=998244353; typedef long long ll; typedef pair<int,int> pi; pi zlt; map<pi,bool> s; int father[maxn],tree[maxn][2],mic[maxn][2],ha[maxn][2],size[maxn]; int h[maxn*2],go[maxn*2],nxt[maxn*2],fx[maxn*2]; int sum[maxn*8],mi[maxn*8],ad[maxn*8]; bool bz[maxn*8]; int a[maxn],b[maxn],d[maxn*2],ans[maxn]; int i,j,k,l,r,t,n,m,tot,top,cnt,root; bool czy; int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x; } void add(int x,int y,int z){ go[++cnt]=y; fx[cnt]=z; nxt[cnt]=h[x]; h[x]=cnt; } void build(int p,int l,int r){ if (l==r){ sum[p]=1; return; } int mid=(l+r)/2; build(p*2,l,mid);build(p*2+1,mid+1,r); sum[p]=sum[p*2]+sum[p*2+1]; } void markcl(int p){ bz[p]=1; sum[p]=0; mi[p]=inf; } void markad(int p,int v){ ad[p]+=v; mi[p]+=v; } void down(int p){ if (bz[p]){ markcl(p*2); markcl(p*2+1); bz[p]=0; } if (ad[p]){ markad(p*2,ad[p]); markad(p*2+1,ad[p]); ad[p]=0; } } void change(int p,int l,int r,int a,int b){ if (a>b) return; if (l==a&&r==b){ markcl(p); return; } down(p); int mid=(l+r)/2; if (b<=mid) change(p*2,l,mid,a,b); else if (a>mid) change(p*2+1,mid+1,r,a,b); else change(p*2,l,mid,a,mid),change(p*2+1,mid+1,r,mid+1,b); sum[p]=sum[p*2]+sum[p*2+1]; } int query(int p,int l,int r,int a,int b){ if (l==a&&r==b) return sum[p]; down(p); int mid=(l+r)/2; if (b<=mid) return query(p*2,l,mid,a,b); else if (a>mid) return query(p*2+1,mid+1,r,a,b); else return query(p*2,l,mid,a,mid)+query(p*2+1,mid+1,r,mid+1,b); } void change2(int p,int l,int r,int a,int b,int v){ if (l==a&&r==b){ markad(p,v); return; } down(p); int mid=(l+r)/2; if (b<=mid) change2(p*2,l,mid,a,b,v); else if (a>mid) change2(p*2+1,mid+1,r,a,b,v); else change2(p*2,l,mid,a,mid,v),change2(p*2+1,mid+1,r,mid+1,b,v); mi[p]=min(mi[p*2],mi[p*2+1]); } int pd(int x){ return tree[father[x]][1]==x; } void update(int x){ size[x]=size[tree[x][0]]+size[tree[x][1]]+1; int t=((ll)ha[tree[x][0]][0]*(n+1)%mo1+x)%mo1; t=((ll)t*mic[size[tree[x][1]]][0]%mo1+ha[tree[x][1]][0])%mo1; ha[x][0]=t; t=((ll)ha[tree[x][0]][1]*(n+1)%mo2+x)%mo2; t=((ll)t*mic[size[tree[x][1]]][1]%mo2+ha[tree[x][1]][1])%mo2; ha[x][1]=t; } void rotate(int x){ int y=father[x],z=pd(x); father[x]=father[y]; if (father[y]) tree[father[y]][pd(y)]=x; tree[y][z]=tree[x][1-z]; if (tree[x][1-z]) father[tree[x][1-z]]=y; tree[x][1-z]=y; father[y]=x; update(y); update(x); } void splay(int x,int y){ while (father[x]!=y){ if (father[father[x]]!=y) if (pd(x)==pd(father[x])) rotate(father[x]);else rotate(x); rotate(x); } } void insert(int &x,int y){ if (!x){ x=y; update(x); return; } if (y<x){ insert(tree[x][0],y); father[tree[x][0]]=x; } else{ insert(tree[x][1],y); father[tree[x][1]]=x; } update(x); } int merge(int a,int b){ if (!a||!b) return a+b; while (tree[a][1]) a=tree[a][1]; splay(a,0); tree[a][1]=b; father[b]=a; update(a); return a; } int main(){ freopen("list.in","r",stdin);freopen("list.out","w",stdout); n=read();m=read(); fo(i,1,n) d[++top]=a[i]=read(),d[++top]=b[i]=read(); sort(d+1,d+top+1); top=unique(d+1,d+top+1)-d-1; fo(i,1,n){ a[i]=lower_bound(d+1,d+top+1,a[i])-d; a[i]++; b[i]=lower_bound(d+1,d+top+1,b[i])-d; change2(1,1,top,a[i],b[i],1); } //change2(1,1,top,1,1,inf); build(1,1,top); fo(i,1,n){ add(a[i],i,1); add(b[i]+1,i,-1); } mic[0][0]=mic[0][1]=1; fo(i,1,n){ mic[i][0]=(ll)mic[i-1][0]*(n+1)%mo1; mic[i][1]=(ll)mic[i-1][1]*(n+1)%mo2; } fo(i,1,top){ t=h[i]; while (t){ if (fx[t]==-1){ splay(go[t],0); father[tree[go[t]][0]]=father[tree[go[t]][1]]=0; root=merge(tree[go[t]][0],tree[go[t]][1]); } t=nxt[t]; } t=h[i]; while (t){ if (fx[t]==1){ insert(root,go[t]); splay(go[t],0); root=go[t]; } t=nxt[t]; } if (!root) change(1,1,top,i,i); else{ zlt=make_pair(ha[root][0],ha[root][1]); if (s[zlt]){ change(1,1,top,i,i); }else s[zlt]=1; } } fo(i,1,n){ t=query(1,1,top,a[i],b[i]); if (t<m){ m-=t; change(1,1,top,a[i],b[i]); change2(1,1,top,a[i],b[i],-1); } else{ ans[++tot]=i; change(1,1,top,1,a[i]-1); change(1,1,top,b[i]+1,top); change2(1,1,top,a[i],b[i],-1); if (mi[1]==0) m--; if (m==0) break; } } printf("%d\n",tot); fo(i,1,tot) printf("%d ",ans[i]); printf("\n"); fclose(stdin);fclose(stdout); return 0; }