[ 补题|题解 ] A - The Child and Sequence

前言

题目链接 : VJ: https://vjudge.net/contest/446835#problem/A CF: https://codeforces.com/problemset/problem/438/D?mobile=true

做这题的时候 感觉挺简单, 最后debug了2小时 真心不容易QAQ (还是太菜了)

难度: 线段树入门基础题

题目

(题目就这么简单 不信你自己看)

三个操作:

1. 区间求和
2. 区间取模
3. 单点修改

区间求和,和单点修改都是线段树基本操作

但是这个区间取模 如果全都取模的话 那么会O n^2 TLE

观察一下不难发现

• 如果一个区间内的最大 都比 Mod 小 那么该区间不会变

计算一下时间复杂度 因为取模之后 一定比 x/2 小 最多是Log n次取模

所以程序总 时间复杂度 是 nlogn (1e5)完全可以跑的下来

CODE

#include 
using namespace std;
const int N = 1e5+10;
using LL  = long long ;
int w[N];

struct node
{
    int l,r,mx;
    LL sum;
} tr[N*4];

void pushup(int u)
{
    tr[u].sum = tr[u