返回信息流题目:hdu1540
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1540
题目的大意是:有n个村庄在一条直线上，编号从1到n，每个村庄和相邻的两个村庄有一条边，三种操作，D a表示把村庄a摧毁，Q a表示询问和村庄a连通的村庄数量，R把最近摧毁的村庄复原。
代码提交结果:wa
我对这道题有如下想法：
基本思路是数状数组+二分查找。 sum(i)表示从村庄1到村庄i(包括i在内)被摧毁的村庄数。
(1) 对于每次查询村庄i，sum(i)由定义可知是随i值单调递增的, 二分查找sum(i), sum(i)+1的左边界值， 假定结果分别为left, right。 left,right值分别代表离i最近的被摧毁的村庄下标。则查询结果为right-left-1
(2）R操作不包含操作值，使用栈存储最近一次被摧毁的村庄下标
(3) 数状数组的更新。 根据sum（i）的定义， 每次摧毁村庄时， add（x, 1）, 修复村庄时add(x, -1)
具体代码见附件:
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #93580同步于 2017/6/2
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
关于hdu 1540 的一点疑问。
windowsills
2017/6/2镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
根据discuss的说法，这个题目会连续摧毁或连续修复同一个村庄。直接+1或-1不太对吧。
这个m*log(n)^2的方法不会超时吗？这个思路我用线段树写了一下就超时了，换成维护左右连续长度的方法才过。
能给个case吗？我想了一些case，都Pass了，但提交还是wa。代码在附件中，真心求教。
【 在 kit 的大作中提到: 】
根据discuss的说法，这个题目会连续摧毁或连续修复...
如果这个确实是题意的话，我确实读题有误，没领会到。
你给的例子中最后有3个R, 3、4、5都恢复的话，正确答案应该是7? 而不是4?
另外
我按照你的建议在代码中做了修改，但提交后仍然是WA.所以问题是不是可能不在这里？
diff --git a/topics/binary indexed trees/hdu1540.cpp b/topics/binary indexed trees/hdu1540.cpp
index b87eaa4..31bff02 100644
--- a/topics/binary indexed trees/hdu1540.cpp
+++ b/topics/binary indexed trees/hdu1540.cpp
@@ -60,13 +60,11 @@ int main() {
cin >> op;
if (op == "D") {
cin >> val;
+ if (vis[val] == 1) continue;
data[++i] = val;
vis[val] = 1;
add(val, 1);
} else if (op == "Q") {
- for (int i = 1; i <= n; i++) {
- //printf("sum(%d)=%d\n", i, sum(i));
- }
cin >> val;
if (vis[val] == 1) {
printf("%d\n", 0);
【 在 kit 的大作中提到: 】
: 7 100
: D 3
: D 3
: ...................