Many Lists

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
There are N sets numbered 1 to N, all initially empty.
Your task is to perform two kinds of queries:
 0 l r x : add the number x to all the sets numbered from l to r. (Note that a set, by definition, can never contain duplicate elements. So a number is only added to a set if it was not already present.)
 1 q : output the size of the set numbered q.
Input
The first line contains two space separated integers N and M denoting the number of lists and the number of the queries respectively.
The following M lines describe the queries. Each of these lines describes exactly one query in the format specified above.
Output
For each query of type 1, output the size of the specified set.
Constraints
 Subtask 1 (14 points): 1 ≤ N, M ≤ 100
 Subtask 2 (25 points): 1 ≤ N, M ≤ 1000
 Subtask 3 (61 points): 1 ≤ N, M ≤ 2.5 * 10^{5}
 1 ≤ l ≤ r ≤ N
 1 ≤ q, x ≤ N
Example
Input: 5 5 0 2 4 4 0 3 5 5 0 1 5 5 1 5 1 3 Output: 1 2
Explanation
Have a look at the sets during the operations:
 Initially, all the sets are empty: {{}, {}, {}, {}, {}}.
 In the first query we add 4 to sets numbered 2 to 4 to get: {{}, {4}, {4}, {4}, {}}.
 In the second query we add 5 to the sets numbered 3 to 5 to get: {{}, {4}, {4, 5}, {4, 5}, {5}}.
 In the third query we add 5 to all the sets to get: {{5}, {4, 5}, {4, 5}, {4, 5}, {5}}.
 The 5^{th} set is {5}, its size is 1.
 The 3^{rd} set is {4, 5}, and its size is 2.
Author:  xcwgf666 
Tester:  logic_iu 
Editorial  http://discuss.codechef.com/problems/MANYLIST 
Tags  hard, ltime28, segmenttree, sets, xcwgf666 
Date Added:  24082015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 