cf评测姬崩了又好了又崩了又好了，让这场vp更(a)加(w)有(s)趣(l)
开场fxq签了A提交了A（评测姬已经崩了qwq），之后hyk开F，lxy开G，fxq开E，hyk和lxy分别有了成熟的想法，在开赛一小时内提交了F和G，同样由于跑路的评测姬，结果未知qwq。
E题fxq假了，hyk假了，fxq和hyk一起提了一个算法又假了qwq，好在后来lxy提出了一个成熟的想法，将所有人的分数a从大到小排序，枚举所有分数，计算以当前人的a为最高分时的及格总人数，然后把他的a改成b，继续枚举，直到当前分数小于第一个b，退出。fxq套用lxy的想法用离散化+BIT写了E，交上去了。
fxq和lxy讨论E的期间hyk看了K，交了E之后三个人一起看K，窝萌都觉得可能是树形dp，但是具体怎么dp就只能各自提出各自成熟的想法（雾）。fxq提出对每个节点的按照深度排序，比较深度与到当前节点到根节点的距离大小决定是否从根节点新派兵，但是三个人都觉得细节不太清楚容易写挂，没有人尝试去写qwq。
开赛三个小时，就当我们都准备明天才能看到评测结果的时候，评测姬猝不及防地评测了我们提交的第一发代码，一下子把我们拉回了现实qwq。。。评测结束后，A题过了，FGE全都挂了，于是我们转头各自去调自己写的题，hyk数组开小了，改了之后F过了，lxy把G优化了一下，从tle2改成wa2，然后细节调不出来一直wa，fxq重新写了G，同样wa，lxy帮忙调了快速幂里可能爆long long的细节，过了G。之后fxq和lxy一起改E，lxy发现fxq少写了一个细节，碰到b的时候也要计算结果更新答案，而不是直接退出。fxq加了这个细节之后过了E。所以一个半小时之后窝萌终于把坑填完了qwq
剩下半个小时窝萌又讨论了K，但是并没有出现成熟的想法qwq
fxq:HIK
lxy:BIK
hyk:暂未补题
树形dp
选择一些叶子节点，计算从根到这些节点的路径，其他边走两遍
两个数组，f维护以当前节点为根的子树所有边走两边的值，dp维护以当前节点为子树，至少有一个叶子节点直接计算到根的路径的值
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=1000010;
int T,n,head[maxn],nxt[2*maxn],to[2*maxn],cnt;
LL f[maxn],dp[maxn];
void add(int u,int v){
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt++;
}
void dfs(int u,int fa,int d){
f[u]=0;
dp[u]=0;
bool judge=false;
LL diff=1e18+10;
for(int i=head[u];~i;i=nxt[i]){
int v=to[i];
if(v!=fa){
dfs(v,u,d+1);
f[u]+=f[v]+2;
if(dp[v]<=f[v]+2){
judge=true;
}
else{
diff=min(diff,dp[v]-(f[v]+2));
}
dp[u]+=min(dp[v],f[v]+2);
}
}
if(dp[u]==0) dp[u]=d;
else{
if(!judge) dp[u]+=diff;
}
}
int main(){
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%d",&n);
for(int i=1;i<=n;i++) head[i]=-1;
cnt=0;
for(int i=2;i<=n;i++){
int j;
scanf("%d",&j);
add(i,j);
add(j,i);
}
dfs(1,-1,0);
printf("Case #%d: %lld\n",cas,dp[1]);
}
}
我们要讨论（x，y）分别作为上下左右四条边界的情况，以下以底边为例，那么底边最长可以是多少呢，我们可以处理出每个点向左右可到达的最远距离（上下同理），假设我们已经知道了矩形的高度h，我们只需要知道最远的 由（x，j）可到达（x-h，j）的点是哪一个，由于询问和枚举h复杂度已经，我们需要log的查询复杂度，这就让我们想到了线段树，远的地方能到达就查询远的地方好啦。
对于每个更新操作，他只会影响这个点所在行列最远距离，更新即可。
所以，对于每次询问我们只需要建四颗线段树，分别统计为上下左右边的答案就行了，于是就码了300行QwQ
#include<bits/stdc++.h>
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(int &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int MAXN = 1100;
int t, n, m, q, cas;
int up[MAXN][MAXN], dw[MAXN][MAXN], le[MAXN][MAXN], ri[MAXN][MAXN];
struct tree{
int mx, mi;
}z[MAXN*10];
int mxtmp[MAXN*10];
char s[MAXN][MAXN];
int ans = 0;
void init(){
memset(mxtmp, 0, sizeof(mxtmp));
for(int i = 1;i <= n+1;i ++)
for(int j = 1;j <= m+1;j ++)
le[i][j] = ri[i][j] = up[i][j] = dw[i][j] = 0;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++){
if(j == 1) le[i][j] = 1;
else if(s[i][j] == '.') le[i][j] = j;
else le[i][j] = le[i][j-1];
}
for(int i = 1;i <= n;i ++)
for(int j = m;j >= 1;j --){
if(j == m) ri[i][j] = j;
else if(s[i][j] == '.') ri[i][j] = j;
else ri[i][j] = ri[i][j+1];
}
for(int j = 1;j <= m;j ++)
for(int i = 1;i <= n;i ++){
if(i == 1) up[i][j] = 1;
else if(s[i][j] == '.') up[i][j] = i;
else up[i][j] = up[i-1][j];
}
for(int j = 1;j <= m;j ++)
for(int i = n;i >= 1;i --){
if(i == n) dw[i][j] = n;
else if(s[i][j] == '.') dw[i][j] = i;
else dw[i][j] = dw[i+1][j];
}
}
void change(int x, int y){
if(s[x][y] == '.') s[x][y] = '#';
else s[x][y] = '.';
up[1][y] = 1;
for(int i = 2;i <= n;i ++)
if(s[i][y] == '.') up[i][y] = i;
else up[i][y] = up[i-1][y];
dw[n][1] = n;
for(int i = n-1;i >= 1;i --)
if(s[i][y] == '.') dw[i][y] = i;
else dw[i][y] = dw[i+1][y];
le[x][1] = 1;
for(int j = 2;j <= m;j ++)
if(s[x][j] == '.') le[x][j] = j;
else le[x][j] = le[x][j-1];
ri[x][m] = m;
for(int j = m-1;j >= 1;j --)
if(s[x][j] == '.') ri[x][j] = j;
else ri[x][j] = ri[x][j+1];
}
void update(int rt){
z[rt].mx = max(z[rt << 1].mx, z[rt << 1|1].mx);
z[rt].mi = min(z[rt << 1].mi, z[rt << 1|1].mi);
}
void build(int rt, int l, int r, int x, int y){
if(l == r){
z[rt].mx = mxtmp[l];
z[rt].mi = mxtmp[l];
return ;
}
int mid = (l + r) >> 1;
build(lson, x, y);
build(rson, x, y);
update(rt);
}
int upminl(int rt, int l, int r, int nowl, int nowr, int h){
if(l == r){
if(z[rt].mi > h) return 1e5;
else return l;
}
int mid = (l + r) >> 1;
int res = 1e5;
if(nowl <= l && r <= nowr){
if(z[rt << 1].mi <= h) return upminl(lson, nowl, nowr, h);
else if(z[rt << 1|1].mi <= h) return upminl(rson, nowl, nowr, h);
}
if(nowr > mid && z[rt << 1|1].mi <= h) res = min(res, upminl(rson, nowl, nowr, h));
if(nowl <= mid && z[rt << 1].mi <= h) res = min(res, upminl(lson , nowl, nowr, h));
return res;
}
int upmaxr(int rt, int l, int r, int nowl, int nowr, int h){
if(l == r){
if(z[rt].mi > h) return 0;
else return l;
}
int mid = (l + r) >> 1;
int res = 0;
if(nowl <= l && r <= nowr){
if(z[rt << 1|1].mi <= h) return upmaxr(rson, nowl, nowr, h);
else if(z[rt << 1].mi <= h) return upmaxr(lson, nowl, nowr, h);
}
if(nowr > mid && z[rt << 1|1].mi <= h) res = max(res, upmaxr(rson, nowl, nowr, h));
if(nowl <= mid && z[rt << 1].mi <= h) res = max(res, upmaxr(lson, nowl, nowr, h));
return res;
}
int downminl(int rt, int l, int r, int nowl, int nowr, int h){
if(l == r){
if(z[rt].mx < h) return 1e5;
else return l;
}
int mid = (l + r) >> 1;
int res = 1e5;
if(nowl <= l && r <= nowr){
if(z[rt << 1].mx >= h) return downminl(lson, nowl, nowr, h);
else if(z[rt << 1|1].mx >= h) return downminl(rson, nowl, nowr, h);
return 1e5;
}
if(nowr > mid && z[rt << 1|1].mx >= h) res = min(res, downminl(rson, nowl, nowr, h));
if(nowl <= mid && z[rt << 1].mx >= h) res = min(res, downminl(lson , nowl, nowr, h));
return res;
}
int downmaxr(int rt, int l, int r, int nowl, int nowr, int h){
if(l == r){
if(z[rt].mx < h) return 0;
else return l;
}
int mid = (l + r) >> 1;
int res = 0;
if(nowl <= l && r <= nowr){
if(z[rt << 1|1].mx >= h) return downmaxr(rson, nowl, nowr, h);
else if(z[rt << 1].mx >= h) return downmaxr(lson, nowl, nowr, h);
//return 0;
}
if(nowr > mid && z[rt << 1|1].mx >= h) res = max(res, downmaxr(rson, nowl, nowr, h));
if(nowl <= mid && z[rt << 1].mx >= h) res = max(res, downmaxr(lson, nowl, nowr, h));
return res;
}
void check(int x, int y, int &l, int &r, int col){
if(col == 0){
if(s[x][l-1] == '#') l = 1;
if(s[x][r+1] == '#') r = m;
}
if(col == 1){
if(s[l-1][y] == '#') l = 1;
if(s[r+1][y] == '#') r = n;
}
}
void workleft_right(int x, int y){//已知底边或顶边枚举高度
int l = le[x][y] + 1;
int r = ri[x][y] - 1;
check(x, y, l, r, 0);
for(int i = l;i <= r;i ++){
int to = up[x][i];
if(s[to][i] == '.') mxtmp[i] = up[x][i]+1;
else mxtmp[i] = up[x][i];
}
build(1, l, r, x, y);
for(int i = 1;i <= x;i ++){//作为底边
if(s[i][y] == '.') continue;
int nowl = le[i][y] + 1;
int nowr = ri[i][y] - 1;//枚举高的左右最大可达点
check(i, y, nowl, nowr, 0);
if(nowr < nowl) continue;
if((nowr - nowl + 1)*(x - i + 1) <= ans) continue;
int ansl = upminl(1, l, r, nowl, y, i);
int ansr = upmaxr(1, l, r, y, nowr, i);
if(ansl > y || ansr < y) continue;
ans = max(ans, (ansr - ansl + 1)*(x - i + 1));
}
for(int i = l;i <= r;i ++){
int to = dw[x][i];
if(s[to][i] == '.') mxtmp[i] = dw[x][i] - 1;
else mxtmp[i] = dw[x][i];
}
build(1, l, r, x, y);
for(int i = n;i >= x;i --){//作为顶边
if(s[i][y] == '.') continue;
int nowl = le[i][y] + 1;
int nowr = ri[i][y] - 1;//枚举高的左右最大可达点
check(i, y, nowl, nowr, 0);
if(nowr < nowl) continue;
if((nowr - nowl + 1)*(i - x + 1) <= ans) continue;
int ansl = downminl(1, l, r, nowl, y, i);
int ansr = downmaxr(1, l, r, y, nowr, i);
if(ansl > y || ansr < y) continue;
ans = max(ans, (ansr - ansl + 1)*(i - x + 1));
}
}
void workup_down(int x, int y){
int u = up[x][y] + 1;
int d = dw[x][y] - 1;
check(x, y, u, d, 1);
for(int i = u;i <= d;i ++){
int to = le[i][y];
if(s[i][to] == '.') mxtmp[i] = le[i][y]+1;
else mxtmp[i] = le[i][y];
}
build(1, u, d, x, y);
for(int i = 1;i <= y;i ++){
if(s[x][i] == '.') continue;
int nowl = up[x][i] + 1;
int nowr = dw[x][i] - 1;
check(x, i, nowl, nowr, 1);
if(nowr < nowl) continue;
if((nowr - nowl + 1)*(y - i + 1) <= ans) continue;
int ansl = upminl(1, u, d, nowl, x, i);
int ansr = upmaxr(1, u, d, x, nowr, i);
if(ansl > x || ansr < x) continue;
ans = max(ans, (ansr - ansl + 1)*(y - i + 1));
}
for(int i = u;i <= d;i ++){
int to = ri[i][y];
if(s[i][to] == '.') mxtmp[i] = ri[i][y] - 1;
else mxtmp[i] = ri[i][y];
}
build(1, u, d, x, y);
for(int i = m;i >= y;i --){
if(s[x][i] == '.') continue;
int nowl = up[x][i] + 1;
int nowr = dw[x][i] - 1;
check(x, i, nowl, nowr, 1);
if(nowr < nowl) continue;
if((nowr - nowl + 1)*(i - y + 1) <= ans) continue;
int ansl = downminl(1, u, d, nowl, x, i);
int ansr = downmaxr(1, u, d, x, nowr, i);
if(ansl > x || ansr < x) continue;
ans = max(ans, (ansr - ansl + 1)*(i - y + 1));
}
}
void work(){
while(q --){
ans = 0;
int op, x, y;
re(op), re(x), re(y);
if(op == 1){
change(x, y);
}
if(op == 2){
if(s[x][y] == '.'){
printf("0\n");
continue;
}
workleft_right(x, y);
workup_down(x, y);
printf("%d\n",ans);
}
}
}
int main(){
// freopen("data.in","r",stdin);
// freopen("Wall.out","w",stdout);
re(t);
for(int i = 1;i <= t;i ++){
scanf("%d %d %d",&n, &m, &q);
for(int j = 1;j <= n;j ++)
scanf("%s",s[j]+1);
printf("Case #%d:\n",++ cas);
init();
work();
}
return 0;
}