Problem proposer: kyopro_friends

This problem can be solved with a data structure called Segment Tree Beats, which is an advanced version of a segment tree.

Attempt to solve with lazy segment tree

Consider solving this problem with a lazy segment tree. (Among several variants of implementation of lazy segment trees, our explanation will be based on one in AtCoder Library(ACL).)

You might naturally come up with the following structure at first:

• Each node maintains:
  • the maximum number of elements \(M\) within the corresponding segment, and
  • the number of sets \(C\) that achieve the maximum within the corresponding segment.
• Each mapping maintains:
  • \((a,b)\) when the mapping is represented as \(f(x)=(x \setminus a)\cup b\).

If you decide to store data this way, we can define op, e, id, and composition, while we cannot appropriately define mapping.

Typically, hen we try to solve problems using (lazy) segment trees, we think of maintaining more information in nodes; however, in this problem, we cannot resolve the issue without worsening the computational complexity.

Idea of Segment Tree Beats

The essential idea of Segment Tree Beats is: if we cannot compute mapping just from \(f\) and \(x\), we propagate the function \(f\) on the node to children nodes and process mapping recursively, and then compute the self node by applying op on its children. This runs fast as long as cases where mapping cannot be computed just from \(f\) and \(x\) occur not so many times.

Solution of this problem

Define the data structure as follows:

• Each node maintains:
  • the union \(O\) of the sets within the segment
  • the intersection \(A\) of the sets within the segment
  • the maximum size \(M\) of the sets within the segment
  • the number of sets \(C\) that achieve the maximum within the segment
• Each mapping maintains:
  • \((a,b)\) when the mapping is represented as \(f(x)=(x \setminus a)\cup b\).
• mapping succeeds when:
  • \((O \setminus A)\cap (a \cup b)=\emptyset\).
    • Intuitively, this means that every element that is removed or added is either contained in all sets, or not contained in any sets, within the segment.

By defining this way, the size of \(O\setminus A\) decreases every time mapping fails. Also, each query increases the size of \(O\setminus A\) of \(O(\log N)\) sets by one each. Therefore, mapping fails a total of \(O(N \max x+Q\log N)\) times, allowing us to process the entire queries with a total of \(O((N+Q)\log N + N\max x)\) operations on the segment tree.

By storing the sets as a bit sequence, set operations can be done in \(O(1)\) time. Therefore, the problem can be solved in \(O((N+Q)\log N + N\max x)\) time.

Sample code (C++ / Only the definition of the data structure and the implementation of the functions)

using ll=long long;
struct S{
	// aaa=\cap S_i, ooo=\cup S_i
	// max=\max(#S_i), cnt=#{i|#S_i=max}
	ll aaa,ooo;
	int max,cnt;
	bool fail;
};
struct F{
	// f(x)=(x \cap aaa) \cup ooo;
	ll aaa,ooo;
};
S e(){
	return{-1,0,0,0,false};
}
F id(){
	return{-1,0};
}
S op(S x,S y){
	S ret;
	ret.aaa=x.aaa&y.aaa;
	ret.ooo=x.ooo|y.ooo;
	if(x.max>y.max){
		ret.max=x.max;
		ret.cnt=x.cnt;
	}else if(x.max<y.max){
		ret.max=y.max;
		ret.cnt=y.cnt;
	}else{
		ret.max=x.max;
		ret.cnt=x.cnt+y.cnt;
	}
	ret.fail=false;
	return ret;
}
S mapping(F f,S x){
	if((x.ooo^x.aaa)&(~f.aaa|f.ooo)){
		//fail
		return {0,0,0,0,true};
	}
	S ret=x;
	ret.max-=__builtin_popcountll(ret.aaa&~f.aaa);
	ret.aaa&=f.aaa;
	ret.ooo&=f.aaa;
	ret.max+=__builtin_popcountll(~ret.ooo&f.ooo);
	ret.aaa|=f.ooo;
	ret.ooo|=f.ooo;
	return ret;
}
F composition(F g,F f){
	F ret;
	ret.aaa=f.aaa&g.aaa;
	ret.ooo=(f.ooo&g.aaa)|g.ooo;
	return ret;
}

// atcoder::lazy_segtree のメンバ関数 all_apply を以下のように変更
void all_apply(int k, F f) {
    d[k] = mapping(f, d[k]);
    if (k < size) {
        lz[k] = composition(f, lz[k]);
        if (d[k].fail) push(k), update(k);  // <-- add
    }
}

References

• atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats (“Adding just one line to atcoder::lazy_segtree to implement abstracted Segment Tree Beats”)
  Article by hitonanode, Japanese
• A simple introduction to “Segment tree beats”
  First introduction of Segment Tree Beats, English
• ABC256Ex editorial
  An official editorial for a problem that can be solved with Segment Tree Beats, authored by Nyaan

Alternative solution without Segment Tree Beats

Consider defining a lazy segment tree that stores an integer sequence, is capable of retrieving the maximum value and the number of its occurrences, and supports segment-wise addition.

If you can enumerate the segments where elements are actually inserted or removed by a query operation, we can perform operations against them to solve the problem. For example, if a query asks to insert \(x\) to \(S_3,\ldots,S_{12}\), when \(x\) is already contained in \(S_5,S_6,S_{10}\), only the segments \([3,4],[7,9],[11,12]\) are genuinely affected by the query; by performing a segment-addition against each of them, the query can be processed only with lazy segment trees described above.

To achieve it, prepare \(60\) lazy segment trees that store a binary sequence, are capable of querying whether all the values within the segment is 0/1 or not, and support segment-wise assignments. The segments that are actually affected can be enumerated by performing a binary search on this lazy segment tree.

Due to the number of positions where adjacent elements have different value within the \(60\) segment trees, we see that the number of segments to be operated is bounded by \(O(Q)\). Hence, the problem has been solved in a total of \(O(Q\log N+N\max x)\) time.

On implementation, we can somehow define bulk operations to represent them as a single lazy segment tree.

This alternative solution is by a tester sheyasutaka.