究竟是谁在设计这种题目。
UniGravity · · 题解
鲜花：校内模拟赛做了一整场，赛后调了一百年发现线段树挂了。
考虑前缀和把矩形变成四个端点加数，就变成每次加若干线段。查询变成查左下角矩形和。
横着和竖着可以直接按照对应的维度扫描线。
对于斜着的线（例如从左下到右上）分为完全在查询矩形内、和矩形的竖直线或水平线相交几种情况。矩形内直接扫描线，竖直线和水平线考虑按照
代码时间较为（？）复杂：
// 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;
}