思路:我们考虑如果取掉一个部分，那么能影响到最优解的只有离它最近的那两个部分。

因此我们考虑堆维护最小的部分，离散化离散掉区间，然后用线段树维护区间有没有雪，最后用平衡树在线段的左右端点上面维护最小的id

我讲的貌似不是很清楚。。

还有，蜜汁80分，打死也改不出来。。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 struct node{  7     int l,r,cnt,id;  8 }a[1200005];  9 struct segment{ 10     int l,r,v;  11     segment(){} 12     segment(int l0,int r0,int v0):l(l0),r(r0),v(v0){} 13 }t[5000005]; 14 struct treap{ 15     int l,r,rnd,v; 16 }tt[5000005]; 17 int tag[5000005],vis[1000005],Tcase; 18 int len[1000005],next[1500005],before[1500005],pos[1000005],heap[1000005]; 19 int o[1500005],p[1000005],sz,Id[1000005],pls[1500005]; 20 int c[2500005],Cnt,sb,rt1[1500005],rt2[1500005],all[500006]; 21 int tot,n,Len; 22 int read(){ 23     int t=0,f=1;char ch=getchar(); 24     while (ch<'0'||ch>'9'){
   if (ch=='-') f=-1;ch=getchar();} 25     while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 26     return t*f; 27 } 28 bool cmp(node a,node b){ 29     return a.r-a.l
          
           1){ 33 if (len[x/2]>len[x]||(len[x/2]==len[x]&&heap[x/2]>heap[x])) std::swap(len[x/2],len[x]),std::swap(heap[x/2],heap[x]),std::swap(pos[heap[x]],pos[heap[x/2]]); 34 else break; 35 x/=2; 36 } 37 } 38 void push_down(int x){ 39 int j; 40 while (x*2<=tot){ 41 if (x*2==tot) j=2*x; 42 else if (len[2*x]
           
            
             len[j]||(len[x]==len[j]&&heap[j]
             
              >1; 78 build(k*2,l,mid); 79 build(k*2+1,mid+1,r); 80 t[k].v=t[k*2].v+t[k*2+1].v; 81 t[k].l=std::min(t[k*2].l,t[k*2+1].l); 82 t[k].r=std::max(t[k*2].r,t[k*2+1].r); 83 } 84 void pushdown(int k,int l,int r){ 85 if (!tag[k]||l==r) return; 86 tag[k]=0; 87 t[k*2].v=t[k*2+1].v=0; 88 tag[k*2]=tag[k*2+1]=1; 89 t[k*2].l=t[k*2+1].l=Len+1; 90 t[k*2].r=t[k*2+1].r=0; 91 } 92 void modify(int k,int l,int r,int x,int y){ 93 if (l>r) return; 94 if (l>y||r
              
               >1;105 if (y<=mid) modify(k*2,l,mid,x,y);106 else107 if (x>mid) modify(k*2+1,mid+1,r,x,y);108 else modify(k*2,l,mid,x,mid),modify(k*2+1,mid+1,r,mid+1,y);109 t[k].v=t[k*2].v+t[k*2+1].v;110 t[k].l=std::min(t[k*2].l,t[k*2+1].l);111 t[k].r=std::max(t[k*2].r,t[k*2+1].r);112 }113 segment query(int k,int l,int r,int x,int y){114 if (x>y) return segment(x,y,0);115 pushdown(k,l,r);116 if (l==x&&r==y){117 return segment(t[k].l,t[k].r,t[k].v);118 }119 int mid=(l+r)>>1;120 if (y<=mid) return query(k*2,l,mid,x,y);121 else122 if (x>mid) return query(k*2+1,mid+1,r,x,y);123 else{124 segment t1=query(k*2,l,mid,x,mid);125 segment t2=query(k*2+1,mid+1,r,mid+1,y);126 return segment(std::min(t1.l,t2.l),std::max(t1.r,t2.r),t1.v+t2.v);127 }128 }129 int find(int x){130 int l=1,r=p[0];131 while (l<=r){132 int mid=(l+r)>>1;133 if (p[mid]==x) return Id[mid];134 if (p[mid]
               
                =1;i--)160 if (a[i].cnt<=a[mn].cnt&&!vis[i]) mn=i;161 printf("%d\n",mn);vis[mn]=1;162 modify(1,1,Len,a[mn].l,a[mn].r);163 for (int i=1;i<=n;i++){164 segment t1=query(1,1,Len,a[i].l,a[i].r); 165 a[i].cnt=t1.v;166 }167 }168 }169 void lturn(int &k){170 if (!k) return;171 int TT=tt[k].r;tt[k].r=tt[TT].l;tt[TT].l=k;k=TT;172 }173 void rturn(int &k){174 if (!k) return;175 int TT=tt[k].l;tt[k].l=tt[TT].r;tt[TT].r=k;k=TT;176 }177 void insert(int &k,int v){178 if (!k){179 if (Cnt) k=c[Cnt--];else k=++sb;180 tt[k].l=tt[k].r=0;tt[k].rnd=rand();181 tt[k].v=v;182 all[v]++;183 return;184 }185 if (tt[k].v==v) {all[v]++;return;}186 if (tt[k].v
                
                 a[x].r) return;232 segment t1=query(1,1,Len,a[x].l,a[x].r);233 a[x].cnt=t1.v;234 if (a[x].id==51612&&(a[x].l==206449||a[x].r==206449)) Gwork();235 del(rt1[a[x].l],a[x].id);236 del(rt2[a[x].r],a[x].id);237 a[x].l=t1.l;238 a[x].r=t1.r;239 insert(rt1[a[x].l],a[x].id);240 insert(rt2[a[x].r],a[x].id);241 modify_heap(a[x].id,a[x].cnt);242 }243 void sbpianfen3(){244 for (int i=1;i<=n;i++) 245 a[i].l=read(),a[i].r=read(),a[i].cnt=a[i].r-a[i].l+1,a[i].id=i,add_heap(i,a[i].r-a[i].l+1),p[++p[0]]=a[i].l,p[++p[0]]=a[i].r;246 std::sort(p+1,p+1+p[0]);int j=1;247 for (int i=2;i<=p[0];i++)248 if (p[i]!=p[j]) p[++j]=p[i];p[0]=j;249 for (int i=1;i<=p[0];i++) 250 if (p[i]!=p[i-1]){251 o[++sz]=p[i]-p[i-1]-1;252 o[++sz]=1;253 Id[i]=sz;254 }255 Len=sz; 256 for (int i=1;i<=n;i++)257 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); 258 for (int i=1;i<=n;i++) 259 pls[a[i].id]=i;260 for (int i=2;i<=n;i++) before[i]=i-1;261 for (int i=1;i
                 
                  a[x].r){269 int t1=before[pls[x]],t2=next[pls[x]];270 next[t1]=t2;271 before[t2]=t1;272 continue;273 }274 if (Tcase==2872) Gwork();275 modify(1,1,Len,a[pls[x]].l,a[pls[x]].r);276 if (before[pls[x]]) updata(before[pls[x]],1);277 if (next[pls[x]]) updata(next[pls[x]],2);278 int t1=before[pls[x]],t2=next[pls[x]];279 next[t1]=t2;280 before[t2]=t1;281 }282 }283 int main(){284 Len=read();n=read();285 if (n<=1000) {sbpianfen1();fclose(stdin);fclose(stdout);return 0;}286 sbpianfen3();287 fclose(stdin);fclose(stdout);288 return 0;289 }