Queries
CF678F Lena and Queries题解
题目链接:CF 或者 洛谷 可以看到查询和插入就是李超线段树的基本操作,但在原有基础上多了一个删除操作,李超线段树不支持删除操作,但支持可撤销和可持久化,所以我们容易想到外层再套一个线段树分治即可。本题用可撤销就远远足够了,很好写。 具体的,我们读入所有操作,对于操作一,为当前下标线段读入它的 \( ......
1211. Queries Quality and Percentage
这道题目不难,但是有很多需要考虑的点以及容易写错的地方。 SELECT query_name, ROUND(AVG(rating/position), 2) AS quality, ROUND(SUM(CASE WHEN rating < 3 THEN 1 ELSE 0 END) * 100 / C ......
CF817F MEX Queries
题意 一个集合,初始为空。 请你维护以下 \(3\) 种操作。 把 \([l, r]\) 中在集合中没有出现过的数添加到集合中。 把 \([l, r]\) 中在集合中出现过的数从集合中删掉。 把 \([l, r]\) 中在集合中没有出现过的数添加到集合中,并把 \([l, r]\) 中在集合中出现过 ......
CF1254D Tree Queries
Tree Queries Luogu CF1254D 题面翻译 给定一棵 \(N\) 个节点的树,有 \(Q\) 次操作。 \(1\ v\ d\) 给定一个点 \(v\) 和一个权值 \(d\),等概率地选择一个点 \(r\),对每一个点 \(u\),若 \(v\) 在 \(u\) 到 \(r\) ......
Maximum And Queries (hard version)
题目传送门 感觉这题比 \(\rm F\) 难啊,\(\rm F\) 就是个板子,但为啥这题是蓝的,\(\rm F\) 是紫的。 思路 首先考虑 \(nq\) 怎么做。 发现很简单,按位贪心就行了。 具体地说,从大到小枚举二进制位,判断答案中能否出现这一位,若 \(i\) 当前这一位没有值,那么必须 ......
AtCoder Regular Contest 168 F Up-Down Queries
洛谷传送门 AtCoder 传送门 貌似是第三道问号题?感觉前面这个转化不是人能想到的。。。 考虑维护 \(y\) 的差分序列。更进一步地,我们类比 slope trick,维护一个可重集,里面有 \(y_{i + 1} - y_i\) 个 \(i\)(为了方便我们让每次操作时 \(y_{m + 1 ......
How does B-tree make your queries fast?
原文 https://blog.allegro.tech/2023/11/how-does-btree-make-your-queries-fast.html ......
CF1861C-Queries-for-the-Array-题解
title: CF1861C Queries for the Array 题解 date: 2023-09-06 07:53:53 categories: - 题解 因为插入和删除操作都在队尾,所以对序列前缀分析一下: 若一个序列的答案为 YES,那么它前缀的答案也为 YES。(对于没检查过的序列) ......
Queries for the Array 题解
前言 这场 CF 是我赛后打的,vp 赛时没做出来,后来发现是有个地方理解错了,有一些细节没有考虑到。现在换了一种思路来写,感觉更清晰了。 做法 首先需要动态维护三个变量,\(cnt\) 和 \(finishsort\) 和 \(unfinishsort\)。这三个变量分别表示当前数字的个数,已经排 ......
CF1902D Robot Queries 题解
题意:有一个二维平面直角坐标系,给定一串向某个方向移动 \(1\) 个单位的操作。 有 \(q\) 个询问,对于每个询问给定 \(x,y,l,r\),问如果倒着做 \(l\) 到 \(r\) 这段区间中的操作,是否会经过 \((x,y)\)。 ds 题。先预处理出 \(sx_i,sy_i\) 表示执 ......
CF938G Shortest Path Queries
Shortest Path Queries Luogu CF938G 题面翻译 给出一个连通带权无向图,边有边权,要求支持 \(q\) 个操作: \(1\) \(x\) \(y\) \(d\) 在原图中加入一条 \(x\) 到 \(y\) 权值为 \(d\) 的边 \(2\) \(x\) \(y\) ......
CF1904E Tree Queries
给定一棵 \(n\) 个节点的树与 \(q\) 次询问,每次询问给出一个 \(x\) 与一个大小为 \(k\) 的点集 \(a\),要求求出在删去了 \(a\) 中的点后从 \(x\) 出发的最长简单路径的长度。每次询问独立。 \(n, q, \sum k \le 2 \times 10^5\)。 ......
CodeForces 1902F Trees and XOR Queries Again
洛谷传送门 CF 传送门 如果我们能把 \(x \to y\) 路径上的所有点权插入到线性基,那么可以 \(O(\log V)\) 查询。 但是因为线性基合并只能 \(O(\log^2 V)\)(把一个线性基的所有元素插入到另一个),所以只能倍增做 \(O((n + q) \log n \log^2 ......
F Trees and XOR Queries Again (树链剖分)
看了知乎一位大佬的文章,用st表优化了查询,在st表中维护线性基 让lognN^2的查询 少了个log加了很多优化的方法 但无济于事 但是这样跑了9000ms 依然没法过 优化了一下线性基的查询方式 从枚举位数变成了类似lowbit的__lg(返回最大的1的位置) 不知道具体怎么算的优化 现在时间大 ......
【题解】CodeForces 1902F Trees and XOR Queries Again
传送门:https://codeforces.com/contest/1902/problem/F 数据结构题,这里讲两种思路。 $ST$ 表思路: 判定“从若干个数中能否取出其中一些,使得异或和为 $x$”的问题,第一时间想到线性基,本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性 ......
F. Trees and XOR Queries Again
首先容易想到lca+线性基,\(O(nlognB^2+qlognB^2)\),显然T飞了。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<vector> #i ......
【题解】Trees and XOR Queries Again - Codeforces 1902F
https://codeforces.com/contest/1902/problem/F 方法一 可以从树上路径想到轻重链剖分(也可以用其他种类的LCA算法),然后从数的异或表示很容易想到线性基。 然后因为是无修改的,所以可以轻重链剖分+ST表+线性基。具体来说就是: 先进行轻重链剖分。然后把每次 ......
D. Robot Queries
D. Robot Queries There is an infinite $2$-dimensional grid. Initially, a robot stands in the point $(0, 0)$. The robot can execute four commands: U — ......
CF1902 D Robot Queries 题解
Link CF1902 D Robot Queries Question Robot 初始在 \((0,0)\) ,有一个字符串 \(s\) ,表示运行列表 \(U\):y+1 \(D\):y -1 \(L\) :x -1 \(R\) :x+1 之后有 \(Q\) 次询问,有\(L,R,x,y\), ......
SP1716 GSS3 - Can you answer these queries III 题解
题意: 给定一个长度为 $ n $ 的序列 $ a $ , $ q $ 次操作,每次操作为以下之一: \(0\) \(x\) \(y\):将 \(a_x\) 修改为 \(y\) \(1\) \(l\) \(r\):询问区间 \([l,r]\) 的最大连续子序列和 思路: 考虑线段树维护区间最大连续子 ......
CodeForces 1526F Median Queries
洛谷传送门 CF 传送门 首先,如果我们确定了 \(1, 2\) 或 \(n - 1, n\) 的位置,我们就能求出原排列。因为题目给了 \(p_1 < p_2\),所以可以不考虑对称性。也就是说我们知道两个位置是 \(1, 2\) 或 \(n - 1, n\) 但不确定究竟是 \(1, 2\) 还 ......
P3455 [POI2007] ZAP-Queries
题意 求 \(\sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} [gcd(i, j) = k]\)。 Sol \[\begin{aligned} f(k) &= \sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} [\gcd(i, j) = k] \ ......
Problem: B. Queries on a String
题意简述: 给出一个字符串,每次给定l,r,k,选择一个子串l-r,然后子串向右移动k个单位. 做法: 每次k对子串的长度取模,然后模拟即可(使用substr函数截取前半段和后半段,交换前半段和后半段即可) 点击查看代码 // Problem: B. Queries on a String // C ......
SP19543 GSS8 - Can you answer these queries VIII 题解
更好的阅读体验 SP19543 GSS8 - Can you answer these queries VIII fhq + 二项式定理。提供一个不太一样的思路。默认下标从 \(1\) 开始。 首先插入删除,区间查询,想到可以平衡树维护或者离线下来做线段树。本文中是用的是 fhq,好写一些。 \(k ......
SP1557 GSS2 - Can you answer these queries II 题解
SP1557 GSS2 - Can you answer these queries II 更好的阅读体验 扫描线。把询问挂在右端点上,扫描右端点,纵轴仍为序列维。 对于这种出现多次的数只算一次的,记 \(pre_i\) 表示 \(i\) 这个值上一次的出现位置,套路化的可以强制让出现多次的在 \( ......
ARC168F Up-Down Queries
考虑一次询问怎么做: 我们想求的答案就是 每次减时为 \(0\) 的位置个数之和(这些位置会与 \(0\) 取 \(\max\) 从而使答案变大) + \(\sum (m-2\times a_i)\)(所有操作的总和)。 考虑维护 \(y\) 的差分数组,分析一次操作 \([1,x]\) 减 \(1 ......
CF911G Mass Change Queries
题目描述: 给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列. 数据范围: \(1\le n\le 2\times 10^5\) \(1\le a_i\le 100\) \(1\le q\le 2\times 10^5,1\le l,r\le n,1\le ......
CF1304E 1-Trees and Queries(lca+树上前缀和+奇偶性)
题目 二话不说,直接按题意模拟暴搜,当然 \(O(nq)\) 的复杂度显然是寄了的。 不过,在模拟的过程中,我在链式前向星的删边中居然一开始错了,还是要 mark 一下以后注意。 void del(int x, int pre) { e[top].to = e[top].next = 0; h[x] ......
[题解]CF938G Shortest Path Queries
Shortest Path Queries 给你一张无向连通图,支持三种操作: 插入一条边 \((u, v, w)\)。 删除一条边。 求 \((u, v)\) 之间的异或最短路。 \(n, m, 1 < 2^{30}\)。 先考虑异或最短路怎么求,这部分和 最大XOR和路径 是一样的。就是把图上的 ......