1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int A[maxn];
struct dian
{
int l,r;
int d;
int lazy;
}sum[maxn<<2];
void pushup(int rt)
{
sum[rt].d=max(sum[rt<<1].d,sum[rt<<1|1].d);
}
void build(int l,int r,int rt)
{
sum[rt].l=l;
sum[rt].r=r;
sum[rt].d=0;
sum[rt].lazy = 0;
if(l!=r)
{
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
}
void xiachuan(int rt)
{
sum[rt<<1].lazy+=sum[rt].lazy;
sum[rt<<1|1].lazy+=sum[rt].lazy;
sum[rt<<1].d+=sum[rt].lazy;
sum[rt<<1|1].d+=sum[rt].lazy;
sum[rt].lazy=0;
}
void cha(int l,int r,int rt)
{
if(sum[rt].l==l&&sum[rt].r==r)
{
sum[rt].d++;
sum[rt].lazy++;
return;
}
if(sum[rt].lazy)
xiachuan(rt);
int mid=(sum[rt].l+sum[rt].r)>>1;
if(r<=mid)
cha(l,r,rt<<1);
else if(l>mid)
cha(l,r,rt<<1|1);
else
{
cha(l,mid,rt<<1);
cha(mid+1,r,rt<<1|1);
}
pushup(rt);
}
int query(int l,int r,int rt)
{
if(sum[rt].l==l&&sum[rt].r==r)
return sum[rt].d;
if(sum[rt].lazy)
xiachuan(rt);
int mid=(sum[rt].r+sum[rt].l)>>1;
if(r<=mid)
return query(l,r,rt<<1);
else if(l>mid)
return query(l,r,rt<<1|1);
else
return max(query(l,mid,rt<<1),query(mid+1,r,rt<<1|1));
}
int main()
{
int k,m;
int a,b;
memset(A,0,sizeof(A));
scanf("%d%d",&k,&m);
build(1,1000000,1);
int id=0;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
b--;
if(query(a,b,1)<k)
{
A[id++]=i+1;
cha(a,b,1);
}
}
for(int i=0;i<id;i++)
printf("%d ",A[i]);
return 0;
}
|
