挺套路的题。如果值域和线段数量同阶,可以预处理不能越过的线段,使用状压四个方向记录每个节点能不能往这个方向走,然后直接爆搜就好了,标记上能走到哪些地方。但这个值域一看就是没有救的,于是就要拿出来离散化了。把线段的横纵坐标都拎出来离散化,依然是同样的预处理,然后从离散化后的 \((0,0)\) 开始向外爆搜,最后还是扫一遍能够到哪些地方,统计答案只需要变成离散化前的对应位置即可。唯一需要注意的地方是放入边界横纵坐标一定要比数据范围大一点,本人最开始边界放 \(10^9\) 疯狂 WA。于是总复杂度为 \(\mathcal O(nm + n \log n + m \log m)\),分别为搜索和离散化。直接这样说可能还是有些抽象了,不过代码非常清晰。
#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y) (__lg((x),(y)))
using namespace std;
namespace FastIO
{
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
return s*w;
}
template<typename T> inline void read(T &s)
{
s=0; int w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
s=s*w;
}
template<typename T,typename... Args> inline void read(T &x,Args &...args)
{
read(x),read(args...);
}
template<typename T> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
putchar(ch);
return;
}
}
using namespace FastIO;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=5010;
static const int inf=2147483647;
static const int INF=4557430888798830399;
static const int mod=1e9+7;
static const int bas=131;
int n,m,ans;
int a[MAX],b[MAX],c[MAX],d[MAX],e[MAX],f[MAX];
int X[MAX],Y[MAX],cntx,cnty;
#define lbx(x) lower_bound(X+1,X+cntx+1,x)-X
#define lby(y) lower_bound(Y+1,Y+cnty+1,y)-Y
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int sx,sy,obs[MAX][MAX],vis[MAX][MAX];
void dfs(int x,int y)
{
if(x<1||y<1||x>cntx||y>cnty||vis[x][y]) return;
vis[x][y]=1;
for(int i=0;i<4;++i) if(!(obs[x][y]>>i&1)) dfs(x+dx[i],y+dy[i]);
}
inline void dry()
{
X[++cntx]=-1.1e9,X[++cntx]=0,X[++cntx]=1.1e9,
Y[++cnty]=-1.1e9,Y[++cnty]=0,Y[++cnty]=1.1e9;
read(n,m);
for(int i=1;i<=n;++i) read(a[i],b[i],c[i]),X[++cntx]=a[i],X[++cntx]=b[i],Y[++cnty]=c[i];
for(int i=1;i<=m;++i) read(d[i],e[i],f[i]),X[++cntx]=d[i],Y[++cnty]=e[i],Y[++cnty]=f[i];
sort(X+1,X+cntx+1),cntx=unique(X+1,X+cntx+1)-X-1;
sort(Y+1,Y+cnty+1),cnty=unique(Y+1,Y+cnty+1)-Y-1;
for(int i=1;i<=n;++i)
{
int l=lbx(a[i]),r=lbx(b[i]),y=lby(c[i]);
for(int j=l;j<r;++j) obs[j][y]|=1<<1,obs[j][y-1]|=1<<0;
}
for(int i=1;i<=m;++i)
{
int x=lbx(d[i]),l=lby(e[i]),r=lby(f[i]);
for(int j=l;j<r;++j) obs[x][j]|=1<<3,obs[x-1][j]|=1<<2;
}
sx=lbx(0),sy=lby(0),dfs(sx,sy);
for(int i=1;i<=cntx;++i) if(vis[i][1]||vis[i][cnty]) return puts("INF"),void();
for(int i=1;i<=cnty;++i) if(vis[1][i]||vis[cntx][i]) return puts("INF"),void();
for(int i=2;i<cntx;++i) for(int j=2;j<cnty;++j) if(vis[i][j]) ans+=(X[i+1]-X[i])*(Y[j+1]-Y[j]);
write(ans,'\n');
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::dry();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}
标签:int,ABC168F,read,题解,long,++,Single,getchar,define
From: https://www.cnblogs.com/LittleTwoawa/p/17489227.html