不是很常规的题目。
考虑奶牛之间的相对位置。因为一头奶牛最多跳出来一次，所以两头奶牛的相对位置最多改变两次。这样就可以求出任意两头奶牛的相对位置。
这样的话直接自定义一个比较奶牛的函数然后 sort 一遍就好了。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int x[20005];
int a[20005][6];
int pos[20005][6];
int s[20005];
bool cmp(int x, int y) {
int cnt = 0;
for (int i = 1; i <= 5; i++)
if (pos[x][i] < pos[y][i]) cnt++;
return cnt >= 3;
}
int main() {
cin >> n;
for (int j = 1; j <= 5; j++)
for (int i = 1; i <= n; i++)
cin >> a[i][j];
for (int i = 1; i <= n; i++) x[i] = a[i][1];
sort(x + 1, x + 1 + n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 5; j++)
a[i][j] = lower_bound(x + 1, x + 1 + n, a[i][j]) - x;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 5; j++)
pos[a[i][j]][j] = i;
for (int i = 1; i <= n; i++) s[i] = i;
sort(s + 1, s + 1 + n, cmp);
for (int i = 1; i <= n; i++)
cout << x[s[i]] << endl;
return 0;
}
相当妙的一道题。
因为这是 Ynoi，所以考虑分块。将 \(1-n\) 的序列进行分块，设块长为 \(\sqrt n\)。由于一个点的所有祖先的编号都小于这个点，所以维护一下每个点的第一个 不和自己在同一个块内 的祖先 \(f\)。这样查询 LCA 可以通过类似树链剖分的方式做到 \(O(\sqrt n)\)。
再考虑修改。一个块被修改 \(\sqrt n\) 次后，块内每个点的父亲都必定不在当前块内。因此每个点的 \(f\) 值就是父亲。于是每个块经过 \(\sqrt n\) 次修改就可以直接打懒标记了。那么对于这 \(\sqrt n\) 次修改，考虑 \(O(\sqrt n)\) 暴力重构 \(f\) 值。这样 \(\sqrt n\) 个块，每个块至多被 \(O(\sqrt n)\) 地重构 \(\sqrt n\) 次，于是这部分的复杂度就做到了 \(O(n\sqrt n)\)。
总的时间复杂度为 \(O(n\sqrt n)\)。
lxl 难得良心一次，本题完全不卡常，代码也很短。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 400005;
int n, m;
int a[maxn];
int l[maxn], r[maxn], pos[maxn];
int t[maxn], cnt[maxn], f[maxn];
int lastans;
int top(int x) {return max(t[x] - f[pos[x]], 1);}
void rebuild(int x) {
for (int i = l[x]; i <= r[x]; i++)
if (a[i] < l[x]) t[i] = a[i];
else t[i] = t[a[i]];
}
void init() {
int block = sqrt(n), g = ceil(n * 1. / block);
for (int i = 1; i <= g; i++) {
l[i] = (i - 1) * block + 1; r[i] = min(i * block, n);
for (int j = l[i]; j <= r[i]; j++) pos[j] = i;
rebuild(i);
}
}
void update(int x, int y, int k) {
int p = pos[x], q = pos[y];
if (p == q) {
for (int i = x; i <= y; i++) a[i] = max(a[i] - k, 1);
rebuild(p);
return;
}
for (int i = p + 1; i <= q - 1; i++) {
if (++cnt[i] >= sqrt(n)) f[i] = min(n, f[i] + k);
else {
for (int j = l[i]; j <= r[i]; j++) a[j] = max(a[j] - k, 1);
rebuild(i);
}
}
for (int i = x; i <= r[p]; i++) a[i] = max(a[i] - k, 1);
for (int i = l[q]; i <= y; i++) a[i] = max(a[i] - k, 1);
rebuild(p); rebuild(q);
}
int query(int u, int v) {
while (1) {
if (u < v) swap(u, v);
if (pos[u] != pos[v]) u = top(u);
else if (top(u) != top(v)) u = top(u), v = top(v);
else break;
}
while (u != v) {
if (u < v) swap(u, v);
u = max(a[u] - f[pos[u]], 1);
}
return u;
}
int main() {
cin >> n >> m;
for (int i = 2; i <= n; i++)
scanf("%d", &a[i]);
init();
for (int i = 1; i <= m; i++) {
int p, x, y, k; scanf("%d", &p);
if (p == 1) {
scanf("%d%d%d", &x, &y, &k);
x ^= lastans; y ^= lastans; k ^= lastans;
update(x, y, k);
} else {
scanf("%d%d", &x, &y);
x ^= lastans; y ^= lastans;
printf("%d\n", lastans = query(x, y));
}
}
return 0;
}
因为这是 Ynoi，所以考虑分块。预处理出 \(ansl_{i,j}\) 表示第 \(i\) 块的左端点到 \(j\) 这个区间的逆序对数，\(ansr_{i,j}\) 表示第 \(i\) 块的右端点到 \(j\) 这个区间的逆序对数。预处理的时候用树状数组维护一下，即可做到 \(O(1)\) 地移动端点。
查询时把区间分成左散块、右散块和中间完整块。用 左散块和中间完整块组成的区间 的逆序对，加上 右散块和中间完整块组成的区间 的逆序对，减去中间完整块的逆序对，再加上左散块对右散块的贡献即可。
显然前三个东西都是可以直接利用 \(ans\) 求的。而最后一个东西，只需要在预处理的时候保存块内排序的结果，然后归并扫一遍即可。
时空复杂度均为 \(O(n\sqrt n)\)。
本题卡常，考虑 IO 优化，再瞎调块长，卡卡过掉了。
但不保证任何时刻都能通过此题。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5, maxb = 205;
int n, m, block, t;
ll last;
int a[maxn], st[maxb], ed[maxb], pos[maxn];
int cnt[maxn], pre[maxn], suf[maxn], P1[maxn], P2[maxn];
int c1[maxb][maxn], c2[maxb][maxn];
ll ansl[maxb][maxn], ansr[maxb][maxn];
int qa[maxn], qb[maxn];
int nmsl[20], len;
struct node {
int id, val;
bool operator < (const node &a) const {return val < a.val;}
} b[maxn];
struct BIT {
int sum[maxn];
inline int lowbit(int x) {return x & -x;}
inline void update(int x, int val) {
for (; x <= n; x += lowbit(x))
sum[x] += val;
}
inline int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += sum[x];
return res;
}
} tr;
namespace fastIO {
const int buffer_size = 1024 * 1024 * 40;
char input[buffer_size], output[buffer_size];
char *fin, *fout;
inline void init() {
fread(input, 1, buffer_size, stdin);
fin = input; fout = output;
}
inline void flush() {
fwrite(output, 1, fout - output, stdout);
fflush(stdout);
}
inline int read(int u = 0, char c = *fin++, bool f = false) {
for (; !isdigit(c); c = *fin++) f |= c == '-';
for (; isdigit(c); c = *fin++) u = u * 10 + c - '0';
return f ? -u : u;
}
inline void read(char *s, char c = *fin++) {
for (; !isspace(c); c = *fin++);
for (; isspace(c); c = *fin++) *s++ = c;
*s = '\0';
}
inline void print(ll u) {
u < 0 ? *fout++ = '-', print(-u) : void(u > 9 ? print(u / 10), *fout++ = u % 10 + '0' : *fout++ = u + '0');
}
inline void print(char *s) {while (*s) *fout++ = *s++; }
inline void print(char c) {*fout++ = c; }
}
using fastIO::read;
using fastIO::print;
inline void init() {
block = 500; t = ceil(n * 1. / block);
for (register int i = 1; i <= t; ++i) {
st[i] = (i - 1) * block + 1; ed[i] = min(i * block, n);
for (register int j = st[i]; j <= ed[i]; ++j) pos[j] = i, b[j] = (node){j, a[j]};
sort(b + st[i], b + ed[i] + 1);
}
for (register int i = 1; i <= t; ++i) {
for (register int j = st[i]; j <= ed[i]; ++j) {pre[j] = tr.query(n) - tr.query(a[j]); tr.update(a[j], 1);}
for (register int j = st[i]; j <= ed[i]; ++j) tr.update(a[j], -1);
for (register int j = ed[i]; j >= st[i]; --j) {suf[j] = tr.query(a[j]); tr.update(a[j], 1);}
for (register int j = ed[i]; j >= st[i]; --j) tr.update(a[j], -1);
P1[st[i]] = P2[ed[i]] = 0;
for (int j = st[i] + 1; j <= ed[i]; ++j) P1[j] = P1[j - 1] + pre[j];
for (int j = ed[i] - 1; j >= st[i]; --j) P2[j] = P2[j + 1] + suf[j];
}
for (register int i = 1, p = 1; i <= n; ++i) {
cnt[a[i]]++;
if (i == ed[p]) {
for (register int j = 1; j <= n; ++j) c1[p][j] = c1[p][j - 1] + cnt[j];
for (register int j = n; j >= 1; --j) c2[p][j] = c2[p][j + 1] + cnt[j];
p++;
}
}
for (register int i = 1; i <= t; ++i) {
for (register int j = st[i]; j <= n; ++j) ansl[i][j] = ansl[i][j - 1] + c2[pos[j] - 1][a[j]] - c2[i - 1][a[j]] + pre[j];
for (register int j = ed[i]; j >= 1; --j) ansr[i][j] = ansr[i][j + 1] + c1[i][a[j]] - c1[pos[j]][a[j]] + suf[j];
}
}
inline ll query(register int l, register int r) {
int x = pos[l], y = pos[r];
if (x == y) {
int p = 1, q = 1, cnt1 = 0, cnt2 = 0; ll ans = ansl[x][r] - ansl[x][l - 1];
for (register int i = st[x]; i <= ed[x]; ++i)
if (b[i].id < l) qa[++cnt1] = b[i].val;
else if (b[i].id <= r) qb[++cnt2] = b[i].val;
while (p <= cnt1 && q <= cnt2)
if (qa[p] <= qb[q]) p++;
else q++, ans -= cnt1 - p + 1;
return ans;
}
int p = 1, q = 1, cnt1 = 0, cnt2 = 0;
ll ans = (y - x > 1 ? ansl[x + 1][r] + ansr[y - 1][l] - ansl[x + 1][st[y] - 1] : P1[r] + P2[l]);
for (register int i = st[x]; i <= ed[x]; ++i)
if (b[i].id >= l) qa[++cnt1] = b[i].val;
for (register int i = st[y]; i <= ed[y]; ++i)
if (b[i].id <= r) qb[++cnt2] = b[i].val;
while (p <= cnt1 && q <= cnt2)
if (qa[p] <= qb[q]) p++;
else q++, ans += cnt1 - p + 1;
return ans;
}
int main() {
fastIO::init();
n = read(); m = read();
for (register int i = 1; i <= n; ++i) a[i] = read();
init();
for (register int i = 1; i <= m; ++i) {
int l = read(), r = read();
l ^= last; r ^= last; last = query(l, r);
printf("%lld\n", last);
}
return 0;
}
感觉 USACO 思路奇葩的题目相当多啊。
考虑把数组从 \(a_x\) 和 \(a_{x+1}\) 中间劈开，划分成 \(AB\) 两个部分。易知每次冒泡之后，\(A\) 中都有且仅有一个数跑到了 \(B\) 里面去，\(B\) 也有且仅有一个数跑到了 \(A\) 去。因此将最小的 \(x\) 个数全部放到 \(A\) 里面所需的冒泡次数，就是原本在 \(A\) 但需要去 \(B\) 的元素的数量。显然这个东西可以树状数组搞。
那么枚举 \(x\) 的位置然后取个 max 就好了。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int pos[100005];
pair<int, int> d[100005];
int ans = 1;
struct BIT {
int sum[100005];
int lowbit(int x) {return x & -x;}
void update(int x) {
for (; x <= n; x += lowbit(x))
sum[x]++;
}
int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += sum[x];
return res;
}
} t;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> d[i].first;
d[i].second = i;
}
sort(d + 1, d + 1 + n);
for (int i = 1; i <= n; i++)
pos[d[i].second] = i;
for (int i = 1; i <= n; i++) {
t.update(pos[i]);
ans = max(ans, i - t.query(i));
}
cout << ans << endl;
return 0;
}
设 \(2^{2^{2\cdots}}=x\)，显然 \(2^x\equiv x\pmod p\)，因此只需求 \(2^x\bmod p\) 即可。根据欧拉定理， \(2^x\bmod p=2^{x\bmod \varphi(p)+\varphi(p)}\bmod p\)，所以求出指数，再快速幂就解决了。问题转化为求 \(x\bmod \varphi(p)\)。
可以发现，从求 \(x\bmod p\) 转化为求 \(x\bmod \varphi(p)\)，这是转化为了一个 规模更小，但形式相同 的问题。因此可以考虑不断递归下去。
递归边界为 \(x\bmod 1=0\)。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, p;
int phi[10000005];
vector<int> pr;
void getphi(int n) {
for (int i = 1; i <= n; i++) phi[i] = i;
for (int i = 2; i <= n; i++) {
if (phi[i] == i) phi[i] = i - 1, pr.push_back(i);
for (int j = 0; j < pr.size(); j++) {
int x = pr[j];
if (x * i > n) break;
if (i % x == 0) {phi[i * x] = phi[i] * x; break;}
else phi[i * x] = phi[i] * phi[x];
}
}
}
int power(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p; b >>= 1;
}
return res % p;
}
int get(int p) {
if (p == 1) return 0;
return power(2, get(phi[p]) + phi[p], p);
}
signed main() {
getphi(1e7);
cin >> t;
while (t--) {
cin >> p;
cout << get(p) << endl;
}
return 0;
}
来分析一波时间复杂度。每次将 \(p\) 取 \(\varphi\) 后，奇数会变成偶数，而偶数至少会减半，因此递归层数的上界为 \(2\log p\)，再加上快速幂，单次询问的复杂度即为 \(O(\log^2 n)\)。
我真是个 SB，，这么 naive 的结论没有想到。退役了退役了。
一个显然的想法是维护一个堆，但是会 T。
考虑如果蚯蚓 \(a\) 比蚯蚓 \(b\) 先被切掉，那么 \(a\) 分成的两条蚯蚓也一定分别比 \(b\) 分成的两条蚯蚓长。这相当于自带单调性。因此可以把堆扔掉了。维护三个队列，第一个放还没被切过的，第二个放被切过的蚯蚓左段，第三个放被切过的蚯蚓右段。然后取最大值的时候只要比较三个队头了。蚯蚓的生长打个标记就好。
代码
#include<bits/stdc++.h>
using namespace std;
int n, m, q, u, v, t;
int d[100005];
queue<int> a, b, c;
int get() {
int x, y, z, res;
x = (a.empty() ? -1e9 : a.front());
y = (b.empty() ? -1e9 : b.front());
z = (c.empty() ? -1e9 : c.front());
res = max(max(x, y), z);
if (res == x) a.pop();
else if (res == y) b.pop();
else c.pop();
return res;
}
int main() {
cin >> n >> m >> q >> u >> v >> t;
for (int i = 1; i <= n; i++) cin >> d[i];
sort(d + 1, d + 1 + n);
for (int i = n; i >= 1; i--) a.push(d[i]);
for (int i = 1; i <= m; i++) {
int res = get() + (i - 1) * q;
if (i % t == 0) cout << res << ' ';
b.push(1ll * res * u / v - i * q);
c.push(res - 1ll * res * u / v - i * q);
}
cout << endl;
for (int i = 1; i <= n + m; i++) {
int res = get();
if (i % t == 0) cout << res + m * q << ' ';
}
cout << endl;
return 0;
}
显然答案为 \(C_n^2\)。接下来考虑构造。
对于每一对 \((i,j)\)，都让兔子 \((j,j+i,j+2i)\) 出去站岗一次。手模一下发现这样可以使每一对兔子都恰好一起出去 \(3\) 次。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
int main() {
cin >> n;
cout << n * (n - 1) / 2 << endl;
for (int i = 1; i <= n / 2; i++)
for (int j = 1; j <= n; j++)
cout << j << ' ' << (j + i - 1) % n + 1 << ' ' << (j + 2 * i - 1) % n + 1 << endl;
return 0;
}
发现平凡的数据结构没有办法做，于是考虑随机化。
考虑哈希，给每一个数随机映射为另一个数，对每一个询问，判断这个区间的所有数的映射值之和是否为 \(k\) 的倍数。
在这个策略下，YES 不可能被错判成 NO，而 NO 被错判成 YES 的概率大致为 \(\frac{1}{k}\)。于是做 \(x\) 遍这个判断，单次询问出现错误的概率可以做到 \(\dfrac{1}{k^x}\)。这里设 \(x\) 为 \(40\) 是可以过的。
代码
// LUOGU_RID: 94434532
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300005;
int n, m, f;
int a[maxn], b[maxn];
int sum[maxn];
int lowbit(int x) {return x & -x;}
void update(int x, int y) {for (; x <= n; x += lowbit(x)) sum[x] += y;}
int query(int x) {int res = 0; for (; x; x -= lowbit(x)) res += sum[x]; return res;}
int mp[maxn << 1];
// unordered_map<int, int> mp;
int ind[maxn << 1], cnt;
struct node {int p, x, y, k;} d[maxn];
int ans[maxn];
inline int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
void discrete() {
for (int i = 1; i <= n; i++) ind[++cnt] = a[i];
for (int i = 1; i <= m; i++)
if (d[i].p == 1) ind[++cnt] = d[i].y;
sort(ind + 1, ind + 1 + cnt); int len = unique(ind + 1, ind + 1 + cnt) - ind - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(ind + 1, ind + 1 + len, a[i]) - ind;
for (int i = 1; i <= m; i++)
if (d[i].p == 1) d[i].y = lower_bound(ind + 1, ind + 1 + len, d[i].y) - ind;
}
int main() {
mt19937 rnd(time(0));
cin >> n >> m;
f = 40;
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= m; i++) {
d[i].p = read(); d[i].x = read(); d[i].y = read();
if (d[i].p == 2) {
d[i].k = read();
if ((d[i].y - d[i].x + 1) % d[i].k) ans[i] = 1;
}
}
discrete();
memcpy(b, a, sizeof(a));
for (int i = 1; i <= f; i++) {
memset(mp, 0, sizeof(mp));
memcpy(a, b, sizeof(b));
for (int j = 1; j <= n; j++) sum[j] = 0;
for (int j = 1; j <= n; j++) {
if (!mp[a[j]]) mp[a[j]] = rnd() % 7000 + 1;
update(j, mp[a[j]]);
}
for (int j = 1; j <= m; j++) {
if (d[j].p == 1) {
if (!mp[d[j].y]) mp[d[j].y] = rnd() % 7000 + 1;
update(d[j].x, mp[d[j].y] - mp[a[d[j].x]]);
a[d[j].x] = d[j].y;
}
else if ((query(d[j].y) - query(d[j].x - 1)) % d[j].k) ans[j] = 1;
}
}
for (int i = 1; i <= m; i++) {
if (d[i].p == 1) continue;
if (ans[i]) printf("NO\n");
else printf("YES\n");
}
return 0;
}