首页 > 代码库 > 洛谷 P1198 BZOJ 1012 [JSOI2008]最大数
洛谷 P1198 BZOJ 1012 [JSOI2008]最大数
题目描述
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
输入输出格式
输入格式：
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
输出格式：
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
输入输出样例
输入样例#1：
5 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3
输出样例#1：
6913
说明
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不
会超过 10^6 。
吐槽
为什么我这次吐槽要用"标题一"呢？请看这个……从4月1日一直做到6月19日，一道水淋淋的题，给了我血淋淋的教训——能用函数就尽量用吧，千万别搞些奇奇怪怪的东西，define定义函数一点都不靠谱啊，大不了用inline，稳得多。之前24分、36分，大片大片地超时就是因为我用了
。
把它换成inline int max()能AC，换成std::max()也能AC。记得树状数组里lowbit函数用define比用inline快一点啊，卡常底层优化真是……
解题思路
裸的线段树，维护最大值即可，lazy都不用(好像也用不成)。听说也是裸的单调栈来着。
注意事项见上面那个大大的“吐槽”即可
源代码
#include<stdio.h>#include<string.h>#define lson(x) ((x)<<1)#define rson(x) (((x)<<1)|1)inline int max(int a,int b){ return a>b?a:b;}const int INF = 2000000000;int num=0,tt=0;//树中元素个数 ，上次查询结果int m,d;int n;char c;struct seg_tree{ int l,r,max;}t[1000010];//从1起 void maketree(int node,int l,int r){ t[node].l=l; t[node].r=r; t[node].max=-INF; if(l==r) return; int mid=l+r>>1; maketree(lson(node),l,mid); maketree(rson(node),mid+1,r);}int query(int node,int l,int r){ if(l>t[node].r||r<t[node].l) return -INF; if(l<=t[node].l&&r>=t[node].r) return t[node].max; return max(query(lson(node),l,r),query(rson(node),l,r));}void add(int node,int pos,int N){ if(pos<=t[node].r&&pos>=t[node].l) t[node].max=max(t[node].max,N); else return; add(lson(node),pos,N); add(rson(node),pos,N);}int main(){ scanf("%d %d",&m,&d); maketree(1,1,m); for(int i=0;i<m;i++) { scanf("\n%c %d",&c,&n); if(c==‘Q‘) { tt=query(1,num-n+1,num)%d; printf("%d\n",tt); } else { add(1,++num,(n+tt)%d); } } return 0;}
洛谷 P1198 BZOJ 1012 [JSOI2008]最大数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。