b406: 12538 - Version Controlled IDE
Tags : 函數式 平衡樹
Accepted rate : 13人/15人 ( 87% ) [非即時]

最近更新 : 2015-06-16 01:21

Programmers use version control systems to manage fi les in their projects, but in these systems, versions are saved only when you manually submit. Can you implement an IDE that automatically saves a new version whenever you insert or delete a string?
Positions in the buff er are numbered from 1 from left to right. Initially, the buff er is empty and in version 0. Then you can execute 3 commands (vnow means the version before executing the command, and L[v] means the length of buff er at version v):
 1 p s: insert string s after position p (0<=p<=L[vnow], p = 0 means insert before the start of the start of the buffer). s contains at most 1 and at most 100 letters.
 2 p c: remove c characters starting at position p (p>=1; p + c<=L[vnow] + 1). The remaining characters (if any) will be shifted left, fi lling the blank.
 3 v p c: print c characters starting at position p (p>=1; p + c<=L[v] + 1), in version v (1<=v<=vnow).
The first command is guaranteed to be command 1(insert). After executing each command 1 or 2, version is incremented by 1.
There is only one test case. It begins with a single integer n (1<=n<=50,000), the number of commands.
Each of the following n lines contains a command. The total length of all inserted string will not exceed 1,000,000.
In order to prevent you from preprocessing the command, we adopt the following obfuscation scheme:
 Each type-1 command becomes 1 p + d s
 Each type-2 command becomes 2 p + d c + d
 Each type-3 command becomes 3 v + d p + d c + d
Where d is the number of lowercase letter `c' you printed, before processing this command.
Before the obfuscation, the sample input would be: 
1 0 abcdefgh
2 4 3
3 1 2 5
3 2 2 3
1 2 xy
3 3 2 4 
Print the results of command 3, in order. The total length of all printed strings will not exceed 200,000.
Sample Input
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6
Sample Output
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <10M
Hint :
函數式 平衡樹
UVa12538 [管理者:
liouzhou_101 (王启圣)

ID User Problem Subject Hit Post Date