首页 > 时空栈
开通博客写题解
头像 范艺杰
发表于 2020-05-10 18:54:21
我们不妨将入栈操作看作在这个时间点加1，将出栈操作看作这个时间点-1。那么询问当前时间点的栈顶元素就是找到最大的后缀下标使得这个后缀的和是1即可。我们通过线段树来维护区间后缀值，维护时，需要同时维护这个区间和以及后缀最大值。如果采用是自底向上的线段树即zkw线段树，那么query只要一个函数即可。如 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 свобода
发表于 2020-05-10 18:47:14
可以先离散化，然后开线段树维护。我们对于栈的查找操作可以理解成找到插入的时间点，然后再找到对应的元素。对于插入和删除操作，可以认为是在指定时间以后+1或者-1。对于查询操作，我们首先可以确定对应时间栈内元素个数，然后用线段树查询在当前时间之前最后一个小于这个个数的时间点t，t+1就是插入的时间。整体 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”