2021 牛客多校第 3 场
F. 24dian
题意
输入
做法 (非标准)
对于
对于
对于

我们的表还被出题人讲题的时候不小心放到屏幕上了, 然后出题人一看心想“woc 这什么傻逼”,赶紧切走了。
I. Kuriyama Mirai and Exclusive Or
题意
给你一个数列
做法 (非标准)
第一种操作就跟没有一样,放到校赛都能过
对于第二种操作,我们按位讨论。操作对于第
对于 bitset
存这个二进制数。
考虑两种情况的阈值
经过一通操作会发现这个东西是
注意为了达到这个复杂度,不能每次都用 bitset<len>
(len
是 fuck<t>
调用 fuck<t-1>
这样的模板元编程 (TMP)
技巧实现对 毒瘤人展示这种写法,
把代码贴出来康康:
#include <bits/stdc++.h>
using namespace std;
static int a[600000];
struct Q
{
int tp, l, r, x;
};
static Q q[400000];
static int f[600000];
enum { t = 10 };
struct Q1
{
int l, x;
bool operator<(const Q1 &rhs) const
{
return l < rhs.l;
}
};
static Q1 q1[800000];
template <int k>
void fuck(int m, int n)
{
bitset<(1 << k)> stat = 0;
bitset<(1 << k)> val = 0;
int b = 1 << (k - 1);
int period = b + b;
int mask = period - 1;
for (int i = b; i < period; i++)
val[i] = 1;
for (int i = 0, j = 0; i < n; i++) {
for (; j < m && q1[j].l <= i; j++) {
int x = q1[j].x & mask;
stat = stat ^ (val >> x) ^ (val << (period - x));
}
if (stat[0])
a[i] ^= b;
int xx = stat[0];
stat >>= 1;
stat[period - 1] = xx;
}
fuck<k - 1>(m, n);
}
template<> void fuck<0>(int, int) {}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < m; i++)
scanf("%d%d%d%d", &q[i].tp, &q[i].l, &q[i].r, &q[i].x);
for (int i = 0; i < m; i++)
if (q[i].tp == 0) {
f[q[i].l - 1] ^= q[i].x;
f[q[i].r] ^= q[i].x;
} else {
for (int k = t + 1; k < 30; k++) {
int b = 1 << k;
int period = b + b;
int mask = period - 1;
int x = q[i].x & mask;
int xx = max(x, b);
int l = q[i].l + xx - x;
int r = l + mask - xx;
if (l <= q[i].r) {
f[l - 1] ^= b;
f[min(r, q[i].r)] ^= b;
}
for (l = r + b + 1; l <= q[i].r; l += period) {
f[l - 1] ^= b;
f[min(l + b - 1, q[i].r)] ^= b;
}
}
}
int acc = 0;
for (int i = 0; i < n; i++)
a[i] ^= (acc ^= f[i]);
int mm = 0;
for (int i = 0; i < m; i++)
if (q[i].tp == 1) {
q1[mm++] = {q[i].l - 1, q[i].x};
q1[mm++] = {q[i].r, q[i].x + (q[i].r - q[i].l + 1)};
}
sort(q1, q1 + mm);
fuck<t + 1>(mm, n);
for (int i = 0; i < n; i++)
printf("%d%c", a[i], " \n"[i + 1 == n]);
return 0;
}
这个题主要教训一个是这种分类讨论题如果阈值定不下来可以直接试 (反正本来算得也不准,因为没考虑常数), 另一个是不要混用闭区间和左闭右开区间,否则会很难受。