link

这里有一种很奇怪的线段树做法。

开O2用时仅443ms。

怎么感觉这个线段树做法不太对。所以此题到底能不能用线段树。

如果确实不对的话有没有什么卡掉的办法。

//writer:Oier_szc

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,Empty=-1e18;
int n;
int a[N]; 
int tr[N<<2];
void fa_change(int u)
{
	if(tr[u<<1]!=tr[u<<1|1]) tr[u]=Empty;
	else tr[u]=tr[u<<1];
}
void push_down(int u)
{
	if(tr[u]==Empty) return;
	tr[u<<1]=tr[u];
	tr[u<<1|1]=tr[u];
}
void build(int u,int l,int r)
{
	tr[u]=Empty;
	if(l==r)
	{
		tr[u]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	fa_change(u);
}
void update(int u,int l,int r,int L,int R,int c)
{
	if(tr[u]==c) return;
	if(L<=l&&r<=R)
	{
		tr[u]=c;
		return;
	}
	push_down(u);
	int mid=l+r>>1;
	if(L<=mid) update(u<<1,l,mid,L,R,c);
	if(R>mid) update(u<<1|1,mid+1,r,L,R,c);
	fa_change(u);
}
int query(int u,int l,int r,int L,int R,int c)
{
	if(tr[u]!=Empty)
	{
		if(tr[u]==c) 
		{
			return min(r,R)-max(l,L)+1;
		}
		else return 0;
	}
	push_down(u);
	int mid=l+r>>1,res=0;
	if(L<=mid) res+=query(u<<1,l,mid,L,R,c);
	if(R>mid) res+=query(u<<1|1,mid+1,r,L,R,c);
	return res;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	int l,r,c;
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld%lld",&l,&r,&c);
		printf("%lld\n",query(1,1,n,l,r,c));
		update(1,1,n,l,r,c);
	}
	return 0;
}