关键词：
外国人的数据结构题真耿直
唯一有难度的操作就是区间取模，然而这个东西可以暴力弄一下，因为一个数$x$被取模不会超过$logn$次。
证明如下（假设$x Mod y$）：
如果$y leq fracx2$那么$x$取模之后会小于$fracx2$，而如果$y > fracx2$时，$x$取模之后一定也会小于$fracx2$
然后就暴力一个一个取过去就好了，还有一个算是剪枝的优化，我们可以顺便维护一下区间最大值，如果区间最大值都小于当前的模数的话，那么就直接$return$好了。
仍然不会算时间复杂度。
丢个模板。
Code：
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N = 1e5 + 5; int n, qn; ll a[N]; template <typename T> inline void read(T &X) X = 0; char ch = 0; T op = 1; for(; ch > ‘9‘|| ch < ‘0‘; ch = getchar()) if(ch == ‘-‘) op = -1; for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; inline ll max(ll x, ll y) return x > y ? x : y; namespace SegT ll s[N << 2], maxn[N << 2]; #define lc p << 1 #define rc p << 1 | 1 #define mid ((l + r) >> 1) inline void up(int p) if(p) s[p] = s[lc] + s[rc]; maxn[p] = max(maxn[lc], maxn[rc]); void build(int p, int l, int r) if(l == r) s[p] = maxn[p] = a[l]; return; build(lc, l, mid); build(rc, mid + 1, r); up(p); void modify(int p, int l, int r, int x, ll v) if(x == l && x == r) s[p] = maxn[p] = v; return; if(x <= mid) modify(lc, l, mid, x, v); else modify(rc, mid + 1, r, x, v); up(p); void doMod(int p, int l, int r, int x, int y, ll v) if(maxn[p] < v) return; if(l == r) s[p] %= v, maxn[p] %= v; return; if(x <= mid) doMod(lc, l, mid, x, y, v); if(y > mid) doMod(rc, mid + 1, r, x, y, v); up(p); ll query(int p, int l, int r, int x, int y) if(x <= l && y >= r) return s[p]; ll res = 0LL; if(x <= mid) res += query(lc, l, mid, x, y); if(y > mid) res += query(rc, mid + 1, r, x, y); return res; using namespace SegT; int main() read(n), read(qn); for(int i = 1; i <= n; i++) read(a[i]); build(1, 1, n); for(int op, x, y; qn--; ) read(op); if(op == 1) read(x), read(y), printf("%lld ", query(1, 1, n, x, y)); if(op == 2) read(x), read(y); ll v; read(v); doMod(1, 1, n, x, y, v); if(op == 3) read(x); ll v; read(v); modify(1, 1, n, x, v); 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的新手。我想要做的就是编写一小段代码，它允许我根据通过单击按钮所做的选择来更改幻... 查看详情