题解 BZOJ 1201 [HNOI2005]数三角形

首先看正着的三角形。
每个点向右上方可以扩展的距离叫 mxl[],左上方叫mxr[]。
枚举三角形右下端点。
设右下为j.坐下为i。
需要满足 底边i..j 联通,并且$j-i<=mxr[j]$且$j-i<=mxl[i]$。
把i挪到一边,把j挪到一边就是
$j-mxr[j]<=i$且$j<=mxl[i]+i$

就是一个二维数据结构问题。
可以一维排序一维树状数组或直接二维树状数组。
然后向下的三角形同理。

code:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int l[1005][1005],r[1005][1005],b[1005][1005];
int mxl[1005][1005],mxr[1005][1005];
long long ans;
int c[2005][2005];
#define lowbit(x) ((x)&-(x))
void add(int x,int y,int d){
for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) c[i][j]+=d;
}
int ask(int x,int y){
int ret=0;
if(x<=0) x=1;
if(y<=0) y=1;
for(int i=x;i<=2*n;i+=lowbit(i)){
for(int j=y;j<=2*n;j+=lowbit(j)){
ret+=c[i][j];
}
}
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d%d%d",&l[i][j],&r[i][j],&b[i][j]);
}
}
for(int i=1;i<=n+1;i++){
for(int j=1;j<=i;j++){
mxl[i][j]=l[i-1][j]?(mxl[i-1][j]+1):0;
mxr[i][j]=r[i-1][j-1]?(mxr[i-1][j-1]+1):0;
}
}
for(int i=2;i<=n+1;i++){
int last=1;
for(int j=1;j<=i;j++){
if(b[i-1][j-1]==0){
while(last<j){
add(last,last+mxl[i][last],-1);last++;
}
}
ans+=ask(j-mxr[i][j],j);
add(j,j+mxl[i][j],1);
}
while(last<=i) add(last,last+mxl[i][last],-1),last++;
}
memset(mxl,0,sizeof mxl);
memset(mxr,0,sizeof mxr);
for(int i=n;i>=1;i--){
for(int j=1;j<=i;j++){
mxl[i][j]=r[i][j]?(mxl[i+1][j+1]+1):0;
mxr[i][j]=l[i][j]?(mxr[i+1][j]+1):0;
}
}
for(int i=2;i<=n+1;i++){
int last=1;
for(int j=1;j<=i;j++){
if(b[i-1][j-1]==0){
while(last<j){
add(last,last+mxl[i][last],-1);last++;
}
}
ans+=ask(j-mxr[i][j],j);
add(j,j+mxl[i][j],1);
}
while(last<=i) add(last,last+mxl[i][last],-1),last++;
}
printf("%lld\n",ans);
return 0;
}

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框