[ICPC2018 WF] Triangles
eipai10
·
·
题解
个人感觉不到黑。
首先，简化问题，只考虑 \triangle 的数量，然后反转一下，再统计一遍。
对于一个三角形，可以把它的三边理解为从一个顶点延伸出的两个长度相等的边以及两条边另一端点的连线。
由此，再次简化问题，我们统计顶点在作为右下顶点时按上述方法能构成的三角形个数，从左到右，从上到下处理。对于每个点 (x,y) 统计下列数据：
$2.U(x,y):$ 从 $(x,y)$ 往左上方最多能延伸多远；
$3.D(x,y):$ 从 $(x,y)$ 往右上方最多能延伸多远。
这三个值可以快速求出。有了这三个值之后，就可以对 $(x,y)$ 进行求解了。考虑从 $(x,y)$ 延伸的两条边距离可取任意正整数 $i\in[1,min(L(x,y),U(x,y))]$ 若满足 $D(x-i,y)\geq i$ 则意味着此处有一个右下顶点为 $(x,y)$ 长为 $i$ 的三角形。
然后就 TLE 了，因为时间复杂度 $O(n^3)$ 。
考虑用 BIT 维护满足 $D(x-i,y)\geq i$ 的点的个数：
考虑点 $(x,y)$ 最多能贡献给几个点，显然 $\forall i,1\leq i\leq D(x,y)
满足
怎么维护在哪里减一？
创一个 vector 数组，记录到 $(x,y)$ 之后时没有贡献的点，处理完以 $(x,y)$ 为右下顶点的三角形的贡献后，将 vector 数组里的位置减一。
代码
```cpp
#include<bits/stdc++.h>
using namespace std;
template<class T> using V = vector<T>;
using LL = long long;
const int NN = 1.2E4 + 5;
int R, C, B[NN];
void M(int k, int d){for(; k; k -= k & (-k)) B[k] += d;}
int Q(int k){
int res = 0;
for(; k <= (C + 1) / 2; k += k & (-k)) res += B[k];
return res;
}
using VI = V<int>;
LL solve(V<string> &G){
V<VI> U(2 * R, VI(2 * C)), D(U), T(2 * C);
auto pd = [&](int a, int b){return G[a][b] != ' ';};
LL ans = 0;
for(int r = 1; r < 2 * R; r += 2){
int mx = 0;
for(int c = pd(r, 1) ? 1 : 3, k = 1, l = 0; c < 2 * C; c += 4, ++k){
int &u = U[r][c], &d = D[r][c];
u = pd(r - 1, c - 1) ? U[r - 2][c - 2] + 1 : 0,
d = pd(r - 1, c + 1) ? D[r - 2][c + 2] + 1 : 0,
l = pd(r, c - 1) ? l + 1 : 0, ans += Q(k - min(u, l)),
M(k, 1), T[k + d].push_back(k), mx = max(mx, k + d);
while(!T[k].empty()) M(T[k].back(), -1), T[k].pop_back();
}
for(int i = C / 2 + 1; i <= mx; ++i) while(!T[i].empty())
M(T[i].back(), -1), T[i].pop_back();
}
return ans;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0);
cin >> R >> C, cin.ignore();
V<string> G(2 * R, string(2 * C + 2, ' '));
for(int i = 1; i < 2 * R; ++i){
string s;
getline(cin, s), copy(begin(s), end(s), begin(G[i]) + 1);
}
LL ans = solve(G);
reverse(begin(G) + 1, end(G)), ans += solve(G);
return printf("%lld", ans), 0;
}
```