View Code of Problem 1067

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> mp;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;
const int MAXM=MAXN<<1;
int LH[MAXN],RH[MAXN],L[MAXN],R[MAXN],O[MAXN],X[MAXN];
vector<mp> vec;

int heap[MAXN],l[MAXM],r[MAXM],h[MAXM],v[MAXM],f[MAXN];
int tot;
int find(int x){ return f[x]==x?x:f[x]=find(f[x]); }
int merge(int x,int y){
	if(x==0) return y;
	if(y==0) return x;
	if(v[x]>v[y]) swap(x,y);
	r[x]=merge(r[x],y);
	if(h[l[x]]<h[r[x]]) swap(l[x],r[x]);
	h[x]=h[r[x]]+1;
	return x;
}
void Union(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y) return ;
	f[y]=x;
	if(x<y){
		RH[x]=RH[y];
		L[R[x]]=x;
		R[x]=R[y];
	}
	else{
		LH[x]=LH[y];
		R[L[x]]=x;
		L[x]=L[y];
	}
	heap[x]=merge(heap[x],heap[y]);
	X[x]+=X[y];
	O[x]+=O[y];
}
int pop(int x){
	return merge(l[x],r[x]);
}

int main(){
	int T,kase=0;
	scanf("%d",&T);
	while(T--){
		int n,m,ans=0;
		scanf("%d%d",&n,&m);
		LH[1]=RH[n]=INF;
		L[n]=n-1;
		for(int i=1;i<n;++i){
			scanf("%d",&RH[i]);
			LH[i+1]=RH[i];
			L[i]=i-1;
			R[i]=i+1;
		}
		vec.clear();
		memset(heap,0,sizeof(heap));
		tot=0;
		while(m--){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			if(z){
				vec.push_back(mp(y+1,x));
			}
			else{
				++ans;
				v[++tot]=y;
				l[tot]=r[tot]=h[tot]=0;
				heap[x]=heap[x]?merge(heap[x],tot):tot;
			}
		}
		for(int i=1;i<=n;++i) f[i]=i;
		sort(vec.begin(),vec.end());
		for(int i=1;i<=n;++i) O[i]=X[i]=0;
		for(int i=0;i<vec.size();++i){
			int x=find(vec[i].second);
			int y=vec[i].first;
			while(y>LH[x]){
				Union(x,L[x]);
				x=find(x);
			}
			while(y>RH[x]){
				Union(x,R[x]);
				x=find(x);
			}
			while(heap[x]!=0&&v[heap[x]]<y){
				heap[x]=pop(heap[x]);
				++X[x];
			}
			if(++O[x]>=X[x]){
				ans+=(O[x]-X[x]);
				O[x]=X[x]=0;
			}
		}
		printf("Case #%d: %d\n",++kase,ans);
	}
}