http://acmicpc.info/archives/1850
Problem D. Dire Wolf
Brief description:
略）
Analysis:
正难则反。）
http://acm.hust.edu.cn/vjudge/contest/viewSource.action?id=3048048
Problem E. Everlasting L
Brief description:
略）
Analysis:
注意到坐标范围较小。。可以扫描线 + 枚举。
预处理：
D[d][n]: <= n 且与 d 互质的数有多少个。。。
up，rt：向上和向右最远可以延伸的距离。。
从左向右扫描线。。。O(n3) 大枚举。。。分三类讨论。
（1. 再左边且不可能与之相交。。
（2. 再左边且与之相交。。
（3. 同一列。。
其中 2 和 3 可以放在一起处理。。。总复杂度 $$O(n3)$$
[cpp]
//}/* .................................................................................................................................. */
const int N = int(2e2) + 9;
int A[N][N], up[N][N], rt[N][N]; int D[N][N]; VII E[N];
int C[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
// <= 2 ... 1
FOR(i, 1, N){
FOR(j, 1, N){
D[i][j] = D[i][j-1] + (gcd(i, j) == 1);
}
}
Rush{
RST(A); FLC(up, rt, -1);
Rush{int x, y; RD(x, y); A[x][y] = 1;}
DWN(i, N-1, 0){
DWN(j, N-1, 0){
rt[i][j] = A[i][j] ? rt[i][j+1] + 1 : -1;
up[i][j] = A[i][j] ? up[i+1][j] + 1 : -1;
}
}
RST(C); REP(j, N) E[j].clear();
LL z = 0, pre = 0; REP(j, N){
ECH(it, E[j]) C[it->fi] -= it->se;
DWN(i, N, 0){
LL ex = C[i]; REP_1(uu, up[i][j]){
ex += C[i+uu]; int d = D[uu][rt[i][j]];
z += (pre-ex)*d; C[i] += d, pre += d; ex += d;
}
REP_1(rr, rt[i][j]) E[j+rr+1].PB(MP(i, D[rr][up[i][j]]));
}
}
OT(z*2);
}
}
[/cpp]
