Painting the Boxes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Anup has N boxes. He painted them.
He wants to pick W adjacent boxes and give it to Suraj on his birthday. He wants all the W boxes he gifts to be of same colour. Anup repaints some of the boxes, and asks how many ways are there to gift W boxes to Suraj. Can you please help him out?
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a two integers N denoting the number of boxes and W denoting the number of adjacent boxes that he wants to gift Suraj. The second line contains N space-separated integers A1, A2, ..., AN denoting the initial colours of the boxes.
- Third line of each test case contains a single integer Q, denoting the number of times Anup repainted a box. Q lines follow, each containing two integers Posi and Coli meaning that Posth box was repainted with colour Col.
- After each repainting query, output the number of ways Anup can gift Suraj W adjacent boxes of the same colour.
- 1 ≤ T ≤ 10
- 1 ≤ W, Pos ≤ N
- 1 ≤ Ai, Col ≤ 109
- For 30 points : 1 ≤ Q ≤ 103, 1 ≤ N ≤ 104
- For 70 points : 1 ≤ Q ≤ 104, 1 ≤ N ≤ 105
Input: 1 4 2 1 1 1 1 3 1 1 1 2 2 2 Output: 3 2 2
After the first repaint the boxes are coloured (1,1,1,1), which means 3 ways to choose 2 adjacent boxes of the same colour.
After the second repaint the boxes are coloured (2,1,1,1), which means 2 ways to select 2 adjacent boxes of the same colour.
After the third repaint thee boxes are coloured (2,2,1,1), which means 2 ways to select 2 adjacent boxes of the same colour.
|Tags||ltime22, medium, piyushkumar, segment-tree, sets|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.