思路:我们考虑如果取掉一个部分，那么能影响到最优解的只有离它最近的那两个部分。
因此我们考虑堆维护最小的部分，离散化离散掉区间，然后用线段树维护区间有没有雪，最后用平衡树在线段的左右端点上面维护最小的id
我讲的貌似不是很清楚。。
还有，蜜汁80分，打死也改不出来。。
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
struct node{
int l,r,cnt,id;
}a[];
struct segment{
int l,r,v;
segment(){}
segment(int l0,int r0,int v0):l(l0),r(r0),v(v0){}
}t[];
struct treap{
int l,r,rnd,v;
}tt[];
int tag[],vis[],Tcase;
int len[],next[],before[],pos[],heap[];
int o[],p[],sz,Id[],pls[];
int c[],Cnt,sb,rt1[],rt2[],all[];
int tot,n,Len;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
bool cmp(node a,node b){
return a.r-a.l<b.r-b.l;
}
void push_up(int x){
while (x>){
if (len[x/]>len[x]||(len[x/]==len[x]&&heap[x/]>heap[x])) std::swap(len[x/],len[x]),std::swap(heap[x/],heap[x]),std::swap(pos[heap[x]],pos[heap[x/]]);
else break;
x/=;
}
}
void push_down(int x){
int j;
while (x*<=tot){
if (x*==tot) j=*x;
else if (len[*x]<len[*x+]||(len[*x]==len[*x+]&&heap[*x]<heap[*x+])) j=*x;
else j=*x+;
if (len[x]>len[j]||(len[x]==len[j]&&heap[j]<heap[x])){
std::swap(len[x],len[j]);
std::swap(heap[x],heap[j]);
std::swap(pos[heap[x]],pos[heap[j]]);
}
x=j;
}
}
void add_heap(int x,int v){
heap[++tot]=x;
len[tot]=v;
pos[x]=tot;
push_up(tot);
}
void delete_heap(int x){
int Pos=pos[x];
heap[Pos]=heap[tot];
len[Pos]=len[tot];
pos[heap[tot]]=Pos;
tot--;
push_down(Pos);
}
void modify_heap(int x,int y){
int Pos=pos[x];
len[Pos]=y;
push_up(Pos);
}
void build(int k,int l,int r){
if (l==r){
t[k].v=o[l];
t[k].l=t[k].r=l;
return;
}
int mid=(l+r)>>;
build(k*,l,mid);
build(k*+,mid+,r);
t[k].v=t[k*].v+t[k*+].v;
t[k].l=std::min(t[k*].l,t[k*+].l);
t[k].r=std::max(t[k*].r,t[k*+].r);
}
void pushdown(int k,int l,int r){
if (!tag[k]||l==r) return;
tag[k]=;
t[k*].v=t[k*+].v=;
tag[k*]=tag[k*+]=;
t[k*].l=t[k*+].l=Len+;
t[k*].r=t[k*+].r=;
}
void modify(int k,int l,int r,int x,int y){
if (l>r) return;
if (l>y||r<x) return;
pushdown(k,l,r);
if (l==x&&r==y){
tag[k]=;
t[k].l=Len+;
t[k].r=;
t[k].v=;
pushdown(k,l,r);
return;
}
int mid=(l+r)>>;
if (y<=mid) modify(k*,l,mid,x,y);
else
if (x>mid) modify(k*+,mid+,r,x,y);
else modify(k*,l,mid,x,mid),modify(k*+,mid+,r,mid+,y);
t[k].v=t[k*].v+t[k*+].v;
t[k].l=std::min(t[k*].l,t[k*+].l);
t[k].r=std::max(t[k*].r,t[k*+].r);
}
segment query(int k,int l,int r,int x,int y){
if (x>y) return segment(x,y,);
pushdown(k,l,r);
if (l==x&&r==y){
return segment(t[k].l,t[k].r,t[k].v);
}
int mid=(l+r)>>;
if (y<=mid) return query(k*,l,mid,x,y);
else
if (x>mid) return query(k*+,mid+,r,x,y);
else{
segment t1=query(k*,l,mid,x,mid);
segment t2=query(k*+,mid+,r,mid+,y);
return segment(std::min(t1.l,t2.l),std::max(t1.r,t2.r),t1.v+t2.v);
}
}
int find(int x){
int l=,r=p[];
while (l<=r){
int mid=(l+r)>>;
if (p[mid]==x) return Id[mid];
if (p[mid]<x) l=mid+;
else r=mid-;
}
}
void sbpianfen1(){
int T=n;
for (int i=;i<=n;i++)
a[i].l=read(),a[i].r=read(),a[i].id=i,a[i].cnt=a[i].r-a[i].l+,add_heap(i,a[i].r-a[i].l+),p[++p[]]=a[i].l,p[++p[]]=a[i].r;
std::sort(p+,p++p[]);int j=;
for (int i=;i<=p[];i++)
if (p[i]!=p[j]) p[++j]=p[i];p[]=j; for (int i=;i<=p[];i++)
if (p[i]!=p[i-]){
o[++sz]=p[i]-p[i-]-;
o[++sz]=;
Id[i]=sz;
}
Len=sz;
for (int i=;i<=n;i++)
a[i].l=find(a[i].l),a[i].r=find(a[i].r);
build(,,Len);
a[n+].cnt=0x7fffffff;
while (T--){
int mn=n+;
for (int i=n;i>=;i--)
if (a[i].cnt<=a[mn].cnt&&!vis[i]) mn=i;
printf("%d\n",mn);vis[mn]=;
modify(,,Len,a[mn].l,a[mn].r);
for (int i=;i<=n;i++){
segment t1=query(,,Len,a[i].l,a[i].r);
a[i].cnt=t1.v;
}
}
}
void lturn(int &k){
if (!k) return;
int TT=tt[k].r;tt[k].r=tt[TT].l;tt[TT].l=k;k=TT;
}
void rturn(int &k){
if (!k) return;
int TT=tt[k].l;tt[k].l=tt[TT].r;tt[TT].r=k;k=TT;
}
void insert(int &k,int v){
if (!k){
if (Cnt) k=c[Cnt--];else k=++sb;
tt[k].l=tt[k].r=;tt[k].rnd=rand();
tt[k].v=v;
all[v]++;
return;
}
if (tt[k].v==v) {all[v]++;return;}
if (tt[k].v<v){
insert(tt[k].r,v);
if (tt[tt[k].r].rnd<tt[k].rnd) lturn(k);
}else{
insert(tt[k].l,v);
if (tt[tt[k].l].rnd<tt[k].rnd) rturn(k);
}
}
void del(int &k,int v){
if (!k) return;
if (tt[k].v==v){
if (tt[k].l*tt[k].r==){
c[++Cnt]=k;
k=tt[k].l+tt[k].r;
all[v]--;
return;
}
if (tt[tt[k].l].rnd<tt[tt[k].r].rnd){
rturn(k);
del(k,v);
}else{
lturn(k);
del(k,v);
}
return;
}
if (tt[k].v<v) del(tt[k].r,v);
else del(tt[k].l,v);
}
int find_treap(int k){
while (tt[k].l!=) k=tt[k].l;
return tt[k].v;
}
bool findit(int k,int x){
if (!k) return ;
if (tt[k].v==x) return ;
else if (tt[k].v<x) return findit(tt[k].r,x);
else return findit(tt[k].l,x);
}
void Gwork(){
Tcase=Tcase;
}
void updata(int x,int id){
if (id==) x=pls[find_treap(rt1[a[x].l])];
else if (id==) x=pls[find_treap(rt2[a[x].r])];
if (a[x].l>a[x].r) return;
segment t1=query(,,Len,a[x].l,a[x].r);
a[x].cnt=t1.v;
if (a[x].id==&&(a[x].l==||a[x].r==)) Gwork();
del(rt1[a[x].l],a[x].id);
del(rt2[a[x].r],a[x].id);
a[x].l=t1.l;
a[x].r=t1.r;
insert(rt1[a[x].l],a[x].id);
insert(rt2[a[x].r],a[x].id);
modify_heap(a[x].id,a[x].cnt);
}
void sbpianfen3(){
for (int i=;i<=n;i++)
a[i].l=read(),a[i].r=read(),a[i].cnt=a[i].r-a[i].l+,a[i].id=i,add_heap(i,a[i].r-a[i].l+),p[++p[]]=a[i].l,p[++p[]]=a[i].r;
std::sort(p+,p++p[]);int j=;
for (int i=;i<=p[];i++)
if (p[i]!=p[j]) p[++j]=p[i];p[]=j;
for (int i=;i<=p[];i++)
if (p[i]!=p[i-]){
o[++sz]=p[i]-p[i-]-;
o[++sz]=;
Id[i]=sz;
}
Len=sz;
for (int i=;i<=n;i++)
a[i].l=find(a[i].l),a[i].r=find(a[i].r),insert(rt1[a[i].l],i),insert(rt2[a[i].r],i);
for (int i=;i<=n;i++)
pls[a[i].id]=i;
for (int i=;i<=n;i++) before[i]=i-;
for (int i=;i<n;i++) next[i]=i+;
int T=n;
build(,,Len);
while (T--){
Tcase++;
int x=heap[];printf("%d\n",x);
delete_heap(x);
if (a[x].l>a[x].r){
int t1=before[pls[x]],t2=next[pls[x]];
next[t1]=t2;
before[t2]=t1;
continue;
}
if (Tcase==) Gwork();
modify(,,Len,a[pls[x]].l,a[pls[x]].r);
if (before[pls[x]]) updata(before[pls[x]],);
if (next[pls[x]]) updata(next[pls[x]],);
int t1=before[pls[x]],t2=next[pls[x]];
next[t1]=t2;
before[t2]=t1;
}
}
int main(){
Len=read();n=read();
if (n<=) {sbpianfen1();fclose(stdin);fclose(stdout);return ;}
sbpianfen3();
fclose(stdin);fclose(stdout);
return ;
}