分块套树状数组维护二维带修
修改和查询都是
cpp
struct DivideFenwick{
vector<vector<int>> c;
vector<int> L,R,be,A;
int m,tot,block;
void init(int n,int m){
block=sqrt(n)+1;
tot=(n+block-1)/block;
this->m=m;
c=vector<vector<int>>(block+1,vector<int>(m+1,0));
L.assign(tot+1,0);
R.assign(tot+1,0);
be.assign(n+1,0);
A.assign(n+1,INF);
for(int i=1;i<=tot;i++){
L[i]=(i-1)*block+1,R[i]=min(i*block,n);
for(int j=L[i];j<=R[i];j++)be[j]=i;
}
}
void add(int x,int y,int v){//a[x][y]=>v
if(v==1)A[x]=y;
else A[x]=INF;
x=be[x];
for(int i=x;i<=tot;i+=i&-i){
for(int j=y;j<=m;j+=j&-j){
c[i][j]+=v;
}
}
}
int query(int x,int y){// 查询1<=x_1<=x,1<=y_1<=y的对数(x_1,y_1)
if(x<=0||y<=0)return 0;
int id=be[x];
int res=0;
for(int i=L[id];i<=x;i++){
res+=A[i]<=y;
}
for(int i=id-1;i>0;i&=i-1){
for(int j=y;j>0;j&=j-1){
res+=c[i][j];
}
}
return res;
}
} t;
void solve(){
int n,m;
cin>>n>>m;
vector<int> a(n+1),b(n+1);
vector<int> X(n+1),Y(n+1);
for(int i=1;i<=n;i++)cin>>a[i],X[a[i]]=i;
for(int i=1;i<=n;i++)cin>>b[i],Y[b[i]]=i;
t.init(n,n);
for(int i=1;i<=n;i++)t.add(X[i],Y[i],1);
auto getsum=[&](int x1,int x2,int y1,int y2){
return t.query(x2,y2)-t.query(x1-1,y2)-t.query(x2,y1-1)+t.query(x1-1,y1-1);
};
while(m--){
int op,x1,x2,y1,y2;
cin>>op;
if(op==1){
cin>>x1>>x2>>y1>>y2;
cout<<getsum(x1,x2,y1,y2)<<"\n";
}
else{
cin>>x1>>x2;
int v1=b[x1],v2=b[x2];
t.add(X[v1],Y[v1],-1);
t.add(X[v2],Y[v2],-1);
swap(Y[v1],Y[v2]);
swap(b[x1],b[x2]);
t.add(X[v1],Y[v1],1);
t.add(X[v2],Y[v2],1);
}
}
}