#include<bits/stdc++.h> using namespace std; const int N=200011; #define int long long // inline int read(){ char c; int x=0,f=0; c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } if(f==-1)return(~x+1); else return x; } int n,m; int sum,a[N],len,belong[N],kl[N],kr[N]; int zheng[N],yl[N],yr[N],num[N]; //yl,yr表示这个块内往左右延伸到多元 signed main(){ // freopen("ODT.in","r",stdin); // freopen("ODT.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++)a[i]=read(); len=sqrt(n); for(int i=1;i<=len;i++)belong[i]=1; for(int i=len+1;i<=n;i++)belong[i]=belong[i-len]+1; sum=n/len; if(n%len!=0)sum++; for(int i=1;i<=sum;i++){ kl[i]=(i-1)*len+1; kr[i]=i*len; } for(int i=1;i<=sum;i++)yr[i]=kr[i],yl[i]=kl[i]; kr[sum]=n; for(int i=1;i<=m;i++){ int l,r,c; l=read(),r=read(),c=read(); int res=0; // cout<<belong[l]<<" "<<belong[r]<<endl; if(belong[l]==belong[r]){//在同一个块内，就更新整个块 int u=belong[l]; for(int j=yr[u]+1;j<=yl[u]-1;j++)a[j]=num[u]; zheng[u]=0;num[u]=0; for(int j=l;j<=r;j++)if(a[j]==c)res++; for(int j=l;j<=r;j++)a[j]=c; yr[u]=kr[u]; yl[u]=kl[u]; } else{ //l if(zheng[belong[l]]){ int u=belong[l]; if(num[u]==c)res+=kr[u]-l+1; zheng[u]=0; yl[u]=l; for(int j=l;j<=kr[u];j++)a[j]=c; } else{ int u=belong[l]; if(yr[u]>=yl[u]-1){ for(int j=l;j<=kr[u];j++){ if(a[j]==c)res++; a[j]=c; } } else{ // if(i==28)cout<<yl[u]<<" "<<yr[u]<<" "; for(int j=l;j<=yr[u];j++){ if(a[j]==c)res++; a[j]=c; } for(int j=max(yl[u],l);j<=kr[u];j++){ if(a[j]==c)res++; a[j]=c; } for(int j=max(l,yr[u]+1);j<yl[u];j++){ if(num[u]==c)res++; a[j]=c; } yl[u]=min(yl[u],l); } // if(i==28)cout<<"l:"<<res<<" "; } //r if(zheng[belong[r]]){ int u=belong[r]; if(num[u]==c)res+=r-kl[u]+1; zheng[u]=0; yr[u]=r; for(int j=kl[u];j<=r;j++)a[j]=c; } else{ int u=belong[r]; // cout<<yl[u]<<" "<<yr[u]<<endl; if(yr[u]>=yl[u]-1){ for(int j=kl[u];j<=r;j++)if(a[j]==c)res++; for(int j=kl[u];j<=r;j++)a[j]=c; } else{ for(int j=kl[u];j<=min(yr[u],r);j++){ if(a[j]==c)res++; a[j]=c; } for(int j=yl[u];j<=r;j++){ if(a[j]==c)res++; a[j]=c; } for(int j=yr[u]+1;j<=min(r,yl[u]-1);j++){ if(num[u]==c)res++; a[j]=c; } yr[u]=max(yr[u],r); } } // cout<<"r:"<<res<<" "; //zheng kuai for(int u=belong[l]+1;u<=belong[r]-1;u++){ if(zheng[u]){ if(num[u]==c)res+=kr[u]-kl[u]+1; } else{ if(yr[u]>=yl[u]-1){ for(int j=kl[u];j<=kr[u];j++)if(a[j]==c)res++; } else{ // cout<<"no:"<<" "<<yr[u]<<" "<<yl[u]<<" "; for(int j=kl[u];j<=yr[u];j++)if(a[j]==c)res++; for(int j=yl[u];j<=kr[u];j++)if(a[j]==c)res++; for(int j=yr[u]+1;j<=yl[u]-1;j++)if(num[u]==c)res++; } } zheng[u]=1; num[u]=c; yl[u]=kr[u]+1; yr[u]=kl[u]-1; } } cout<<res<<endl; } }