| 题目名称 | 2282. [HZOI 2015]黑树白 |
|---|---|
| 输入输出 | D_Tree.in/out |
| 难度等级 | ★★ |
| 时间限制 | 3500 ms (3.5 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：19， 提交：64， 通过率：29.69% | ||||
 mostshy |
100 | 2.627 s | 210.96 MiB | C++ |
 jiachinzhao |
100 | 3.439 s | 279.28 MiB | C++ |
 FoolMike |
100 | 3.484 s | 351.25 MiB | C++ |
 now-ing |
100 | 3.813 s | 318.89 MiB | C++ |
 0 |
100 | 3.917 s | 280.17 MiB | C++ |
 AntiLeaf |
100 | 3.939 s | 126.05 MiB | C++ |
 哒哒哒哒哒！ |
100 | 3.978 s | 234.06 MiB | C++ |
|
0 |
100 | 4.003 s | 252.15 MiB | C++ |
|
0 |
100 | 4.217 s | 280.17 MiB | C++ |
|
0 |
100 | 4.491 s | 280.17 MiB | C++ |
| 关于 黑树白 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
丧心病狂，居然卡线段树套线段树的常数，非得搞个bit……
| ||||
|
| ||||
|
http://www.cnblogs.com/joyouth/p/5434886.html
本蒟蒻的题解报告，欢迎各路神犇前来踩  Aglove
2016-04-26 14:08
1楼
| ||||
【题目描述】
给定一棵树，每个节点有点权，要求维护以下两个操作：
1、Q u v a b 本蒟蒻施展大魔法，使得树上所有点权>=a且点权<=b的点变成白点，其余的点变成黑点，并查询u到v的简单路径上有多少个白点
2、M u v 本蒟蒻施展小魔法，将u点的点权改为v
【输入格式】
第一行n，m 表示节点总数和操作次数
以下n个正整数wi表示i点的点权
以下n-1行，每行u，v描述一条边的端点
以下m行，每行一个操作如题意
注意：由于本蒟蒻的魔法太弱不稳定
所以对于每次Q和M输入的u和v，你需要令u=(u+ans)%n+1,v=(v+ans)%n+1
其中ans为上一次的答案，最开始ans=0
注意只是Q和M中输入的u和v
n，m<=80000,任意时刻点权不会超过n
【输出格式】
对于每个Q操作，输出相应答案
【样例输入】
5 5 4 3 3 1 1 2 1 3 2 4 3 5 4 M 2 1 M 4 4 M 1 4 Q 2 4 2 3 Q 4 2 1 5
【样例输出】
1 4