题目描述

有一棵点数为 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：

输出样例#1：

说明

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。

吐槽

　　为什么我这次吐槽要用"标题一"呢？请看这个……从4月1日一直做到6月19日，一道水淋淋的题，给了我血淋淋的教训——能用函数就尽量用吧，千万别搞些奇奇怪怪的东西，define定义函数一点都不靠谱啊，大不了用inline，稳得多。之前24分、36分，大片大片地超时就是因为我用了。

　　把它换成inline int max()能AC，换成std::max()也能AC。记得树状数组里lowbit函数用define比用inline快一点啊，卡常底层优化真是……

——————2018年5月13日更新————————

　　今天不想做作业（都快高考了……）来洛谷上做一道裸线段树放松一下……结果突然想到，我这种#define MAX的行为不TLE才是见鬼了……

　　因为我代码中的a、b都是递归函数，它在query()替换成的代码就是这样的——

return query(lson(node),l,r)>query(rson(node),l,r)?query(lson(node),l,r):query(lson(node),l,r);

　　本来跑两遍询问，然后比较结果大小就好，用了，就跑了三四遍……

　　再次说明了#define的危险性！使用时一定要小心！

解题思路

　　裸的线段树，维护最大值即可，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 = ;

int num=,tt=;//树中元素个数 ，上次查询结果

int m,d;

int n;

char c;

struct seg_tree{

    int l,r,max;

}t[];//从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>>;

    maketree(lson(node),l,mid);

    maketree(rson(node),mid+,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(,,m);

    for(int i=;i<m;i++)

    {

        scanf("\n%c %d",&c,&n);

        if(c=='Q')

        {

            tt=query(,num-n+,num)%d;

            printf("%d\n",tt);

        }

        else

        {

            add(,++num,(n+tt)%d);

        }

    }

    return ;

}

巴特西

洛谷 P1198 BZOJ 1012 [JSOI2008]最大数

题目描述

输入输出格式

输入输出样例

说明

吐槽

解题思路

源代码

最新文章

热门文章