题面

思路

本题偏向思维吧，需要注意一点，开始时所有云都是没有重叠面积且速度相同的，所以往同一方向的云都是相对静止的，并且云的速度方向只有向右和向上，这样就给了我们一个十分优秀的性质–只有向上与向右的云才会重叠，并且最多一个位置只能被两朵云覆盖，最少一朵云，所以只需要判断任意一朵的向右的云是否将会与向上的相交即可，设向右的云有$n$朵，向上的云有$m$朵，那么$n*m$的做法已经不难想出了，但明显是无法拿满分的，需要优化。这时我们或许会想起初中科学老师的教导相对运动这一概念，我们把向上的云固定住，向右的云就变成了向右下$45度$角运动，这样它的右上角和左下角会与$x$轴有交点，然后我们对于一种方向的云他的右上角和左下角的连线映射到$x$轴上，然后对另一种方向的云判断是否有一条线段会与它重叠即可，可以用差分，线段树，排序，二分做。在这里我用的是标记永久化线段树。

细节

因为边缘不算，所以要对一种运动的矩形的对角线在$x$轴上左开右开，对另一种运动的矩形的对角线的查询要左闭右闭，然后离散化。

代码

个人觉得这篇题解写得不大好，还望各位通过代码理解。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
struct node{int l,r,opt;}seg[100005];
int tmp[200005],top=0,T,n;
void Read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
struct Tree
{
    int tree[800005],mark[800005];
    void add(int rt,int l,int r,int ql,int qr)
    {
        if (l>=ql&&r<=qr) {mark[rt]+=1;return;}
        tree[rt]+=min(qr,r)-max(ql,l)+1;
        int mid=l+r>>1;
        if (ql<=mid) add(rt<<1,l,mid,ql,qr);
        if (qr>mid) add(rt<<1|1,mid+1,r,ql,qr);
    }   
    int ask(int rt,int l,int r,int ql,int qr)
    {
        if (l>qr||r<ql) return 0;
        if(l>=ql&&r<=qr) return tree[rt]+(r-l+1)*mark[rt];
        int mid=l+r>>1;
        int res=(min(qr,r)-max(ql,l)+1)*mark[rt];
        if (ql<=mid) res+=ask(rt<<1,l,mid,ql,qr);
        if (qr>mid) res+=ask(rt<<1|1,mid+1,r,ql,qr);
        return res;
    }
}S;
int main()
{
    Read(T);
    while(T--)
    {
        top=0;
        memset(seg,0,sizeof(seg));
        memset(tmp,0,sizeof(tmp));
        memset(S.tree,0,sizeof(S.tree));
        memset(S.mark,0,sizeof(S.mark));
        Read(n);
        for (int i=1;i<=n;i++)
        {
            int x,y,w,h,d;
            Read(x),Read(y),Read(w),Read(h),Read(d);
            if (d==1) seg[i].l=x+y+1,seg[i].r=x+y+w+h-1;
            if (d==0) seg[i].l=x+y,seg[i].r=x+y+w+h;
            seg[i].opt=d;
            if (d==1) tmp[++top]=x+y+1,tmp[++top]=x+y+w+h-1;
            if (d==0) tmp[++top]=x+y,tmp[++top]=x+y+w+h;
        }
        sort(tmp+1,tmp+top+1);
        int cnt=unique(tmp+1,tmp+top+1)-tmp-1;
        for (int i=1;i<=n;i++)
        {
            seg[i].l=lower_bound(tmp+1,tmp+cnt+1,seg[i].l)-tmp;
            seg[i].r=lower_bound(tmp+1,tmp+cnt+1,seg[i].r)-tmp;
            if (seg[i].opt==0) S.add(1,1,cnt,seg[i].l,seg[i].r);
        }
        bool flag=0;
        for (int i=1;i<=n;i++) 
        if (seg[i].opt==1) 
        if (S.ask(1,1,cnt,seg[i].l,seg[i].r)>0) 
        {
            cout<<2<<endl;
            flag=1;
            break;
        } 
        if (!flag) cout<<1<<endl;
    }
    return 0;
}