#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+7;
int seg1[N<<2],seg2[N<<2],a[N],n,m;
void update1(int p,int l,int r,int x,int v){
	if(l==r){
		seg1[p]=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) update1(p<<1,l,mid,x,v);
	if(x>mid) update1(p<<1|1,mid+1,r,x,v);
	seg1[p]=seg1[p<<1]+seg1[p<<1|1];
}
void update2(int p,int l,int r,int x,int v){
	if(l==r){
		seg2[p]=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) update2(p<<1,l,mid,x,v);
	if(x>mid) update2(p<<1|1,mid+1,r,x,v);
	seg2[p]=seg2[p<<1]+seg2[p<<1|1];
}
int query1(int p,int l,int r,int x,int y){
	//cout<<"p="<<p<<endl;
	if(x<=l&&r<=y){
		return seg1[p];
	} 
	int mid=l+r>>1,sum=0;
	if(x<=mid) sum+=query1(p<<1,l,mid,x,y);
	if(y>mid) sum+=query1(p<<1|1,mid+1,r,x,y);
	return sum;
}
int query2(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return seg2[p];
	} 
	int mid=l+r>>1,sum=0;
	if(x<=mid) sum+=query2(p<<1,l,mid,x,y);
	if(y>mid) sum+=query2(p<<1|1,mid+1,r,x,y);
	return sum;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==1) update1(1,1,n,i,1);
		if(a[i]==2) update2(1,1,n,i,1);
	}
	while(m--){
		int op;
		cin>>op;
		if(op==1){
			int l,r,ans;
			cin>>l>>r;
			int q1=query1(1,1,n,l,r);
			int q2=query2(1,1,n,l,r);
			int len=r-l+1;
			ans=(q1*q2*3+q1*(len-q2-q1)*2+q1*(q1-1)+(len-q1-1)*(len-q1)/2);
			cout<<ans<<endl;
		}
		if(op==2)
		{
			int k,x;
			cin>>k>>x;
			if(x==1) update1(1,1,n,k,1),update2(1,1,n,k,0);
			if(x==2) update2(1,1,n,k,1),update1(1,1,n,k,0);
			else{
				update1(1,1,n,k,0);
				update2(1,1,n,k,0);
			}
		}
	}
	return 0;
}