矩阵写法没过样例求条

#include<bits/stdc++.h>
#define int long long
#define ls (cur<<1)
#define rs (cur<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=1e6+5;
int n,q,a[N],lst[N],ans[N];
struct node{int id,x;};
vector<node>v[N];
struct mat{
	int a11,a12,a13,a21,a22,a23,a33;
	mat operator+(const mat&x)const{
		mat y;
		y.a11=y.a12=y.a13=y.a21=y.a22=y.a23=y.a33=0;
		y.a11=a11+x.a11,y.a12=a12+y.a12,y.a13=a13+y.a13;
		return y;
	}
	mat operator*(const mat&x)const{
		mat y;
		y.a11=y.a12=y.a13=y.a21=y.a22=y.a23=y.a33=0;
		y.a11=a11*x.a11+a12*x.a21;
		y.a12=a11*x.a12+a12*x.a22;
		y.a13=a11*x.a13+a12*x.a23+a13*x.a33;
		y.a21=a21*x.a11+a22*x.a21;
		y.a22=a21*x.a12+a22*y.a22;
		y.a23=a21*x.a13+a22*x.a23+a23*x.a33;
		y.a33=a33*x.a33;
		return y;
	}
	bool operator==(const mat&x)const{
		return !(a11^x.a11||a12^x.a12||a13^x.a13||a21^x.a21||a22^x.a22||a23^x.a23||a33^x.a33);
	}
}tr[N<<2],tg[N<<2],o1,o2,b1,b2;
void ps(int cur){return tr[cur]=tr[ls]+tr[rs],void();}
void bd(int cur,int l,int r){
	tg[cur]=o2;
	if(l==r)return tr[cur]=o1,void();
	return bd(ls,l,mid),bd(rs,mid+1,r),void();
}
void ad(int cur,mat t){return tr[cur]=tr[cur]*t,tg[cur]=tg[cur]*t,void();}
void pd(int cur){
	if(tg[cur]==o2)return;
	ad(ls,tg[cur]),ad(rs,tg[cur]);
	return tg[cur]=o2,void();
}
void upd(int cur,int l,int r,int x,int y,int op){
	if(l>y||r<x)return;
	if(x<=l&&r<=y)return ad(cur,(op==1?b1:b2)),void();
	return pd(cur),upd(ls,l,mid,x,y,op),upd(rs,mid+1,r,x,y,op),ps(cur),void();
}
int qy(int cur,int l,int r,int x,int y){
	if(l>y||r<x)return 0;
	if(x<=l&&r<=y)return tr[cur].a13;
	return pd(cur),qy(ls,l,mid,x,y)+qy(rs,mid+1,r,x,y);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	o1.a11=1,o2.a11=o2.a22=o2.a33=1;
	b1.a12=b1.a13=b1.a21=b1.a33=1,b2.a11=b2.a22=b2.a23=b2.a33=1;
	cin>>q,bd(1,1,n);
	for(int i=1,l,r;i<=q;i++)cin>>l>>r,v[r].push_back({i,l});
	for(int i=1;i<=n;i++){
		upd(1,1,n,lst[a[i]]+1,i,1);
		if(lst[a[i]])upd(1,1,n,1,lst[a[i]],2);
		lst[a[i]]=i;
		for(auto it:v[i])ans[it.id]=qy(1,1,n,it.x,i);
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
	return 0;
}