主席树 – Tgotp-Blog

tyvj测试

很不爽啊。。。

day1 60 + 100 + 10 = 170

day2 100 + 40 + 80 = 220

总分390

update:然后吐槽一下:tyvj的测评姬大概烂破了天际。。。能测一个小时的代码我还是第一次见。。。莫名其妙的System Error真[……]

Read more

3585: mex

算法一:莫队算法,大力艹一艹就过了。

速度堪忧。。。显而易见是下面那个。。。

c++代码如下:

算法二:主席树

对于权值建树,离散化位置。

更新每个点最后出现的位置,如果左子树最后出现的位置小于l,肯定能过[……]

Read more

P1383 高级打字机

这题的IOI挑战就是可持久化结构;

在线的实现用主席树就好了;

undo就是追溯过去sz-1-x的版本(其本身也算作一个版本);

而query就是从上次的版本找到第x个;

至于add就是新建立一个版本,并且在起相应位置插入当前的字符c;

代码仅供参考。

c++代码[……]

Read more