关键词：

CF438D The Child and Sequence

给定数列，区间查询和，区间取模，单点修改。

n,m小于10^5

难点在于区间取模，类似于区间开方，如果这个区间的最大值$<=$ $mod$，不对其进行操作，反之对区间里每个数进行操作（由于操作数很少）

开$long long$

#include<bits/stdc++.h>

#define N 1000000
#define LL long long
using namespace std;

struct node
    LL l,r,w,f,maxn;
tr[N];

void push_up(LL k)
    tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn);
    tr[k].w=tr[k<<1].w+tr[k<<1|1].w;


void build(LL k,LL l,LL r)
    tr[k].l=l,tr[k].r=r;
    if(l==r)
        scanf("%d",&tr[k].w);
        tr[k].maxn=tr[k].w;
        return;
    
    LL mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    push_up(k);


void push_down(LL k)
    if(tr[k].f)
        tr[k<<1].w+=tr[k].f*(tr[k<<1].r-tr[k<<1].l+1);
        tr[k<<1].f+=tr[k].f,tr[k<<1].maxn+tr[k].f;
        
        tr[k<<1|1].w+=tr[k].f*(tr[k<<1|1].r-tr[k<<1|1].l+1);
        tr[k<<1|1].f+=tr[k].f,tr[k<<1|1].maxn+tr[k].f;
        tr[k].f=0;
    


void change(LL k,LL ql,LL qr,LL Mod,LL x)
    LL l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
    if(l==r)
        if(!Mod) tr[k].w=tr[k].maxn=x;
        else tr[k].w%=Mod,tr[k].maxn=tr[k].w;
        return;
    push_down(k);
    if(ql<=mid&&tr[k<<1].maxn>=Mod) change(k<<1,ql,qr,Mod,x);
    if(qr>mid&&tr[k<<1|1].maxn>=Mod) change(k<<1|1,ql,qr,Mod,x);
    push_up(k);


LL query(LL k,LL ql,LL qr)
    LL l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
    if(ql<=l&&qr>=r) return tr[k].w;
    push_down(k);
    LL ans=0;
    if(ql<=mid) ans+=query(k<<1,ql,qr);
    if(qr>mid) ans+=query(k<<1|1,ql,qr);
    push_up(k);
    return ans;


LL n,m;


int main()

    scanf("%lld%lld",&n,&m);
    build(1,1,n);
    for(LL opt,l,r,x,i=1;i<=m;i++)
        scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt==1)
            printf("%lld
",query(1,l,r));
        else if(opt==2)
            scanf("%lld",&x);
            change(1,l,r,x,0);
        else if(opt==3)
            change(1,l,l,0,r);
        
    
    
    return 0;

codeforces438dthechildandsequence

题面：codeforces438D 正解：线段树。这题好像是$picks$出的题，然后无限弱化才上的$cf$。。区间取模，每个数取模以后至少$/2$，所以暴力搞即可。证明：若$p<x/2$，那么$xmodp<x/2$；若$p>x/2$，那么$xmodp=x-p<x/2$。维护一个区... 查看详情

cf438dthechildandsequence(代码片段)

一道CF线段树好题.前置芝士1.线段树:一个很有用数据结构.2.势能分析:用来证明复杂度,其实不会也没什么关系啦.具体做法不难发现,对于一个数膜一个大于它的数后,这个数至少减少一半,每个数最多只能被膜(log_2N)次,所以就可以暴... 查看详情

cf438dthechildandsequence线段树(代码片段)

给定数列，区间查询和，区间取模，单点修改。n,m小于10^5。。。当区间最值小于模数时，就直接返回就好啦~#include<cstdio>#include<iostream>#defineRregisterint#definels(tr<<1)#definers(tr<<1|1)usingnamespacestd;inlinelonglongg()registerlon... 查看详情

cf438dthechildandsequence(线段树)(代码片段)

区间驱魔？看你大于模数吗，大就上，否则回家。会不会(T)？每次驱魔至少变(frac12)，所以(log)，不怂注意到叶子才更新#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#defi... 查看详情

codeforces438dthechildandsequence

题意：给定一个n个数的序列，完成以下3个操作：　　1.给定区间求和　　2.给定区间对x取模　　3.单点修改 对一个数取模，这个数至少折半。于是我们记一个最大值max，如果x>max则不做处理。 #include<stdio.h>#include<... 查看详情

codeforces438dthechildandsequence(代码片段)

题意要求支持三种操作 1.区间求和 2.单点修改 3.区间取模分析问题主要在于区间取模需要多维护一个区间最大值，当最大值已经小于模数的时候就不需要操作了【先开始读错题了，写了个区间修改哎我没救了】#include&... 查看详情

cf(438d)thechildandsequence(线段树)

题意：对数列有三种操作：Printoperation l,?r.Picksshouldwritedownthevalueof .Modulooperation l,?r,?x.Picksshouldperformassignment a[i]?=?a[i] mod x foreach i (l?≤?i?≤?r 查看详情

cf438e

题目叙述给定一个数组(c)和一个数(s)，求满足以下条件的二叉树数量：每个节点有个权值，权值为(c)中的一个数所有节点权值和为(s)题解首先设(f_i)表示(i)个结点组成的这样的树有(f_i)个，(g_i)表示数(i)是否在。那么(f_i=sum_j=0^ig_js... 查看详情

bzoj3625(cf438e)thechildandbinarytree——多项式开方(代码片段)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3625　　　http://codeforces.com/contest/438/problem/E开方：https://blog.csdn.net/kscla/article/details/79356786不过还是不会二次剩余。也不知道为什么取了G(x)-B(x)=0而不是G(x)+B(x) 查看详情

cf438ethechildandbinarytree（生成函数+多项式开根）(代码片段)

点此看题面大致题意：给你(n)个数，对于(i∈[1,m])，求出有多少棵不同的二叉树，满足权值都取自这(n)个数中，且权值和恰为(i)。推式子我们令(f_i)表示权值和恰为(i)的二叉树个数，(g_i)表示(i)是否为给出的数（(0/1)）。对于(f_0)... 查看详情

cf920fsumandreplace题解(代码片段)

...后便降到<=2，所以复杂度优秀(大约是nlogn？)这题与CF438DTheChildandSequence(区间取模)，类似，也可以维护区间最大值CF920F：#include<bits/stdc++.h>usingnamespacestd;#definergregister#definelllonglonginlinevoidread(int&x)charch=getchar();x=0;while(!isdigi... 查看详情

cf438ethechildandbinarytree（生成函数+多项式开根+多项式求逆）(代码片段)

传送门 可以……这很多项式开根模板……而且也完全不知道大佬们怎么把这题的式子推出来的……首先，这题需要多项式开根和多项式求逆。多项式求逆看这里->这里，这里讲一讲多项式开根多项式... 查看详情

cf438ethechildandbinarytree(代码片段)

题目生成函数就是好，什么题目都能搞先来列一个暴力(dp)，(dp_i)表示形成(i)点权的二叉树的方案数我们可以直接列出方程[dp_i=sum_k=1^nsum_j=0^i-c_kdp_jdp_i-c_k-j]边界条件(dp_0=1)发现里面类似卷积，于是生成函数来搞[F(x)=sum_i=0([i=0]+sum_k=... 查看详情

cf438e.thechildandbinarytree(ntt多项式开根多项式求逆)(代码片段)

题意链接Sol生成函数博大精深Orz我们设(f(i))表示权值为(i)的二叉树数量，转移的时候可以枚举一下根节点(f(n)=sum_winC_1dotsC_nsum_j=0^n-wf(j)f(n-w-j))设(T=n-w)，后半部分变为(sum_j=0^Tf(j)f(T-j))，是个标准的卷积形式。对于第一重循环我们可... 查看详情

cf数据结构练习

1.CF438D TheChildandSequence大意:n元素序列,m个操作:1,询问区间和.2,区间对m取模.3,单点修改维护最大值,取模时暴力对所有>m的数取模.因为取模后至少减半,复杂度$O(nlognlogC)$2.CF431E ChemistryExperiment大意:n个试管,第$i$个试管有$a_i$... 查看详情

[leetcode-438-findallanagramsinastring]

Givenastringsandanon-emptystringp,findallthestartindicesofp‘sanagramsins.StringsconsistsoflowercaseEnglishlettersonlyandthelengthofbothstringssandpwillnotbelargerthan20,100.Theorderofoutputdoesnotmatt 查看详情

438.findallanagramsinastring

438.FindAllAnagramsinaString TotalAccepted: 16658TotalSubmissions: 50116Difficulty: EasyContributors: Stomach_ache Givenastring s anda non-empty strin 查看详情

Powerpoint VBA 运行时错误 438（简单）

】PowerpointVBA运行时错误438（简单）【英文标题】：PowerpointVBARuntimeError438(easy)【发布时间】：2014-12-1709:55:27【问题描述】：我是powerpointvba的新手。我想要做的就是编写一小段代码，它允许我根据通过单击按钮所做的选择来更改幻... 查看详情