Rt . 我的思路是 , 线段树每个节点维护每个数的个数 , 以及 $A_i = x , A_j = y , i<j$ 的所有有序对 , 记为 $calc[x][y]$

为什么会 挂 ? 而且 , 题解为什么只维护逆序对 ?

code :

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
struct Segment {
	int tg,tag[4],cnt[4],calc[4][4];
}t[MAXN<<2];
int n,m,Cnt[4],Calc[4][4],v[MAXN],a[MAXN]; //a[i] i->a[i]
void update_point(int k) {
	memset(Cnt,0,sizeof(Cnt)),memset(Calc,0,sizeof(Calc));
	ffor(i,0,2) Cnt[i]=0;
	ffor(i,0,2) ffor(j,0,2) Calc[i][j]=0;
	ffor(i,0,2) Cnt[a[i]]+=t[k].cnt[i];
	ffor(i,0,2) ffor(j,0,2) Calc[a[i]][a[j]]+=t[k].calc[i][j];
	ffor(i,0,2) t[k].cnt[i]=Cnt[i];
	ffor(i,0,2) ffor(j,0,2) t[k].calc[i][j]=Calc[i][j];
	return ;
}
Segment merge(Segment a,Segment b) {
	memset(Cnt,0,sizeof(Cnt)),memset(Calc,0,sizeof(Calc));
	ffor(i,0,2) Cnt[i]=a.cnt[i]+b.cnt[i];
	ffor(i,0,2) ffor(j,0,2) Calc[i][j]=a.calc[i][j]+b.calc[i][j];
	ffor(i,0,2) ffor(j,0,2) Calc[i][j]+=a.cnt[i]*b.cnt[j];
	Segment res; res.tg=res.tag[0]=res.tag[1]=res.tag[2]=0;
	ffor(i,0,2) res.cnt[i]=Cnt[i];
	ffor(i,0,2) ffor(j,0,2) res.calc[i][j]=Calc[i][j];
	return res;
}	
void push_down(int k,int l,int r) {
	if(t[k].tg) {
		ffor(i,0,2) a[i]=t[k].tag[i];
		update_point(k<<1),update_point(k<<1|1);
		t[k<<1].tg=t[k<<1|1].tg=1; ffor(i,0,2) t[k<<1].tag[i]=t[k<<1|1].tag[i]=t[k].tag[i];
		ffor(i,0,2) t[k].tag[i]=0; t[k].tg=0;
		return ;
	}
	return ;
}
void update(int k,int l,int r,int x,int y,int s,int T,int R) {
	if(x<=l&&r<=y) {
		t[k].tg=1; a[0]=s,a[1]=T,a[2]=R;
		t[k].tag[0]=s,t[k].tag[1]=T,t[k].tag[2]=R;
		update_point(k); 
		return ;
	}
	push_down(k,l,r);
	int mid=l+r>>1;
	if(x<=mid) update(k<<1,l,mid,x,y,s,T,R);
	if(y>mid) update(k<<1|1,mid+1,r,x,y,s,T,R);
	t[k]=merge(t[k<<1],t[k<<1|1]);
	return ;
}
Segment Query(int k,int l,int r,int x,int y) {
	if(x<=l&&r<=y) return t[k];
	push_down(k,l,r);
	int mid=l+r>>1;
	if(y<=mid) return Query(k<<1,l,mid,x,y);
	if(x>mid) return Query(k<<1|1,mid+1,r,x,y);
	return merge(Query(k<<1,l,mid,x,y),Query(k<<1|1,mid+1,r,x,y));
}
void build(int k,int l,int r) {
	if(l==r) {t[k].cnt[v[l]]=1; return ;}
	int mid=l+r>>1; 
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	t[k]=merge(t[k<<1],t[k<<1|1]);
	return ;
}
signed main() {
	cin>>n>>m;
	ffor(i,1,n) cin>>v[i];
	build(1,1,n);
	ffor(i,1,m) {
		int op;cin>>op;
		if(op==1) {
			int l,r;cin>>l>>r;
			Segment st=Query(1,1,n,l,r);
			int ans=st.calc[1][0]+st.calc[2][0]+st.calc[2][1];
			cout<<ans<<'\n';
		}
		else {
			int l,r,s,t,u;cin>>l>>r>>s>>t>>u;
			update(1,1,n,l,r,s,t,u);	
		}
	}
	return 0;
}