- 技术
- Vases and Flowers HDU - 4614（线段树+二分）
思路：用线段树去更新和修改花瓶内的花，sum=1表示没花，0表示有花，lazy标记同意义，当执行1操作时，首先对给出的区间头x，查询x-n之间有多少空瓶子，如果空瓶子的个数不为0那么说明我们可以插花，此时我们用二分去判断符合条件的区间下标，对于左区间我们只需要找到可以插1个花的位置，对于右区间我们去找插完所有花的位置。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e4+7;
const int N
=2e5+10;
const int inf
=0x7f7f7f7f;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
struct node
{
int l
,r
,sum
,lazy
;
}tr
[N
<<2];
int n
;
void push_up(int root
)
{
tr
[root
].sum
=tr
[lson
].sum
+tr
[rson
].sum
;
}
void push_down(int root
)
{
if(tr
[root
].lazy
!=-1)
{
tr
[lson
].lazy
=tr
[root
].lazy
;
tr
[rson
].lazy
=tr
[root
].lazy
;
int mid
=tr
[root
].l
+tr
[root
].r
>>1;
tr
[lson
].sum
=(mid
-tr
[root
].l
+1)*tr
[root
].lazy
;
tr
[rson
].sum
=(tr
[root
].r
-mid
)*tr
[root
].lazy
;
tr
[root
].lazy
=-1;
}
}
void build(int root
,int l
,int r
)
{
tr
[root
].l
=l
;
tr
[root
].r
=r
;
tr
[root
].lazy
=-1;
if(l
==r
)
{
tr
[root
].sum
=1;return ;
}
int mid
=l
+r
>>1;
build(lson
,l
,mid
);
build(rson
,mid
+1,r
);
push_up(root
);
}
void update(int root
,int l
,int r
,int x
)
{
if(l
<=tr
[root
].l
&&r
>=tr
[root
].r
)
{
tr
[root
].sum
=(tr
[root
].r
-tr
[root
].l
+1)*x
;
tr
[root
].lazy
=x
;return ;
}
int mid
=tr
[root
].l
+tr
[root
].r
>>1;
push_down(root
);
if(mid
>=l
)update(lson
,l
,r
,x
);
if(mid
<r
)update(rson
,l
,r
,x
);
push_up(root
);
}
int query(int root
,int l
,int r
)
{
if(l
<=tr
[root
].l
&&tr
[root
].r
<=r
) return tr
[root
].sum
;
int mid
=tr
[root
].l
+tr
[root
].r
>>1;
push_down(root
);
int res
=0;
if(l
<=mid
)res
+=query(lson
,l
,r
);
if(r
>mid
)res
+=query(rson
,l
,r
);
push_up(root
);
return res
;
}
int bserach(int x
,int num
)
{
int l
=x
,r
=n
;
int mid
,ans
=0;
while(l
<=r
)
{
mid
=l
+r
>>1;
if(query(1,x
,mid
)>=num
){
r
=mid
-1;ans
=mid
;
}else l
=mid
+1;
}
return ans
;
}
int main()
{
SIS
;
int t
;
cin
>>t
;
while(t
--)
{
int m
;
cin
>>n
>>m
;
build(1,1,n
);
while(m
--)
{
int op
,x
,y
;
cin
>>op
>>x
>>y
;
if(op
==1)
{
x
++;
int cnt
=query(1,x
,n
);
if(cnt
==0)
cout
<<"Can not put any one."<<endl
;
else
{
int L
=bserach(x
,1);
int R
=bserach(x
,min(cnt
,y
));
update(1,L
,R
,0);
cout
<<L
-1<<' '<<R
-1<<endl
;
}
}else
{
x
++,y
++;
int ans
=query(1,x
,y
);
ans
=y
-x
-ans
+1;
cout
<<ans
<<endl
;
update(1,x
,y
,1);
}
}
cout
<<endl
;
}
return 0;
}
Processed:
0.013, SQL:
9
