模拟赛 T3，好像是 lxl 的题。
题意
给定一个 \(n\times n\) 的二维平面，有 \(n\times n\) 个整点，每个整点都有权值，初始为 \(0\)。
有 \(n\) 次操作，每次操作给定一个矩形 \(x_1,x_2,y_1,y_2\) 和一个值 \(v\)，把这个矩形内的所有点的权值跟 \(v\) 取 \(\max\)。
在这 \(n\) 次操作之后，有 \(m\) 次询问，每次询问查询一个矩形的权值和。
数据范围： \(1\le n,m\le 10^5，1\le v \le n\)。
题解
直接考虑分块，把 \(x\) 轴分成 \(O(\sqrt{n})\) 个块，对于每个块内部会有一些零散的修改/查询，以及一些完整跨过这个块的修改/查询，下面对每个块单独考虑。
我们把这个块内部零散的修改/查询涉及到的 \(y\) 坐标离散化，设离散化后的 \(y\) 一共有 \(tot\) 个，那么所有块的 \(tot\) 之和是 \(O(n+m)\) 级别的。
我们称离散化之后的网格的每个点为一个格子，显然一个格子在原平面中代表一个在 \(x\) 轴方向上长为 \(1\) 的矩形。
因为修改都是在查询之前的，所以我们可以把修改离线下来按照 \(v\) 从大到小排序，这样的好处是每个点都只会被覆盖一次。
-
对散块修改：
我们对每个 \(x\) 都开一个大小为 \(tot\) 的并查集，维护这个 \(x\) 坐标上哪些离散化之后的 \(y\) 还没有被覆盖，然后对散块的每个 \(x\) 都用并查集找到还没被覆盖的 \(y\) 进行覆盖。同时我们要对于每个离散化之后的 \(y\) 去维护有多少个真实的 \(x\) 已经被修改了（记作 \(c_1\)），以及这些修改操作的 \(v\) 之和（记作 \(s_1\)）。 -
对整块修改：
我们开一个大小为 \(n\) 的并查集维护哪些真实的 \(y\) 还没有被修改，然后找到所有还没被修改的 \(y\) 进行修改。同时我们要对于每个离散化之后的 \(y\) 去维护有多少个真实的 \(y\) 已经被修改了（记作 \(c_2\)），以及这些修改操作的 \(v\) 之和（记作 \(s_2\)）。 -
对散块查询：
对于散块查询，我们只需要提前处理出离散化之后的网格的二维前缀和即可。具体的，当我们进行散块修改时对 \((x,y)\) 这个格子（\(y\) 是离散化之后的）进行了覆盖，那么在这次操作之前，它里面已经有 \(c_2(y)\) 个真实的 \(y\) 被修改了，且权值和为 \(s_2(y)\)，我们可以算出这个格子中剩下还有多少个点没被覆盖，用它乘上这次操作的 \(v\) 再加上 \(s_2(y)\) 就是这个格子的权值。 -
对整块查询：
类似的维护原始真实的 \(y\) 序列的前缀和即可。
不难分析出复杂度是 \(O(n\sqrt{n})\)（假设 \(n=m\)）。
code
#include<bits/stdc++.h>
#define Debug puts("-------------------------")
#define pb push_back
#define LL long long
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5,B=320;inline int read(){int w=1,s=0;char c=getchar();for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());return w*s;
}
int n,m,L[B],R[B],id[N],t,len;
LL ans[N];
struct P1{ int l1,r1,l2,r2,v; };
struct P2{ int l2,r2,v; };
struct Q1{ int l1,r1,l2,r2,id; };
struct Q2{ int l2,r2,id; };
vector<P1> v1[B];
vector<P2> v2[B];
vector<Q1> v3[B];
vector<Q2> v4[B];
void Init(){len=sqrt(n);t=(n+len-1)/len;for(int i=1;i<=t;i++){L[i]=R[i-1]+1,R[i]=min(n,len*i);for(int j=L[i];j<=R[i];j++) id[j]=i;}
}
int dis[N<<2],tot,ID[N],f[B][N],f2[N],c1[N],c2[N];
LL s1[N],s2[N],pre[B][N],pre2[N];
vector<PII> vec[N];
int Dis(int x){return lower_bound(dis+1,dis+tot+1,x)-dis;}
int get(int x,int *fa){return (x==fa[x])?x:(fa[x]=get(fa[x],fa));}
int Len(int y){return dis[y+1]-dis[y];}
void solve(int o,vector<P1> &v1,vector<P2> &v2,vector<Q1> &v3,vector<Q2> &v4){int sz1=v1.size(),sz2=v2.size(),sz3=v3.size(),sz4=v4.size(),len=R[o]-L[o]+1;dis[tot=1]=1,dis[++tot]=n+1; for(P1 u:v1) dis[++tot]=u.l2,dis[++tot]=u.r2+1;for(Q1 u:v3) dis[++tot]=u.l2,dis[++tot]=u.r2+1;sort(dis+1,dis+tot+1),tot=unique(dis+1,dis+tot+1)-dis-1; --tot; ///最后一个 n+1 不算 for(int i=1;i<=tot;i++) for(int j=dis[i];j<dis[i+1];j++) ID[j]=i;for(int i=0;i<sz1;i++) v1[i].l2=Dis(v1[i].l2),v1[i].r2=Dis(v1[i].r2+1)-1;for(int i=0;i<sz3;i++) v3[i].l2=Dis(v3[i].l2),v3[i].r2=Dis(v3[i].r2+1)-1;for(int i=1;i<=n;i++) vec[i].clear();for(int i=0;i<sz1;i++) vec[v1[i].v].pb({1,i});for(int i=0;i<sz2;i++) vec[v2[i].v].pb({2,i});for(int i=1;i<=len;i++) for(int j=1;j<=tot+1;j++) f[i][j]=j,pre[i][j]=0;for(int i=1;i<=n+1;i++) f2[i]=i,pre2[i]=0;for(int i=1;i<=tot;i++) s1[i]=s2[i]=c1[i]=c2[i]=0;for(int val=n;val>=1;val--){for(PII u:vec[val]){int i=u.se;if(u.fi==1){int l1=v1[i].l1,r1=v1[i].r1,l2=v1[i].l2,r2=v1[i].r2;for(int x=l1-L[o]+1;x<=r1-L[o]+1;x++){int y=get(l2,f[x]);while(y<=r2){c1[y]++,s1[y]+=val,pre[x][y]=s2[y]+1ll*val*(Len(y)-c2[y]);f[x][y]=y+1,y=get(y,f[x]);}}}else{int l2=v2[i].l2,r2=v2[i].r2,y1=get(l2,f2);while(y1<=r2){int y=ID[y1];c2[y]++,s2[y]+=val,pre2[y1]=s1[y]+1ll*val*(len-c1[y]);f2[y1]=y1+1,y1=get(y1,f2);}}}} //还会剩下一些没被覆盖的 for(int x=1;x<=len;x++){int y=get(1,f[x]);while(y<=tot) pre[x][y]=s2[y],f[x][y]=y+1,y=get(y,f[x]);}int y=get(1,f2);while(y<=n) pre2[y]=s1[ID[y]],f2[y]=y+1,y=get(y,f2);for(int i=1;i<=len;i++) for(int j=1;j<=tot;j++) pre[i][j]+=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];for(int i=1;i<=n;i++) pre2[i]+=pre2[i-1];for(Q1 u:v3){int l1=u.l1-L[o]+1,r1=u.r1-L[o]+1,l2=u.l2,r2=u.r2;ans[u.id]+=pre[r1][r2]-pre[l1-1][r2]-pre[r1][l2-1]+pre[l1-1][l2-1];}for(Q2 u:v4) ans[u.id]+=pre2[u.r2]-pre2[u.l2-1];
}
signed main(){freopen("rmrs.in","r",stdin);freopen("rmrs.out","w",stdout);n=read(),m=read();Init();for(int i=1;i<=n;i++){int l1=read(),r1=read(),l2=read(),r2=read(),v=read(),p=id[l1],q=id[r1];if(p==q) v1[p].pb({l1,r1,l2,r2,v});else{v1[p].pb({l1,R[p],l2,r2,v}),v1[q].pb({L[q],r1,l2,r2,v});for(int j=p+1;j<q;j++) v2[j].pb({l2,r2,v});}}for(int i=1;i<=m;i++){int l1=read(),r1=read(),l2=read(),r2=read(),p=id[l1],q=id[r1];if(p==q) v3[p].pb({l1,r1,l2,r2,i});else{v3[p].pb({l1,R[p],l2,r2,i}),v3[q].pb({L[q],r1,l2,r2,i});for(int j=p+1;j<q;j++) v4[j].pb({l2,r2,i});}}for(int i=1;i<=t;i++) solve(i,v1[i],v2[i],v3[i],v4[i]);for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0;
}