自动搬运

查看原文

来自洛谷，原作者为

	UniGravity 好菜阿。

搬运于2025-08-24 23:11:49，当前版本为作者最后更新于2025-06-27 15:21:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

鲜花：校内模拟赛做了一整场，赛后调了一百年发现线段树挂了。

考虑前缀和把矩形变成四个端点加数，就变成每次加若干线段。查询变成查左下角矩形和。

横着和竖着可以直接按照对应的维度扫描线。

对于斜着的线（例如从左下到右上）分为完全在查询矩形内、和矩形的竖直线或水平线相交几种情况。矩形内直接扫描线，竖直线和水平线考虑按照 $x+y$ 或 $x-y$ 扫描即可。

代码时间较为（？）复杂：

// Code by UniGravity
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define forto(i,a,b) for(register int i=(a);i<=(b);i++)
#define forbk(i,a,b) for(register int i=(a);i>=(b);i--)
#define forv(i,a) for(register int i=0;i<(a);i++)
#define il inline
#define eb emplace_back
#define mp make_pair
using namespace std;
il int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N=250005,VM=250000,M=6000005;
struct Seg{
    ll t1[N*5],t2[N*5];int n=500000;
    #define lowbit(x) (x&-x)
    il void clear(){memset(t1,0,sizeof(t1)),memset(t2,0,sizeof(t2));}
    il void _add(int i,ll v){
        ll v1=i*v;
        for(;i<=n;i+=(i&-i))t1[i]+=v,t2[i]+=v1;
    }
    il void add(int l,int r,ll v){if(l<=0||r<=0)return;_add(l,v),_add(r+1,-v);}
    il void add(int p,ll v){add(p,p,v);}
    il ll _qry(ll t[],int i){
        ll a=0;for(;i>=1;i-=(i&-i))a+=t[i];return a;
    }
    il ll qry(int l,int r){
        if(l<=0||r<=0)return 0;
        return 1ll*(r+1)*_qry(t1,r)-1ll*l*_qry(t1,l-1)-_qry(t2,r)+_qry(t2,l-1);
    }
}ds,all1,allc1,all2,allc2,dw,dwc,up,upc;
const int dx[]={1,1,0,-1,-1,-1,0,1},dy[]={0,1,1,1,0,-1,-1,-1};
int n,m,q;
struct Rect{int ax,ay,bx,by;}r[N];
struct Line1{int x,y,len,v;};struct Line2{int x,y,v;};
struct Point{int x,y,id;ll ans;}a[N];
vector<Line1>l1,l2;vector<Line2>l3,l4;
ll allans[N];

vector<long long int>count_enclosing_rectangle(vector<pair<int,int>> R1,vector<pair<int,int>>R2,vector<int>V,vector<int>I,vector<int>D,vector<pair<int,int>>P){
    n=R1.size();
    forv(i,n)r[i+1].ax=R1[i].first,r[i+1].ay=R1[i].second,r[i+1].bx=R2[i].first,r[i+1].by=R2[i].second;
    m=V.size();
    int dr,id,dis;
    forv(_,m){
        dr=V[_],id=I[_],dis=D[_];int ax=r[id].ax,ay=r[id].ay,bx=r[id].bx,by=r[id].by;
        if(dr==2||dr==6){//只对 y 操作
            int d=(dr==2)?(dis-1):-(dis-1);
            l1.eb((Line1){ax,ay,d,1});
            l1.eb((Line1){ax,by+1,d,-1});
            l1.eb((Line1){bx+1,ay,d,-1});
            l1.eb((Line1){bx+1,by+1,d,1});
        }else if(dr==1||dr==5){//左下-右上线段
            if(dr==1){
                l3.eb((Line2){ax,ay,1}),l3.eb((Line2){ax+dis,ay+dis,-1});
                l3.eb((Line2){ax,by+1,-1}),l3.eb((Line2){ax+dis,by+1+dis,1});
                l3.eb((Line2){bx+1,ay,-1}),l3.eb((Line2){bx+1+dis,ay+dis,1});
                l3.eb((Line2){bx+1,by+1,1}),l3.eb((Line2){bx+1+dis,by+1+dis,-1});
            }else{
                l3.eb((Line2){ax+1,ay+1,-1}),l3.eb((Line2){ax+1-dis,ay+1-dis,1});
                l3.eb((Line2){ax+1,by+2,1}),l3.eb((Line2){ax+1-dis,by+2-dis,-1});
                l3.eb((Line2){bx+2,ay+1,1}),l3.eb((Line2){bx+2-dis,ay+1-dis,-1});
                l3.eb((Line2){bx+2,by+2,-1}),l3.eb((Line2){bx+2-dis,by+2-dis,1});
            }
        }else if(dr==0||dr==4){
            int d=(dr==0)?(dis-1):-(dis-1);
            l2.eb((Line1){ax,ay,d,1});
            l2.eb((Line1){ax,by+1,d,-1});
            l2.eb((Line1){bx+1,ay,d,-1});
            l2.eb((Line1){bx+1,by+1,d,1});
        }else{//左上-右下线段
            if(dr==7){
                l4.eb((Line2){ax,by,1}),l4.eb((Line2){ax+dis,by-dis,-1});
                l4.eb((Line2){ax,ay-1,-1}),l4.eb((Line2){ax+dis,ay-1-dis,1});
                l4.eb((Line2){bx+1,by,-1}),l4.eb((Line2){bx+1+dis,by-dis,1});
                l4.eb((Line2){bx+1,ay-1,1}),l4.eb((Line2){bx+1+dis,ay-1-dis,-1});
            }else{
                l4.eb((Line2){ax+1,by-1,-1}),l4.eb((Line2){ax+1-dis,by-1+dis,1});
                l4.eb((Line2){ax+1,ay-2,1}),l4.eb((Line2){ax+1-dis,ay-2+dis,-1});
                l4.eb((Line2){bx+2,by-1,1}),l4.eb((Line2){bx+2-dis,by-1+dis,-1});
                l4.eb((Line2){bx+2,ay-2,-1}),l4.eb((Line2){bx+2-dis,ay-2+dis,1});
            }
        }
        r[id].ax+=dis*dx[dr],r[id].bx+=dis*dx[dr],r[id].ay+=dis*dy[dr],r[id].by+=dis*dy[dr];
    }
    forto(i,1,n){//加上额外的最后一次
        l1.eb((Line1){r[i].ax,r[i].ay,0,1});
        l1.eb((Line1){r[i].ax,r[i].by+1,0,-1});
        l1.eb((Line1){r[i].bx+1,r[i].ay,0,-1});
        l1.eb((Line1){r[i].bx+1,r[i].by+1,0,1});
    }
    q=P.size();
    forto(i,1,q)a[i].x=P[i-1].first,a[i].y=P[i-1].second,a[i].id=i,a[i].ans=0;
    // 竖直线段处理 / 斜线段
    sort(a+1,a+q+1,[](Point &x,Point &y){return x.x<y.x;});
    sort(l1.begin(),l1.end(),[](Line1 &x,Line1 &y){return x.x<y.x;});
    sort(l3.begin(),l3.end(),[](Line2 &x,Line2 &y){return x.x<y.x;});
    sort(l4.begin(),l4.end(),[](Line2 &x,Line2 &y){return x.x<y.x;});
    int j=0,k1=0,k2=0;ll sum;
    forto(i,1,q){
        while(j<l1.size()&&l1[j].x<=a[i].x){
            int l=l1[j].y,r=l1[j].y+l1[j].len;if(l>r)swap(l,r);
            ds.add(l,r,l1[j].v),j++;
        }
        a[i].ans+=ds.qry(1,a[i].y);

        while(k1<l3.size()&&l3[k1].x<=a[i].x){
            all1.add(l3[k1].y,l3[k1].y*l3[k1].v),allc1.add(l3[k1].y,l3[k1].v);
            dw.add(l3[k1].y-l3[k1].x+VM,(l3[k1].y-l3[k1].x)*l3[k1].v);
            dwc.add(l3[k1].y-l3[k1].x+VM,l3[k1].v);
            k1++;
        }
        sum=(a[i].y+1)*allc1.qry(1,a[i].y)-all1.qry(1,a[i].y);
        sum+=dw.qry(1,a[i].y-a[i].x+VM)+(a[i].x-a[i].y)*dwc.qry(1,a[i].y-a[i].x+VM);
        a[i].ans+=sum;

        while(k2<l4.size()&&l4[k2].x<=a[i].x){
            all2.add(l4[k2].y,l4[k2].y*l4[k2].v),allc2.add(l4[k2].y,l4[k2].v);
            up.add(l4[k2].x+l4[k2].y,(l4[k2].x+l4[k2].y)*l4[k2].v);
            upc.add(l4[k2].x+l4[k2].y,l4[k2].v);
            k2++;
        }
        sum=all2.qry(a[i].y,VM*2)-(a[i].y-1)*allc2.qry(a[i].y,VM*2);
        sum+=upc.qry(a[i].x+a[i].y,VM*2)*(a[i].x+a[i].y)-up.qry(a[i].x+a[i].y,VM*2);
        a[i].ans+=sum;
    }
    // 水平线段处理 其实就是换个扫描线方式
    sort(a+1,a+q+1,[](Point &x,Point &y){return x.y<y.y;});
    sort(l2.begin(),l2.end(),[](Line1 &x,Line1 &y){return x.y<y.y;});
    ds.clear();
    j=0;
    forto(i,1,q){
        while(j<l2.size()&&l2[j].y<=a[i].y){
            int l=l2[j].x,r=l2[j].x+l2[j].len;if(l>r)swap(l,r);
            ds.add(l,r,l2[j].v),j++;
        }
        a[i].ans+=ds.qry(1,a[i].x);
    }

    forto(i,1,q)allans[a[i].id]=a[i].ans;
    vector<ll>ansv;
    forto(i,1,q)ansv.eb(allans[i]);
    return ansv;
}