ACM
线段树
3200字
G 线段树 区间修改、取模，区间哈希和查询 需要维护一个支持区间加1并对固定模数取模、区间哈希查询的线段树
开局就想写的一道题，写到最后艰难调出来后wa7，最终放弃上机辅助队友看别的题
晚上回去又调了很久，发现了几个错误
线段树哈希写错了，在求哈希和的时候不像普通的线段树区间和一样，查询哈希和时查询的区间[L, R]是需要动态变化的，必须保证L被不断地截断，才能保证算法的正确性 眼睛比较瞎，前缀和pre[]对M(65536)取模了 最开始的purify(将那些超过65536的位置取模)写挫了，在终止条件(l == r)之前就调用了down函数。调了一年才发现原来是这里有问题：如果在终止条件之前就调用down函数，这会导致地址的越界访问。因为st只开了4倍空间，所以如果在那种边角叶子结点（在满二叉树上多一个节外生枝的结构）仍然尝试down下去，就会访问到8倍的位置！在CF居然没有发生RE报警，以至于我一度怀疑是自己算法写错了，其实是空间的计算错误导致了UKE。 cpp 1#define ls (p << 1) 2#define rs ((p << 1) | 1) 3#define mid ((l + r) >> 1) 4 5using namespace std; 6const int maxn = 5e5 + 10; 7const int M = 65536; 8 9const int pp = 999983; 10const int mod = 1000237529; 11 12int a[maxn]; 13ll tag1[maxn << 2], st2[maxn << 2], st[maxn << 2]; 14ll po[maxn], pre[maxn]; 15 16void up(int p, int l, int r){ 17 st[p] = st[ls] + st[rs] * po[mid - l + 1] % mod; st[p] %= mod; 18 st2[p] = max(st2[ls], st2[rs]); 19} 20 21void build(int p, int l, int r, int k, int x){ 22 if(l == r && l == k){ 23 st[p] = st2[p] = x; 24 return ; 25 } 26 if(k <= mid) build(ls, l, mid, k, x); 27 else build(rs, mid + 1, r, k, x); 28 up(p, l, r); 29} 30 31void down(int p, int l, int r){ 32 if(tag1[p]){ 33 tag1[ls] += tag1[p]; 34 tag1[rs] += tag1[p]; 35 36 st[ls] += pre[mid - l] * tag1[p] % mod; st[ls] %= mod; 37 st[rs] += pre[r - mid - 1] * tag1[p] % mod; st[rs] %= mod; 38 39 st2[ls] += tag1[p]; 40 st2[rs] += tag1[p]; 41 42 tag1[p] = 0; 43 } 44} 45 46void update(int p, int l, int r, int L, int R){ 47 if(L <= l && r <= R){ 48 st[p] += pre[r - l]; st[p] %= mod; 49 st2[p]++; tag1[p]++; 50 return ; 51 } 52 down(p, l, r); 53 if(L <= mid) udpate(ls, l, mid, L, R); 54 if(R > mid) update(rs, mid + 1, r, L ,R); 55 up(p, l, r); 56} 57 58void purify(int p, int l, int r){ 59 if(st2[p] < M) return; 60 down(p, l, r); 61 if(l == r){ 62 st[p] %= M; st2[p] %= M; 63 return ; 64 } 65 66 if(st2[ls] >= M) purify(ls, l, mid); 67 if(st2[rs] >= M) purify(rs, mid + 1, r); 68 up(p, l, r); 69} 70 71ll hsh(int p, int l, int r, int L, int R){ 72 if(L <= l && r <= R) return st[p]; 73 down(p, l, r); 74 75 if(R <= mid) return hsh(ls, l, mid, L, R); 76 else if(L > mid) return hsh(rs, mid + 1, r, L, R); 77 else{ 78 ll ans = hsh(ls, l, mid, L, mid); 79 ans += hsh(rs, mid + 1, r, mid + 1, R) * po[mid - L + 1] % mod; 80 ans %= mod; 81 return ans; 82 } 83} 84 85int main(){ 86// Fastin; 87 po[0] = 1; 88 for(int i = 1; i < maxn; i++) po[i] = po[i - 1] * 1ll * pp % mod; 89 pre[0] = 1; 90 for(int i = 1; i < maxn; i++) pre[i] = pre[i - 1] + po[i], pre[i] %= mod; 91 92 int n, m; scanf("%d %d", &n, &m); 93 for(int i = 1; i <= n; i++){ 94 scanf("%d", a + i); 95 build(1, 1, n, i, a[i]); 96 } 97 98 while(m--){ 99 int op; scanf("%d", &op); 100 if(op == 1){ 101 int l, r; scanf("%d %d", &l, &r); 102 update(1, 1, n, l, r); 103 } 104 else{ 105 int l, r, k; scanf("%d %d %d", &l, &r, &k); 106 purify(1, 1, n); 107 108 ll res1 = hsh(1, 1, n, l, l + k - 1); 109 ll res2 = hsh(1, 1, n, r, r + k - 1); 110 puts(res1 == res2? "yes": "no"); 111 } 112 } 113 114 return 0; 115} L 分组背包 & LCM 给出n，构造某种拆分$p_1+p_2+…+p_k = n$，使得$lcm(p_1, p_2, …, p_k)$最大。
...