CodeForces 438D: The Child and Sequence (Modulo Segment Tree)

针对一个长度为n的非负整数数组a，需要实现以下三种操作：第一种操作是，给定区间端点l和r，计算该区间内所有元素的总和；第二种操作是，给定l、r和x，对区间[l, r]内的每个元素执行对x取模运算；第三种操作是，给定k和y，将数组中第k个位置的数值替换为y。其中n和m的取值范围不超过100000，而数组中的数值、x以及y的最大可能值均为10^9。

为了高效处理这些操作，可以采用线段树结构来维护区间的最大值与总和。在执行取模操作时，若发现x大于当前区间的最大值，则无需进一步处理；否则继续向下递归处理左右子区间。对于单个元素而言，每次有效的取模操作所需的时间复杂度为O(logn)，并且该元素的数值在每次取模后至少会减半。因此，在最坏情况下，每次修改操作的时间复杂度增加量为O(logn logW)。整体算法的时间复杂度为O(m logn logW)。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long 
     using namespace std;
    const int MAXN=1000100;
    struct JKX{
      int l,r,maxx;
      ll  w