求扫描线部分的答案和std是一致的(ans1是对的
但ans2-ans3斜线暴力部分错了(比如color2比答案小2
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
int tid;
int n,m,q;
int la;
int ans1,ans2,ans3;
int t,a,b,c,d;
int tot,cnt,qoq;
int slx1[6],sly1[6],slx2[6],sly2[6];
int hx1[100010],hx2[100010],hy[100010],h;
int sy1[100010],sy2[100010],sx[100010],s;
int x[200010];
bool exi[6];
struct node{
int x,y;
}pre;
bool operator <(node x1,node x2){return x1.x==x2.x?x1.y<x2.y:x1.x<x2.x;}
map<node,bool>vis;
struct edge{
int y,x1,x2;
int opt;
}e[200010];
bool cmp(edge x1,edge x2){return x1.y<x2.y;}
struct Seg{
int len,sum;
}T[800010];
void pushup(int id,int l,int r)
{
if(T[id].sum) T[id].len=x[r+1]-x[l];
else if(l<r) T[id].len=T[id<<1].len+T[id<<1|1].len;
else T[id].len=0;
}
void add(int id,int l,int r,int u,int v,int k)
{
if(x[l]==u && x[r+1]==v) return T[id].sum+=k,pushup(id,l,r),void();
int mid=l+r>>1;
if(v<=x[mid+1]) add(id<<1,l,mid,u,v,k);
else if(u>=x[mid+1]) add(id<<1|1,mid+1,r,u,v,k);
else
{
add(id<<1,l,mid,u,x[mid+1],k);
add(id<<1|1,mid+1,r,x[mid+1],v,k);
}
pushup(id,l,r);
}
signed main()
{
cin>>tid;
cin>>n>>m>>q;
for(int i=1;i<=q;++i)
{
cin>>t>>a>>b>>c>>d;
if(t==3)
{
++qoq;
slx1[qoq]=a,sly1[qoq]=b;
slx2[qoq]=c,sly2[qoq]=d;
continue;
}
if(t==1) hx1[++h]=a,hx2[h]=c,hy[h]=b;
else sy1[++s]=b,sy2[s]=d,sx[s]=a;
x[++tot]=a,x[++tot]=c+1;
e[++cnt].opt=1;
e[cnt].x1=a,e[cnt].x2=c+1,e[cnt].y=b;
e[++cnt].opt=-1;
e[cnt].x1=a,e[cnt].x2=c+1,e[cnt].y=d+1;
}
sort(x+1,x+tot+1);
m=unique(x+1,x+tot+1)-x-1;
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<cnt;++i)
{
add(1,1,m-1,e[i].x1,e[i].x2,e[i].opt);
ans1+=(e[i+1].y-e[i].y)*T[1].len;
}
for(int i=1;i<=qoq;++i)
{
for(int j=1;j<i;++j) if(!exi[j] && sly1[j]-slx1[j]==sly1[i]-slx1[i])
{
if(slx1[j]<=slx1[i] && slx2[i]<=slx2[j]) {exi[i]=1;break;}
if(slx1[j]>=slx1[i] && slx2[i]>=slx2[j]) exi[j]=1,ans2-=slx2[j]-slx1[j]+1;
else if(slx1[i]<=slx2[j] && slx1[i]>slx1[j]) slx1[i]=slx2[j]+1;
else if(slx2[i]<slx2[j] && slx2[i]>=slx1[j]) slx2[i]=slx1[j]-1;
}
if(!exi[i]) ans2+=slx2[i]-slx1[i]+1;
}
for(int i=1;i<=qoq;++i) if(!exi[i])
{
for(int j=1;j<=h;++j)
{
pre.y=hy[j];
pre.x=hy[j]-sly1[i]+slx1[i];
if(hx1[j]<=pre.x && pre.x<=hx2[j] && slx1[i]<=pre.x && pre.x<=slx2[i])
if(!vis[pre]) vis[pre]=1,++ans3;
}
for(int j=1;j<=s;++j)
{
pre.x=sx[j];
pre.y=sx[j]+sly1[i]-slx1[i];
if(sy1[j]<=pre.y && pre.y<=sy2[j] && sly1[i]<=pre.y && pre.y<=sly2[i])
if(!vis[pre]) vis[pre]=1,++ans3;
}
}
cout<<ans1+ans2-ans3<<'\n';
return 0;
}