记录编号	301799	评测结果	AAAAAAAAAA
题目名称	2121.[2016轻工业学院ACM]蛤玮打扫教室	最终得分	100
用户昵称	沉迷学习的假的Keller	是否通过	通过
代码语言	C++	运行时间	0.382 s
提交时间	2016-09-02 14:56:24	内存使用	5.74 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=300000+10;
struct node{
    int l,r;  
}a[maxn];
int v[maxn],w[maxn],ans[maxn],sum[maxn];
int n,m,s;
int main(){
	freopen("HWsweepclassroom.in","r",stdin);
	freopen("HWsweepclassroom.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i].l,&a[i].r);
		v[a[i].l]++;    //左端点加一 
		v[a[i].r+1]--;  //右端点后面减一 
	}
	for(int i=0;i<=n;i++){  
        s+=v[i];  
        w[i]=s;   //w[i]表示每个点的覆盖次数 
    }
    for(int i=0;i<=n;i++){
        if(w[i]>1)  //覆盖次数大于1的时候  
            sum[i]=sum[i-1]+1;    //sum数组代表包括i之前所有覆盖次数大于1的数量 
        else  
            sum[i]=sum[i-1];  
    }
    int num=1;
    for(int i=1;i<=m;i++){
        if(sum[a[i].r]-sum[a[i].l-1]==a[i].r-a[i].l+1)  //利用差分思想sum[a[i].r]-sum[a[i].l-1] 为区间内覆盖次数大于1的数量 
            ans[num++]=i;                              //如果 区间内覆盖次数大于1的数量等于区间长度 则可以选 
    }
    printf("%d\n",num-1);  
    for(int i=1;i<num;i++){ 
        printf("%d ",ans[i]);
    }
	return 0;
}