8649: BZOJ4649:Sum
Memory Limit:512 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
给一棵大小为(n<=100000)的树,每个点有权值vi。要求支持以下操作: 子树加、子树对某数取max/min、链加、链对某数取max/min、子树修改、链修改、链权值翻转、子树求和、链求和。输出对10^9+7取模的非负结果即可。 树有根为1。保证输入中的链权值翻转操作的i为j的祖先。
输入格式
输入第一行一个正整数n,第二行n个整数v,第三行到第n+1行每行两个数u、v代表u和v之间有一条边。 接下来一行一个整数(m<=100000),下面m行每行一个操作。操作格式如下: SUBADD i v i的子树加上v SUBMAX i v i的子树对v取max SUBMIN i v i的子树对v取min CHAINADD i j v i到j的路径上每个点加上v CHAINMAX i j v i到j的路径上每个点对v取max CHAINMIN i j v i到j的路径上每个点对v取min SUBXGW i v i的子树修改为v CHAINXGW i j v i到j的路径上每个点修改为v CHAINREV i j i到j的路径进行权值翻转 SUBQUE i 输出i的子树和 CHAINQUE i j 输出i到j路径上的权值和 操作中所有v和点的初始权值v满足v<=1000000,保证全程不会有点权值超过10^9+7
输出格式
对于每个求和操作输出一行代表对应权值和。
样例输入
10 -3 -2 1 3 1 -2 0 -5 1 4 2 1 3 1 4 1 5 2 6 4 7 3 8 2 9 3 10 2 19 SUBADD 4 2 SUBXGW 9 -5 CHAINQUE 1 1 SUBQUE 9 SUBMAX 7 -1 SUBMIN 10 2 CHAINQUE 6 9 SUBQUE 1 CHAINADD 9 3 4 CHAINXGW 5 7 5 CHAINQUE 7 7 SUBQUE 1 CHAINMAX 8 7 -5 CHAINMIN 5 3 4 CHAINQUE 3 1 SUBQUE 5 CHAINREV 1 7 CHAINQUE 3 2 SUBQUE 7
样例输出
1000000004 1000000002 1000000005 1000000001 5 26 8 4 13 4
提示
没有写明提示
题目来源
By DpDarkFantasy