CodeForces - 981 G Magic multisets (선분 트 리 + set 유지보수 구간 정보)

G. Magic multisets
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
In the School of Magic in Dirtpolis a lot of interesting objects are studied on Computer Science lessons.
Consider, for example, the magic multiset. If you try to add an integer to it that is already presented in the multiset, each element in the multiset duplicates. For example, if you try to add the integer 22 to the multiset {1,2,3,3}{1,2,3,3}, you will get {1,1,2,2,3,3,3,3}{1,1,2,2,3,3,3,3}.
If you try to add an integer that is not presented in the multiset, it is simply added to it. For example, if you try to add the integer 44 to the multiset {1,2,3,3}{1,2,3,3}, you will get {1,2,3,3,4}{1,2,3,3,4}.
Also consider an array of nn initially empty magic multisets, enumerated from 11 to nn.
You are to answer qq queries of the form "add an integer xx to all multisets with indices l,l+1,…,rl,l+1,…,r" and "compute the sum of sizes of multisets with indices l,l+1,…,rl,l+1,…,r". The answers for the second type queries can be large, so print the answers modulo 998244353998244353.
Input
The first line contains two integers nn and qq (1≤n,q≤2⋅1051≤n,q≤2⋅105) — the number of magic multisets in the array and the number of queries, respectively.
The next qq lines describe queries, one per line. Each line starts with an integer tt (1≤t≤21≤t≤2) — the type of the query. If tt equals 11, it is followed by three integers ll, rr, xx (1≤l≤r≤n1≤l≤r≤n, 1≤x≤n1≤x≤n) meaning that you should add xx to all multisets with indices from ll to rrinclusive. If tt equals 22, it is followed by two integers ll, rr (1≤l≤r≤n1≤l≤r≤n) meaning that you should compute the sum of sizes of all multisets with indices from ll to rr inclusive.
Output
For each query of the second type print the sum of sizes of multisets on the given segment.
The answers can be large, so print them modulo 998244353998244353.
Examples
input
Copy

4 4
1 1 2 1
1 1 2 2
1 1 4 1
2 1 4

output
Copy

10

input
Copy

3 7
1 1 1 3
1 1 1 3
1 1 1 2
1 1 1 1
2 1 1
1 1 1 2
2 1 1

output
Copy

4
8

Note
In the first example after the first two queries the multisets are equal to [{1,2},{1,2},{},{}][{1,2},{1,2},{},{}], after the third query they are equal to [{1,1,2,2},{1,1,2,2},{1},{1}][{1,1,2,2},{1,1,2,2},{1},{1}].
In the second example the first multiset evolves as follows:
{}→{3}→{3,3}→{2,3,3}→{1,2,3,3}→{1,1,2,2,3,3,3,3}{}→{3}→{3,3}→{2,3,3}→{1,2,3,3}→{1,1,2,2,3,3,3,3}.
 
 
문제 풀이 방향: 먼저 N 개의 집합 크기 를 하나의 선분 트 리 로 유지 하고 이 선분 트 리 는 구간 곱셈, 구간 덧셈, 구간 구 화 를 지원 합 니 다.관건 은 업데이트 작업 이다.언제 구간 이 * 2 또는 + 1 이 고 어떤 구간 이 * 2 또는 + 1 이 어야 합 니까?
그러면 우 리 는 모든 집합 안에 어떤 숫자 가 있 는 지 지 켜 야 한다. 만약 우리 가 주석 나무 로 발견 하 는 것 이 좀 어렵다 면.그럼 폭력 을 생각해.
매번 구간 을 갱신 할 때마다 우 리 는 모든 집합 을 폭력 적 으로 조회 하여 그 수가 존재 하 는 지 확인 하 는데, 이렇게 하 는 것 은 분명히 바람 직 하지 않다.
그러면 우 리 는 다른 방식 으로 생각 하 는 것 도 좋 습 니 다. 우 리 는 하나의 집합 배열 S [i] 로 i 번 째 숫자 가 어떤 구간 에 나 타 났 는 지 유지 합 니 다.
우리 가 업데이트 작업 이 있 을 때 우 리 는 S [w] 집합 을 직접 조회 한 다음 에 이 집합 안의 모든 구간 이 조회 한 [L, R] 과 교차 하 는 것 이 있 는 지 판단 하고 교차 하 는 부분 은 * 2 로 교차 하지 않 는 부분 은 + 1 로 한다. 이런 방법 은 매우 좋 은 것 같 지만 최 악의 복잡 한 것 은 매우 크다.그래서 우 리 는 어떤 구간 이 교차 하 는 지 효율적으로 조회 해 야 한다.그래서 S [w] 집합 은 구간 을 저장 할 수 없고 구간 의 점 을 저장 해 야 합 니 다. 그러면 우 리 는 set 자체 의 lower 를 사용 할 수 있 습 니 다.bound 작업, 효율 적 인 업데이트 구간 과 집합.코드 조작 을 구체 적 으로 보다.
set 유지보수 구간 을 배 워 보 세 요.
 
 

#include 
#include 
#include 
#include 
#include 
#include 
#include