生活随笔
收集整理的这篇文章主要介绍了
HDU - 6992 Lawn of the Dead 线段树 + 思维
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
传送门
文章目录
题意：
给你一张n∗mn*mn∗m的图，其中有kkk个点不能走，你只能向下和向右走，问你能到达多少点。
n,m,k≤1e5n,m,k\le1e5n,m,k≤1e5
思路：
可以发现每个点如果其左边和上面都有障碍，那么这个点不可达。考虑到障碍数量比较少，所以肯定是枚举障碍的数量，现在就变成怎么快速统计答案了。
我们按照每一列来考虑，下面是样例的图，其中三角形代表障碍。
对于每个位置(x,y)(x,y)(x,y)，我们查询其它上面障碍出现的位置(如果之前没有障碍我们定义为000)之后到(x−1,y−1)(x-1,y-1)(x−1,y−1)的位置中第一次空位置，即能走的位置，将这个位置到当前位置之前都赋值为111，代表这些点可达。
下图中问号即为询问的区间，箭头指向(x−1,y−1)(x-1,y-1)(x−1,y−1)。
区间查询以及区间覆盖的操作显然可以用线段树来实现，再加点边界限制即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
,k
;
vector
<int>v
[N
];
struct Seg {struct Node{int l
,r
;int sum
;int lazy
;}tr
[N
<<2];void pushup(int u
) {tr
[u
].sum
=tr
[L
].sum
+tr
[R
].sum
;}void pushdown(int u
) {if(tr
[u
].lazy
!=-1) {int lazy
=tr
[u
].lazy
; tr
[u
].lazy
=-1; tr
[L
].sum
=Len(L
)*lazy
; tr
[L
].lazy
=lazy
;tr
[R
].sum
=Len(R
)*lazy
; tr
[R
].lazy
=lazy
;} }void build(int u
,int l
,int r
) {tr
[u
]={l
,r
,0,-1};if(l
==r
) return;build(L
,l
,Mid
); build(R
,Mid
+1,r
);}void modify(int u
,int l
,int r
,int x
) {if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) {tr
[u
].sum
=Len(u
)*x
;tr
[u
].lazy
=x
;return;}pushdown(u
);if(l
<=Mid
) modify(L
,l
,r
,x
);if(r
>Mid
) modify(R
,l
,r
,x
);pushup(u
); }int query(int u
,int l
,int r
) {if(tr
[u
].sum
==0) return INF
;if(tr
[u
].l
==tr
[u
].r
) return tr
[u
].l
;pushdown(u
);if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) {if(tr
[L
].sum
>0) return query(L
,l
,r
);else return query(R
,l
,r
);}int ans
=INF
;if(l
<=Mid
) ans
=min(ans
,query(L
,l
,r
));if(r
>Mid
) ans
=min(ans
,query(R
,l
,r
));return ans
;}}t
[2];int main()
{
int _
; scanf("%d",&_
);for(int __
=1;__
<=_
;__
++) {scanf("%d%d%d",&n
,&m
,&k
);for(int i
=1;i
<=m
;i
++) v
[i
].clear();for(int i
=1;i
<=k
;i
++) {int x
,y
; scanf("%d%d",&x
,&y
);v
[y
].pb(x
);} t
[0].build(1,1,n
); t
[1].build(1,1,n
);int now
=0; t
[now
].modify(1,1,1,1); now
^=1;LL ans
=0;for(int i
=1;i
<=m
;i
++) {sort(v
[i
].begin(),v
[i
].end());int l
=0;for(auto x
:v
[i
]) {if(l
+1<=x
-1) {int pos
=t
[now
^1].query(1,l
+1,x
-1);if(pos
!=INF
) t
[now
].modify(1,pos
,x
-1,1);}l
=x
;}if(l
+1<=n
) {int pos
=t
[now
^1].query(1,l
+1,n
);if(pos
!=INF
) t
[now
].modify(1,pos
,n
,1);}ans
+=t
[now
].tr
[1].sum
;t
[now
^1].modify(1,1,n
,0);now
^=1;}printf("%lld\n",ans
);}return 0;
}
总结
以上是生活随笔为你收集整理的HDU - 6992 Lawn of the Dead 线段树 + 思维的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
