维护一个数列, 支持6种操作: 区间插入, 区间删除, 区间赋值, 区间翻转, 区间求和, 求和最大的连续子列. (插入数字的总数不超过4*10^6, 任何时刻数列中最多含5*10^5个数, 任何一个数字均在[-1000, 1000]内, 操作数不超过20000)

Read More

给一个N*M的正整数矩阵, 支持子矩阵加, 子矩阵gcd查询. 所有查询均包含某个特定的点(X, Y). (NM ≤ 5*10^5, 操作数T≤10^5, 保证所有时刻矩阵中的数为小于2^62的正整数) 具体输入格式, BZOJ上的描述有误, 参考原题面.

Read More

写一个数据结构, 维护一个n*n矩阵, 支持单点修改, 子矩阵最值查询. (n ≤ 100)

Read More

一个非负整数数列A, 求 Ai xor Aj (1≤i<j≤n) 的前k小. (2≤n≤10^5, 1≤k≤min{2.5*10^5, n*(n-1)/2})

Read More

发现马老师的线段树只用两倍空间, 他说这是 <高级数据结构> 上介绍的一种奇妙的方法. 这种方法用很小的代价实时计算出线段对应的编号, 相比堆式存储, 可以省掉一个参数. 空间紧凑了, 寻址的时间缩短, 程序也跑得更快了.

秉承着 "让常数优化成为一种习惯" -_-b 学习一下, 顺便对这种方法的正确性给个证明. <高级数据结构> 上写的是错的......

Read More

长度为n的序列a, 一个区间的价值等于这段区间的次大值与区间内其他任意一个数异或的最大值, 求最大价值. (1≤n≤50000, 0≤ai≤10^9, ai两两不同)

Read More

给一个长度为N的序列A, 求(A[l1] xor A[l1+1] xor ... xor A[r1]) + (A[l2] xor A[l2+1] xor ... xor A[r2])的最大值. (2≤N≤4*10^5, 0≤Ai≤10^9)

Read More

给定一个初始长度为N的非负整数序列和M个操作: 在序列末尾添加一个数x / 寻找l≤p≤r, 使得A[p] xor A[p+1] xor ... xor A[N] xor x最大. (N,M≤300000, 0≤a[i]≤10^7)

Read More

比赛的时候做了前四道, 然而第四道FST了, 原因是m,n搞反.

以下是A-F的题解. 6/7

最后一道题 (貌似是数位DP) 还没想通......脑子有点乱, 先放着吧.

Read More

把莫斯科时间当成北京时间, 于是错过了这一场......题目不难, 唉, 一个涨rating的机会...... 以下是题解: 6/6 会发现是贪心专场.

Read More

题意: 一个长度为n的序列, Q个询问, 查询左端点在[a, b], 右端点在[c, d]的所有子串中最大的中位数. 奇数个数的中位数是排序后最中间的一个, 偶数个数的中位数定义为排序后中间靠右的那一个. (n≤20000, Q≤25000)

Read More

题意: 一个长度为N的序列, 一个定值K, 和M个询问, 每次询问位置[x, y]是否有某个长度为K的子串, 是则回答"No", 否则回答"Yes". (N ≤ 2*10^5, 序列中数的大小不超过N)

Read More

加强版题意: 写一个并查集, n个集合, m个操作, 除了并, 查, 还支持回到某一历史版本, 强制在线. (0<n,m≤2*10^5)

Read More

题意: 带修改的区间第k小. 询问m, 序列长度n ≤ 10^4, 0≤序列中的数≤10^9.

Read More

题意: n个数和m个询问, 问位置[l, r]中是否存在一个数出现的次数大于(r-l+1)/2, 如有则输出, 否则报告不存在. (每个数是不超过n的正整数, n, m ≤ 5*10^5)

Read More