topic

click here see topic.

analyze

First, solving this problem is equivalent to figuring out when each operation will be "completely popped", that is, when there will be no weight left in the queue for this operation.

For the operation of \(l=r\): after this operation, adding \(a_l\) weights to the queue \(l\) will cause the weights of the operation to be popped up.

For the operation of \(l<r\): Obviously, we can think of it as the maximum value of the time that the operation is popped in each single queue in \([l,r]\) . The problem is that we can't enumerate each queue to calculate, how can we do it?

Note that this method of calculation implies that we can group the queues arbitrarily for the calculation. Therefore, one method is to "block" and split it into \ (O(\sqrt n) \) intervals; Another method is "segment tree" or "tree group", which is divided into \ (O(n) \) intervals, and each operation covers at most \ (O(\log n) \) intervals

All the operation ranges are attached to the segment tree nodes, and all queries are processed offline in DFS order. All queries are now global queries, and the "pop" time is monotonic with the "join" time. Therefore, we can make a double pointer according to time for all queries in a certain interval, and the later pointer maintains "when will it be popped". At this point we can focus on modifying:

1. Modification of full coverage interval: We need to know the modification time, so we can use a segment tree (or tree-like array) to maintain the time.

2. Modification of some intersecting intervals: In this part, we need to consider both time and location. However, according to the splitting method of the line segment tree, the total number of modifications that partially intersect is \(O(n\log n)\), which is the same time complexity as the line segment tree. Therefore, for each interval, such a modification is violently saved, and then added to the two-pointer process for consideration. This part also requires another segment tree to maintain the sequence.

Doing this is exactly \(O(n\log^2n)\) . Due to the repeated nesting of line segment trees, there is no direct correlation between complexity and running efficiency 😓.

Remark.

The first simple observation leads to the key thinking: the queues are independent of each other, the answers can be merged quickly, so we can process the queues in groups. Of course, this result can also be obtained from the perspective of general data structures.

Grass, why not think about line segment trees?

The difference from the line segment tree is that we do not strictly follow the structure of the line segment tree, but regard the line segment tree as a special interval division method. This division has nice properties:

1. The number of intervals is \(O(n)\).

2. A modification goes through at most \(O(\log n)\) line segment tree nodes (roughly estimated, the constant is about \(4\)).

3. Although the intervals may overlap, according to the tree structure, the intervals are either included or not intersected.

4. The query attached to the node of the segment tree can be regarded as a global query on the interval.

Now, we can process interval by interval. Moreover, the interval that contains the relationship tends to have an impact, and DFS against the tree can help us deal with this impact.

code

#include <cstdio>
#include <vector>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int MAXN = 1e5 + 5;

template<typename _T>
void read( _T &x ) {
	x = 0; char s = getchar(); bool f = false;
	while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	if( f ) x = -x;
}

template<typename _T>
void write( _T x ) {
	if( x < 0 ) putchar( '-' ), x = -x;
	if( 9 < x ) write( x / 10 );
	putchar( x % 10 + '0' );
}

template<typename _T>
inline _T Max( const _T &a, const _T &b ) {
	return a > b ? a : b;
}

template<typename _T>
inline _T Abs( const _T &a ) {
	return a < 0 ? -a : a;
}

std :: vector<int> opt[MAXN];

int app[MAXN], ans = 0;

int qL[MAXN], qR[MAXN], qX[MAXN], ddl[MAXN];
int A[MAXN];

int N, M;

namespace Time {
	int su[MAXN];

	inline void Down( int &x ) { x &= x - 1; }
	inline void Up( int &x ) { x += x & ( - x ); }
	inline void Update( int x, int v ) { for( ; x <= M ; Up( x ) ) su[x] += v; }
	inline  int Query( int x ) { int ret = 0; for( ; x ; Down( x ) ) ret += su[x]; return ret; }
	inline  int Query( const int &l, const int &r ) { return Query( r ) - Query( l - 1 ); }

	inline int Search( const int &lim ) {
		int p = 0, val = 0;
		for( int k = 16 ; ~ k ; k -- )
			if( p + ( 1 << k ) <= M && val + su[p | 1 << k] < lim )
				val += su[p |= 1 << k];
		return p + 1;
	}
}

namespace Sequence {
	int mx[MAXN << 2], tag[MAXN << 2];

	inline void Upt( const int &x ) {
		mx[x] = Max( mx[x << 1], mx[x << 1 | 1] );
	}

	inline void Add( const int &x, const int &delt ) {
		mx[x] += delt, tag[x] += delt;
	}

	inline void Normalize( const int &x ) {
		if( ! tag[x] ) return ;
		Add( x << 1, tag[x] );
		Add( x << 1 | 1, tag[x] );
		tag[x] = 0;
	}

	void Build( const int &x, const int &l, const int &r ) {
		if( l > r ) return ;
		if( l == r ) { mx[x] = A[l]; return ; }
		int mid = ( l + r ) >> 1;
		Build( x << 1, l, mid );
		Build( x << 1 | 1, mid + 1, r );
		Upt( x );
	}

	void Modify( const int &x, const int &l, const int &r, const int &segL, const int &segR, const int &delt ) {
		if( segL <= l && r <= segR ) { Add( x, delt ); return ; }
		int mid = ( l + r ) >> 1; Normalize( x );
		if( segL <= mid ) Modify( x << 1, l, mid, segL, segR, delt );
		if( mid  < segR ) Modify( x << 1 | 1, mid + 1, r, segL, segR, delt );
		Upt( x );
	}

	int Query( const int &x, const int &l, const int &r, const int &segL, const int &segR ) {
		if( segL <= l && r <= segR ) return mx[x];
		int mid = ( l + r ) >> 1; Normalize( x );
		if( segR <= mid ) return Query( x << 1, l, mid, segL, segR );
		if( mid  < segL ) return Query( x << 1 | 1, mid + 1, r, segL, segR );
		return Max( Query( x << 1, l, mid, segL, segR ), Query( x << 1 | 1, mid + 1, r, segL, segR ) );
	}

	inline int Query( const int &l, const int &r ) {
		return Query( 1, 1, N, l, r );
	}

	inline void Modify( const int &segL, const int &segR, const int &delt ) {
		Modify( 1, 1, N, segL, segR, delt );
	}
}

namespace GetDDL {
	std :: vector<int> mdf[MAXN << 2];
	bool any[MAXN << 2];

	void Hang( const int &x, const int &l, const int &r, const int &segL, const int &segR, const int &qId ) {
		if( segL <= l && r <= segR ) {
			mdf[x].push_back( qId ), any[x] = true;
			return ;
		}
		int mid = ( l + r ) >> 1; mdf[x].push_back( - qId );
		if( segL <= mid ) Hang( x << 1, l, mid, segL, segR, qId );
		if( mid  < segR ) Hang( x << 1 | 1, mid + 1, r, segL, segR, qId );
	}
	
	void DFS( const int &u, const int &l, const int &r ) {
		if( mdf[u].empty() ) return ;
		int n = mdf[u].size();
		if( any[u] ) {
			int p = 0, q = 0;
			for( ; p < n ; p ++ ) {
				int tL = Abs( mdf[u][p] );
				Sequence :: Modify( qL[tL], qR[tL], +1 );
				if( mdf[u][p] > 0 ) {
					bool flg = false;
					int tR, val, pre = Time :: Query( tL - 1 );
					while( q < p ) {
						tR = Abs( mdf[u][q] );
						Sequence :: Modify( qL[tR], qR[tR], -1 ), q ++;
					}
					while( q < n ) {
						tR = Abs( mdf[u][q] );
						val = Sequence :: Query( l, r ) + pre;
						if( val <= Time :: Query( tR ) ) {
							ddl[tL] = Max( ddl[tL], Time :: Search( val ) );
							flg = true;
							break;
						}
						Sequence :: Modify( qL[tR], qR[tR], -1 ), q ++;
						if( Sequence :: Query( l, r )  + pre <= Time :: Query( tR ) ) {
							ddl[tL] = Max( ddl[tL], tR ), flg = true;
							break;
						}
					}
					if( ! flg && q == n ) {
						val = Sequence :: Query( l, r ) + pre;
						if( val <= Time :: Query( M ) )
							ddl[tL] = Max( ddl[tL], Time :: Search( val ) );
						else ddl[tL] = M + 1;
					}
				}
			}
			while( q < n ) {
				int tR = Abs( mdf[u][q] );
				Sequence :: Modify( qL[tR], qR[tR], -1 ), q ++;
			}
		}
		if( l == r ) return ;
		int mid = ( l + r ) >> 1;
		for( int i = 0 ; i < n ; i ++ ) if( mdf[u][i] > 0 ) 
			Time :: Update( mdf[u][i], +1 );
		DFS( u << 1, l, mid );
		DFS( u << 1 | 1, mid + 1, r );
		for( int i = 0 ; i < n ; i ++ ) if( mdf[u][i] > 0 ) 
			Time :: Update( mdf[u][i], -1 );
	}

	void Work() {
		Sequence :: Build( 1, 1, N );
		DFS( 1, 1, N );
	}
}

int main() {
	read( N ), read( M );
	rep( i, 1, N ) read( A[i] );
	rep( i, 1, M ) {
		read( qL[i] ), read( qR[i] ), read( qX[i] );
		GetDDL :: Hang( 1, 1, N, qL[i], qR[i], i );
	}
	GetDDL :: Work();
	rep( i, 1, M ) {
		opt[ddl[i]].push_back( qX[i] );
		int n = opt[i].size();
		rep( j, 0, n - 1 )
			ans -= ! ( -- app[opt[i][j]] );
		ans += ! ( app[qX[i]] ++ );
		write( ans ), putchar( '\n' );
	}
	return 0;
}