C - Adjacent Swaps
题目大意
\(N\)个球从左到右排成一列。开始时，从左往右的第\(i\)个球上写着数字\(i\)。
请执行\(Q\)个操作，第\(i\)个操作如下：
- 令\(j=~N\)个球中写着数字\(x_i\)的球的位置
- 如果\(j=N\)，将其与第\(j-1\)个球交换；否则，与第\(j+1\)个球交换。
求所有操作后的球上分别写的数字。详见输出格式。
\(2\le N\le 2\times 10^5\)
\(1\le Q\le 2\times 10^5\)
\(1\le x_i\le N\)
输入格式
\(N~Q\)
\(x_1\)
\(\vdots\)
\(x_Q\)
输出格式
令\(a_i=N\)个球中从左往右的第\(i\)个在所有操作结束后写的数，则按如下格式输出：
\(a_1~a_2~\dots~a_n\)
即将\(a_1,\dots,a_n\)按顺序输出到一行，用空格隔开。
样例
略，请自行前往AtCoder查看。
分析
根据数据范围可得，本题只能使用时间复杂度不超过\(\mathcal O(N+Q\log n)\)的算法。
因此，暴力模拟，即查找每个球对应的位置\(j\)（\(\mathcal O(NQ)\)）肯定是行不通的。
但是很容易想到可以设置索引数组\(p\)，使当\(a_i=x\)时，\(p_x=i\)。
这样，对于每一个操作，只需\(\mathcal O(1)\)的时间复杂度就能找到\(x_i\)出现的位置。
交换时注意同时交换一下\(a\)和\(p\)中的元素即可。总时间复杂度\(\mathcal O(N+Q)\)。
代码
#include <cstdio>
#define maxn 200005
using namespace std;
inline void swap(int& x, int& y) { x ^= y ^= x ^= y; }
int pos[maxn], ans[maxn];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++)
ans[i] = pos[i] = i;
while(q--)
{
int x;
scanf("%d", &x);
int p1 = pos[x];
int p2 = p1 == n? p1 - 1: p1 + 1;
swap(pos[x], pos[ans[p2]]);
swap(ans[p1], ans[p2]);
}
for(int i=1; i<=n; i++)
printf("%d ", ans[i]);
return 0;
}
D - 250-like Number
题目大意
当一个正整数\(k\)满足以下条件时，我们称其为“与\(250\)相似的”：
- \(k=p\times q^3\)，其中\(p,q\)均为质数，且\(p<q\)。
求不超过\(N\)的“与\(250\)相似的”\(k\)的个数。
\(1\le N\le 10^{18}\)
输入格式
\(N\)
输出格式
将答案输出为一个整数。
样例
| \(N\) | 输出 |
|---|---|
| \(250\) | \(2\) |
| \(1\) | \(0\) |
| \(123456789012345\) | \(226863\) |
分析
看到数据范围后我们发现\(N\)太大，不能盲目下手。
由\(k=p\times q^3,k\le N\)可知，\(p\times q^3\le N\le 10^{18}\)。
又因为\(p,q\)是质数，且\(p<q\)可得，\(2\le p<q\)。
因此，当\(p\)最小时\(q\)最大，所以\(q\le \sqrt[3]{\frac {N=10^{18}} {p=2}}\approx794000\)。
这时，可以想到筛出质数表，并对于每个质数\(p\)计算最大的\(q\)，此时质数\(p<x\le q\)都能作为\(q\)，因此将答案加上\(p<x\le q\)的质数数量即可。当\(p\ge q\)时，退出循环，输出结果即可。
计算\(q\)时可以使用二分查找或者双指针算法快速处理。
总时间复杂度大约在\(\mathcal O(n^{\frac 7 {22}})\)。
代码
本代码使用双指针实现。
#include <cstdio>
#include <cmath>
#include <vector>
#define maxp 794000
using namespace std;
using LL = long long;
bool bad[maxp];
vector<int> primes;
inline LL pow3(LL x) { return x * x * x; }
int main()
{
bad[0] = bad[1] = true;
for(int i=2; i<maxp; i++)
if(!bad[i])
{
primes.push_back(i);
for(int j=i<<1; j<maxp; j+=i)
bad[j] = true;
}
LL n;
scanf("%lld", &n);
LL ans = 0LL;
for(int i=0, j=primes.size()-1; i<j; i++)
{
while(j >= 0 && primes[i] * pow3(primes[j]) > n) j --;
if(i >= j) break;
ans += j - i;
}
printf("%lld\n", ans);
return 0;
}
E - Prefix Equality
题目大意
给定长度为\(N\)的正整数序列\(A=(A_1,\dots,A_N)\)和\(B=(B_1,\dots,B_N)\)。
对于每个\(1\le i\le Q\)，给定两个正整数\(x_i,y_i\)，回答如下格式的查询：
- 判断集合\(\{A_1,\dots,A_{x_i}\}\)和\(\{B_1,\dots,B_{y_i}\}\)是否相等。
集合可以说成是序列排序并去重的结果，如序列\((9,3,5,3,4)\)对应的集合是\(\{3,4,5,9\}\)。
\(1\le N,Q\le 2\times 10^5\)
\(1\le A_i\le B_i\le 10^9\)
\(1\le x_i,y_i\le N\)
输入格式
\(N\)
\(A_1~\dots~A_N\)
\(B_1~\dots~B_N\)
\(Q\)
\(x_1~y_1\)
\(\vdots\)
\(x_Q~y_Q\)
样例
样例输入
5
1 2 3 4 5
1 2 2 4 3
7
1 1
2 2
2 3
3 3
4 4
4 5
5 5
样例输出
Yes
Yes
Yes
No
No
Yes
No
分析
本题做法很多。这里我们介绍使用哈希(Hash)的算法。
现在我们有一个很简单但明显错误的思路：
将\(A\)和\(B\)做一个前缀和，只计算不重复的元素，即
此时，只需判断\(P_A(x_i)\)和\(P_B(y_i)\)是否相等即可。时间复杂度为\(\mathcal O(N+Q)\)或\(\mathcal O(Q+N\log N)\)。
构造hack数据也很简单，只需部分前缀和相等即可，如：
5
1 3 5 6 7
3 2 4 1 5
1
3 3
这样，因为\(1+3+5=3+2+4=9\)，所以这样的程序会认为这是相等的序列，从而输出Yes，但显然\(\{1,3,5\}\ne\{3,2,4\}\)，因此答案为No，程序错误。
现在考虑改进这个思路，使其不容易被hack，可以使用一个哈希函数：
\[H(x)=x(x+A)(x+B)\bmod P \]其中\(A,B,P\)一般取质数，\(H(x)\)即为\(x\)对应的哈希值。（对\(P\)取模是为了防止哈希值太大导致溢出）
显然，这样有一个很小的概率会产生哈希冲突（即不同的数得到相同的哈希值），但因为\(A,B,P\)的取值太多，评测机没法针对性的hack，所以正常情况下都能通过（CF的Hack机制除外）。如果真担心有问题，可以采取双哈希，即对于一个\(x\)，用两个不同的哈希函数计算哈希值，这样就几乎不可能出现哈希冲突了。
现在，前缀和变为：
\[P_A(i)=\sum\{H(A_1),\dots,H(A_i)\}\bmod P\\ P_B(i)=\sum\{H(B_1),\dots,H(B_i)\}\bmod P \]还是按原来的思路，判断前缀和是否相等即可。
总时间复杂度为\(\mathcal O(n)\)（unordered_set/HashSet）或\(\mathcal O(n\log n)\)（set/TreeSet）。
代码
这里还是要提一点，就是使用哈希时有一个小技巧，即直接取\(P=2^{32}-1\)（unsigned int）或者\(P=2^{64}-1\)（unsigned long long），使整数自然溢出，省去了麻烦又耗时间的取模步骤。CodeForces上还是建议取较大的质数（常用的有\(10^9+7,998244353\)）作为\(P\)，以免被hack导致丢分。
这里我用的哈希函数为\(H(x)=x(x+93)(x+117)\bmod(2^{32}-1)\)，即\(A=93,B=117,P=2^{32}-1\)。
#include <cstdio>
#include <unordered_set>
#define maxn 200005
using namespace std;
inline int read()
{
char c;
while((c = getchar()) < '0' || c > '9');
int res = c ^ 48;
while((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c ^ 48);
return res;
}
unsigned suma[maxn], sumb[maxn];
inline void hread(unsigned* psum, int n)
{
unordered_set<int> s;
for(int i=1, x; i<=n; i++)
{
psum[i] = psum[i - 1];
if(s.insert(x = read()).second)
psum[i] += x * unsigned(x + 93) * unsigned(x + 117);
}
}
int main()
{
int n = read();
hread(suma, n);
hread(sumb, n);
for(int q=read(); q--;)
puts(suma[read()] == sumb[read()]? "Yes": "No");
return 0;
}