题目概述

有 $n$ 条线段 $(a_i,b_i)$ ，定义 $C(i)$ 表示包含 $i+{1\over 2}$ 的有序线段列表，求字典序第 $K$ 小的 $C(i)$（相同列表不重复计算）。

解题报告

我菜死了，这都不会做……显然不同的列表最多 $2n$ 个，那么就有暴力想法，通过扫描线构造出每个列表，直接sort。

怎么优化呢？我们发现可以用哈希快速比较两个列表，这样sort就可以做到 $O(nlog_2^2n)$ 。然而构造还是 $O(n^2)$ 的。为了解决构造 $O(n^2)$ 的问题，我们用主席树维护哈希值，然后sort的时候在主席树上二分就好了。

$4\times10^5$ 跑两个 $log$ 疯狂TLE……可以把sort换成set（我不知道为什么set就是比sort快QAQ），然后讨论 $K$ 是否超过总列表个数 $num$ 的一半，如果超过那么我们就求第 $num-K+1$ 大，这样可以强行减小一倍常数。

示例程序

#include<set>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef unsigned long long ULL;
const int maxn=200000,maxm=maxn<<1,maxt=1e7,BA=998244353;

int n,K,m,tem[maxm+5],ID[maxm+5];pair<int,int> s[maxm+5];ULL pw[maxn+5];
int len,ro[maxm+5],ls[maxt+5],rs[maxt+5];ULL sum[maxt+5];int ans[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline int Find(int x,int L=1,int R=tem[0]){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        if (x==tem[mid]) return mid; else x<tem[mid]?R=mid-1:L=mid+1;return -1;
}
inline int absi(int x) {return x<0?-x:x;}
int Insert(int p,int pos,int k,int l=1,int r=n){
    int now=++len;ls[now]=ls[p];rs[now]=rs[p];
    if (l==r) {sum[now]=sum[p]+k;return now;}int mid=l+(r-l>>1);
    if (pos<=mid) ls[now]=Insert(ls[p],pos,k,l,mid); else rs[now]=Insert(rs[p],pos,k,mid+1,r);
    sum[now]=sum[ls[now]]+pw[mid-l+1]*sum[rs[now]];return now;
}
bool Ask(int A,int B,int l=1,int r=n,bool F=0,bool G=0){
    if (l==r) return sum[A]?G:!F;int mid=l+(r-l>>1);
    if (sum[ls[A]]==sum[ls[B]]) return Ask(rs[A],rs[B],mid+1,r,F,G);
    return Ask(ls[A],ls[B],l,mid,F||sum[rs[A]],G||sum[rs[B]]);
}
inline bool cmp(const int &a,const int &b){
    if (!sum[ro[a]]&&!sum[ro[b]]) return a<b;if (!sum[ro[a]]||!sum[ro[b]]) return !sum[ro[b]];
    if (sum[ro[a]]==sum[ro[b]]) return false;return Ask(ro[a],ro[b]);
}
struct List{
    int x;inline List(int X) {x=X;}
    inline bool operator < (const List &a) const {return cmp(x,a.x);}
};set<List> S;
void Dfs(int p,int l=1,int r=n){
    if (l==r) {if (sum[p]) ans[++ans[0]]=l;return;}int mid=l+(r-l>>1);
    if (sum[ls[p]]) Dfs(ls[p],l,mid);if (sum[rs[p]]) Dfs(rs[p],mid+1,r);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(readi(n),readi(K),1),x,y;i<=n;i++)
        readi(x),tem[++m]=x,s[m]=mp(x,i),readi(y),tem[++m]=y,s[m]=mp(y,-i);
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=pw[i-1]*BA;
    sort(tem+1,tem+1+m);tem[0]=unique(tem+1,tem+1+m)-tem-1;
    sort(s+1,s+1+m);for (int i=1;i<=m;i++) s[i].fr=Find(s[i].fr);
    for (int i=1,j=1;i<=tem[0];i++)
        for (ro[i]=ro[i-1];j<=m&&s[j].fr==i;j++) ro[i]=Insert(ro[i],absi(s[j].sc),s[j].sc);
    for (int i=1;i<=tem[0];i++) S.insert(List(i));int tp=(K>S.size()/2);if (tp) K=S.size()-K+1;
    if (tp){
        for (set<List>::iterator it=S.end();it!=S.begin();)
            if (it--,--K==0){
                Dfs(ro[(*it).x]);printf("%d\n",ans[0]);
                for (int i=1;i<=ans[0];i++) printf("%d%c",ans[i],i<ans[0]?' ':'\n');break;
            }
    } else{
        for (set<List>::iterator it=S.begin();it!=S.end();it++)
            if (--K==0){
                Dfs(ro[(*it).x]);printf("%d\n",ans[0]);
                for (int i=1;i<=ans[0];i++) printf("%d%c",ans[i],i<ans[0]?' ':'\n');break;
            }
    }return 0;
}