BZOJ 2727:[HNOI 2012]ダブルクロスツリー配列
10779 ワード
トランスファゲート
タイトル:
R∗C R∗Cの01行列が与えられ、この01行列の中にどれだけの二重十字があるかを計算する必要がある.
二重十字は、2つの水平線と1つの垂直な「1」線分で構成され、以下の制限を満たす必要があります.
1.2つの水平の線分は隣接する2行にはできません.
2.垂直線分の上端は2本の水平線分より厳格に高く、下端は2本の水平線分より厳格に低くなければならない.
3.垂直線分は、2つの水平線分を厳密に等しい半分に分割する必要があります.
4.上の水平線分は、下の水平線分よりも厳密に短くなければならない.
二重十字の個数mod 1000000009の値を出力します.
R,C,N≤10000,R∗C≤1000000 R , C , N ≤ 10000 , R ∗ C ≤ 1000000
Solution:
lr[i]l r[i]はiから最大で左右にどれだけ伸びるかを表す
down[i]d o w n[i]はiから最大どれだけ下に伸びるかを表す
top[i]はiから最大でどれだけ伸びるかを表す
下端セグメントの中点jを列挙し,次に各上端セグメントの中点iに対して答えへの寄与を考慮する.
∑lr[j]len=1min(len−1,lr[i])∗top[i]∗down[j] ∑ l e n = 1 l r [ j ] m i n ( l e n − 1 , l r [ i ] ) ∗ t o p [ i ] ∗ d o w n [ j ]
minはうまく処理できないので、何とかして取り除きます.
ディスカッションの分類を試みます.
lr[i]≦lr[j]l r[i]≦l r[j]の場合、答えは(lr[i]∗lr[j]−lr[i](lr[i]+1)2)∗top[i]∗down[j](lr[i]∗lr[j]−l r[i](l r[i]+1)2)∗t o p[i]∗d o w n[j]
>lr[i]>lr[j]>l r[i]>l r[j]の場合、lr[j]∗(lr[j]−1)2∗top[i]−down[j]l r[j]∗(l r[j]−1)2∗t o p[i]∗d o w n[j]
各列の連続する非0区間については,iに関するものをすべて記録し,jと結合して計算するたびに
3つの値をツリー配列で維持します.
1. −lr[i]∗(lr[i]+1)2∗top[i] − l r [ i ] ∗ ( l r [ i ] + 1 ) 2 ∗ t o p [ i ]
2. lr[i]∗top[i] l r [ i ] ∗ t o p [ i ]
3. top[i] t o p [ i ]
RとCは不確定で配列が開かない可能性があるので,行列を1次元に圧縮した.
注意コードにはリアルタイム計算topコードが含まれています.
タイトル:
R∗C R∗Cの01行列が与えられ、この01行列の中にどれだけの二重十字があるかを計算する必要がある.
二重十字は、2つの水平線と1つの垂直な「1」線分で構成され、以下の制限を満たす必要があります.
1.2つの水平の線分は隣接する2行にはできません.
2.垂直線分の上端は2本の水平線分より厳格に高く、下端は2本の水平線分より厳格に低くなければならない.
3.垂直線分は、2つの水平線分を厳密に等しい半分に分割する必要があります.
4.上の水平線分は、下の水平線分よりも厳密に短くなければならない.
二重十字の個数mod 1000000009の値を出力します.
R,C,N≤10000,R∗C≤1000000 R , C , N ≤ 10000 , R ∗ C ≤ 1000000
Solution:
lr[i]l r[i]はiから最大で左右にどれだけ伸びるかを表す
down[i]d o w n[i]はiから最大どれだけ下に伸びるかを表す
top[i]はiから最大でどれだけ伸びるかを表す
下端セグメントの中点jを列挙し,次に各上端セグメントの中点iに対して答えへの寄与を考慮する.
∑lr[j]len=1min(len−1,lr[i])∗top[i]∗down[j] ∑ l e n = 1 l r [ j ] m i n ( l e n − 1 , l r [ i ] ) ∗ t o p [ i ] ∗ d o w n [ j ]
minはうまく処理できないので、何とかして取り除きます.
ディスカッションの分類を試みます.
lr[i]≦lr[j]l r[i]≦l r[j]の場合、答えは(lr[i]∗lr[j]−lr[i](lr[i]+1)2)∗top[i]∗down[j](lr[i]∗lr[j]−l r[i](l r[i]+1)2)∗t o p[i]∗d o w n[j]
>lr[i]>lr[j]>l r[i]>l r[j]の場合、lr[j]∗(lr[j]−1)2∗top[i]−down[j]l r[j]∗(l r[j]−1)2∗t o p[i]∗d o w n[j]
各列の連続する非0区間については,iに関するものをすべて記録し,jと結合して計算するたびに
3つの値をツリー配列で維持します.
1. −lr[i]∗(lr[i]+1)2∗top[i] − l r [ i ] ∗ ( l r [ i ] + 1 ) 2 ∗ t o p [ i ]
2. lr[i]∗top[i] l r [ i ] ∗ t o p [ i ]
3. top[i] t o p [ i ]
RとCは不確定で配列が開かない可能性があるので,行列を1次元に圧縮した.
注意コードにはリアルタイム計算topコードが含まれています.
#include" "<" "<<x<for (;i<=m;i+=(i&-i))
{
tr[i][id]+=x;
if (tr[i][id]>=mod) tr[i][id]-=mod;
if (tr[i][id]<0) tr[i][id]+=mod;
}
}
int query(int id,int i)
{
int ans=0;
for (;i;i-=(i&-i))
{
ans+=tr[i][id];
if (ans>=mod) ans-=mod;
if (ans<0) ans+=mod;
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
for (int x,y,i=1;i<=p;i++) scanf("%d%d",&x,&y),pos[id(x,y)]=1;
for (int i=1;i<=n;i++)
{
l[1]=(!pos[id(i,1)]);
for (int j=2;j<=m;j++) if (!pos[id(i,j)]) l[j]=l[j-1]+1;else l[j]=0;
r[m]=(!pos[id(i,m)]);
for (int j=m-1;j>=1;j--) if (!pos[id(i,j)]) r[j]=r[j+1]+1;else r[j]=0;
for (int j=1;j<=m;j++)
lr[id(i,j)]=min(l[j],r[j])-1;
//,cout<" "<" "<for (int i=1;i<=m;i++)
{
down[id(n,i)]=(!pos[id(n,i)]);
for (int j=n-1;j>=1;j--)
if (!pos[id(j,i)]) down[id(j,i)]=down[id(j+1,i)]+1;
}
for (int i=1;i<=n*m;i++) if (down[i]) down[i]--;
for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
if (pos[id(j,i)]){memset(tr,0,sizeof(tr));top=j+1;continue;}
ans=(1ll*query(0,lr[id(j,i)])*down[id(j,i)]+ans)%mod;
ans=(1ll*query(1,lr[id(j,i)])*down[id(j,i)]%mod*lr[id(j,i)]+ans)%mod;
ans=(1ll*(query(2,m)-query(2,lr[id(j,i)])+mod)*down[id(j,i)]%mod*lr[id(j,i)]*(lr[id(j,i)]-1)/2+ans)%mod;
// cout<if (j==1) continue;
if (pos[id(j-1,i)]) continue;
if (lr[id(j-1,i)])
{
add(0,lr[id(j-1,i)],(1ll*(-lr[id(j-1,i)]*(lr[id(j-1,i)]+1)/2)*(j-1-top)%mod+mod)%mod);
add(1,lr[id(j-1,i)],lr[id(j-1,i)]*(j-1-top));
add(2,lr[id(j-1,i)],j-1-top);
}
}
memset(tr,0,sizeof(tr));top=1;
}
printf("%d",ans);
}