51nod 1562 玻璃切割

xiaoxiao2021-02-27  523

之前连续好几天没怎么睡,还好没得道成仙。。。ddl是第一生产力。。。

找了道水题做下。

倒序处理所有答案,再输出。

用可以用并查集进行合并区间操作(一开始想写伪链表的,发现好像不行)。不断更新横纵最大值即可。

#include<bits/stdc++.h> using namespace std; void read(int &a) { char ch;while(!((ch=getchar())>='0')&&(ch<='9')); a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0'; } inline void prin_d(int x) { if (x > 9) { prin_d(x / 10); } putchar(x % 10 + '0'); return ; } const int MAXN=200200; char op[MAXN]; int a[MAXN],hcut[MAXN],vcut[MAXN],hseg[MAXN],vseg[MAXN],hnode[MAXN],vnode[MAXN],vfa[MAXN],hfa[MAXN]; long long ans[MAXN]; int vfindfa(int x) { if(vfa[x]==x) return x; return vfa[x]=vfindfa(vfa[x]); } int hfindfa(int x) { if(hfa[x]==x) return x; return hfa[x]=hfindfa(hfa[x]); } int main() { int v,h,n,i,hmx,vmx,hcnt,vcnt,bef,index; while(~scanf("%d%d%d",&v,&h,&n)) { memset(hcut,0,sizeof(hcut)); memset(vcut,0,sizeof(vcut)); hcut[h]=1; vcut[v]=1; for(i=0;i<n;i++) { scanf(" %c %d",&op[i],&a[i]); if(op[i]=='H') hcut[a[i]]=1; else vcut[a[i]]=1; } hmx=vmx=hcnt=vcnt=bef=0; for(i=1;i<=h;i++) { if(hcut[i]) { hseg[hcnt++]=i-bef; hmx=max(hmx,hseg[hcnt-1]); bef=i; hnode[i]=hcnt-1; } } bef=0; for(i=1;i<=v;i++) { if(vcut[i]) { vseg[vcnt++]=i-bef; vmx=max(vmx,vseg[vcnt-1]); bef=i; vnode[i]=vcnt-1; } } for(i=0;i<hcnt;i++) hfa[i]=i; for(i=0;i<vcnt;i++) vfa[i]=i; for(i=n-1;i>=0;i--) { ans[i]=(long long)hmx*vmx; if(op[i]=='H') { index=hfindfa(hnode[a[i]]); hfa[hnode[a[i]]+1]=index; hseg[index]+=hseg[hnode[a[i]]+1]; hmx=max(hmx,hseg[index]); } else { index=vfindfa(vnode[a[i]]); vfa[vnode[a[i]]+1]=index; vseg[index]+=vseg[vnode[a[i]]+1]; vmx=max(vmx,vseg[index]); } } for(i=0;i<n;i++) printf("%lld\n",ans[i]); } }

转载请注明原文地址: https://www.6miu.com/read-388.html

最新回复(0)