模擬賽 T3，好像是 lxl 的題。

題意

給定一個 \(n\times n\) 的二維平面，有 \(n\times n\) 個整點，每個整點都有權值，初始為 \(0\)。
有 \(n\) 次操作，每次操作給定一個矩形 \(x_1,x_2,y_1,y_2\) 和一個值 \(v\)，把這個矩形內(nèi)的所有點的權值跟 \(v\) 取 \(\max\)。
在這 \(n\) 次操作之后，有 \(m\) 次詢問，每次詢問查詢一個矩形的權值和。

數(shù)據(jù)范圍： \(1\le n,m\le 10^5，1\le v \le n\)。

題解

直接考慮分塊，把 \(x\) 軸分成 \(O(\sqrt{n})\) 個塊，對于每個塊內(nèi)部會有一些零散的修改/查詢，以及一些完整跨過這個塊的修改/查詢，下面對每個塊單獨考慮。

我們把這個塊內(nèi)部零散的修改/查詢涉及到的 \(y\) 坐標離散化，設離散化后的 \(y\) 一共有 \(tot\) 個，那么所有塊的 \(tot\) 之和是 \(O(n+m)\) 級別的。
我們稱離散化之后的網(wǎng)格的每個點為一個格子，顯然一個格子在原平面中代表一個在 \(x\) 軸方向上長為 \(1\) 的矩形。
因為修改都是在查詢之前的，所以我們可以把修改離線下來按照 \(v\) 從大到小排序，這樣的好處是每個點都只會被覆蓋一次。

• 對散塊修改：
  我們對每個 \(x\) 都開一個大小為 \(tot\) 的并查集，維護這個 \(x\) 坐標上哪些離散化之后的 \(y\) 還沒有被覆蓋，然后對散塊的每個 \(x\) 都用并查集找到還沒被覆蓋的 \(y\) 進行覆蓋。同時我們要對于每個離散化之后的 \(y\) 去維護有多少個真實的 \(x\) 已經(jīng)被修改了（記作 \(c_1\)），以及這些修改操作的 \(v\) 之和（記作 \(s_1\)）。

• 對整塊修改：
  我們開一個大小為 \(n\) 的并查集維護哪些真實的 \(y\) 還沒有被修改，然后找到所有還沒被修改的 \(y\) 進行修改。同時我們要對于每個離散化之后的 \(y\) 去維護有多少個真實的 \(y\) 已經(jīng)被修改了（記作 \(c_2\)），以及這些修改操作的 \(v\) 之和（記作 \(s_2\)）。

• 對散塊查詢：
  對于散塊查詢，我們只需要提前處理出離散化之后的網(wǎng)格的二維前綴和即可。具體的，當我們進行散塊修改時對 \((x,y)\) 這個格子（\(y\) 是離散化之后的）進行了覆蓋，那么在這次操作之前，它里面已經(jīng)有 \(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;
}