set 内置函数已经 SPFA 了

#define IT set<node>::iterator
int check(int l,int r,ll val=1){
int ans=0;
IT itl = split(l),itr = split(r+1);
for (; itl != itr; ++itl) if(itl->v==val) ans++;
return ans;
}


int check(int l,int r,ll val=1){
int ans=0;
IT itl = split(l),itr = split(r+1);
for (; itl != itr; ++itl) if(itl->v==val) ans+=itl->r-itl->l+1;
return ans;
}


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int l,r;
mutable ll v;
node(int L, int R=-1, ll V=0):l(L), r(R), v(V) {}
bool operator<(const node& o) const{return l < o.l;}
};
set<node> ODT;
#define IT set<node>::iterator
IT split(int pos){
IT it = ODT.lower_bound(node(pos));
if (it != ODT.end() && it->l == pos) return it;
--it;
int L = it->l, R = it->r;
ll V = it->v;
ODT.erase(it);
ODT.insert(node(L, pos-1, V));
return ODT.insert(node(pos, R, V)).first;
}
int check(int l,int r,ll val=1){
int ans=0;
IT itl = split(l),itr = split(r+1);
for (; itl != itr; ++itl) if(itl->v==val) ans+=itl->r-itl->l+1;
return ans;
}
void assign(int l, int r, ll val=0){
IT itl = split(l),itr = split(r+1);
ODT.erase(itl, itr);
ODT.insert(node(l, r, val));
}
int main(){
int n,a;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a);
ODT.insert(node(i,i,a));
}for(int i=1;i<=n;i++){
int l,r;
ll c;
scanf("%d%d%lld",&l,&r,&c);
printf("%d\n",check(l,r,c));
assign(l,r,c);
}//system("pause");
}


Sora。对一切怀着热诚的心。