Random Sums
Турнир за Купата на Декана, 2011
Time Limit: 3s, Memory Limit: 64MiB
Поради сложността на задачата няма да има готино условие. Само ще кажем, че тази задача е за Ели.
Дадени са N на брой числа H1, H2, ..., HN. След това се изпълняват Q заявки, които могат да са:
Дадени са N на брой числа H1, H2, ..., HN. След това се изпълняват Q заявки, които могат да са:
- Добави ново число Xi в редицата.
- Сортирай всички числа (първоначалните и добавените до сега) и намери сумата на тези с индекси Si1, Si2, Si3, ..., SiK.
- Si1 = F % M
- Sik = (Sik-1 * A + B) % M, за k = 2, 3, ..., K.
Вход
На първия ред на стандартния вход са зададени целите числа N и Q. Следва ред с N цели числа H1, H2, ..., HN. Следват Q на брой реда. i-тият от тях започва с главна латинска буква: 'A' за заявкa от тип A и 'B' за заявкa от тип B. Ако заявката е от тип A, то на същия ред ще има само още едно цяло число Xi – новото число, което добавяме. Ако пък заявката е от тип B, на същия ред след типа ще бъдат зададени четирите цели числа Ki, Fi, Ai, Bi.
Изход
На стандартния изход изведете по един ред за всяка заявка от тип B, съдържащ едно цяло число - търсената сума.
Ограничения
- 1 ≤ N, Q ≤ 100,000
- 1 ≤ Ki, Fi, Ai, Bi ≤ 1,000
- 1 ≤ Hi, Xi ≤ 1,000,000,000
Примерен Вход | Примерен Изход |
---|---|
2 3 42 13 B 2 2 1 1 A 17 B 5 2 5 6 | 55 160 |
10 13 42 13 7 11 5 666 13 17 20 6 B 3 6 7 8 B 13 1 11 9 A 23 B 13 1 11 9 A 23 A 8 B 3 3 3 3 B 7 17 9 11 A 12 B 1 8 3 5 A 31 A 28 B 77 17 11 13 | 64 1477 510 679 99 17 1236 |
В първия пример първата заявка пита за сумата на числата с индекси 0 и 1, която е 13 + 42 = 55. След втората заявка числата са {13, 17, 42}. Третата заявка пита за сумата на числата с индекси 2, 1, 2, 1, и 2, която е 42 + 17 + 42 + 17 + 42 = 160.