题目列表

数据范围

赌徒

数学题，分类讨论。不多说。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void gmx(T &x, T y) { x = max(x, y); }
template <typename T>
void gmn(T &x, T y) { x = min(x, y); }
typedef long long ll;
void solve()
{
    ll a, b, c;
    cin >> a >> b >> c;
    if (!c)
        return puts(!b ? "Ivor" : "Harper"), void();
    puts(a + b <= c && b ^ c && b || (b % c & 1) && !(c & 1) ? "Harper" : "Ivor");
}
int main()
{
    freopen("gambler.in", "r", stdin);
    freopen("gambler.out", "w", stdout);
    int x;
    cin >> x;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

残片

没改好。

代码

护手

没有强制在线，我只用莫队！！1

首先你会发现这道题长了一脸莫队的样子，区间询问又是可以离线的。

然后你直接拍一个莫队上去，会发现 $T=0$ 奇数分是很好拿的。因为我们知道 $x \oplus x=0,x\oplus 0=x$，那么奇数次出现就是区间所有的异或起来。只拿这个分甚至可以维护前缀直接异或直接 $\mathcal O(1)$ 回答问题。

~~但事实上我考场是凑了半天发现不用判断是第几次出现直接异或就可以的。~~

然后你考虑偶数的怎么搞，你想，区间里非重复元素的集合减去出现奇数次元素集合不就是出现偶数次元素集合吗！

所以你维护某个区间去重之后的元素的异或，把偶数当成奇数做，最后和上树的去重元素异或异或一下就好。

去重元素异或维护很容易，统计每个数出现次数，删去之后全都没了和加上之后是第一次都异或起来。得分 $83\ \text{pts}$。

怎么回事呢？

考虑进行卡常。

我们会发现我们 不在意每个数具体出现多少次，只在意他前面和后面出现的位置。 因为我们只需要判断是否在区间内出现过。

考虑维护 $pre_i$ 表示第 $i$ 个位置上一个与其相等元素位置，$nxt_i$ 表示第 $i$ 个位置下一个与其相等元素位置。

然后莫队区间移动只需要判断 $pre,nxt,l,r$ 的大小关系了。本地测试最长点耗时 $1.7\ \text{s}$。

再插一嘴，你要是 $nxt,pre$ 或者是 $83\ \text{pts}$ 做法维护的数字出现次数的数组，用 map/unordered_map 是真的要死。map 稳定 $\log$，unordered_map 均摊常数实则会被卡到线性。

你复杂度再乘上一个 $\log$ 你卡的过去？？？

离散化，离散化，离散化！

代码

#include <bits/stdc++.h>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
inline int read()
{
    register char c = getchar();
    register int x = 0;
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}
int n, Q;
int a[800020];
struct node
{
    int l, r, t, id;
} query[700020];
int ans[700020];
int b[800020];
int p[800020];
int mp[800020];
int pos[800020];
int fa[800020];
int pre[800020];
int nxt[800020];
int len;
int ANS, X;
inline bool cmp(node a, node b) { return pos[a.l] ^ pos[b.l] ? pos[a.l] < pos[b.l] : pos[a.l] & 1 ? a.r > b.r
                                                                                                  : a.r < b.r; }
int main()
{
    freopen("gauntlet.in", "r", stdin);
    freopen("gauntlet.out", "w", stdout);
    register int subtask;
    subtask = read();
    n = read();
    Q = read();
    len = sqrt(n);
    for (register int i = 1; i <= n; i++)
        a[i] = b[i] = read();
    sort(b + 1, b + n + 1);
    register int m = unique(b + 1, b + n + 1) - b;
    for (register int i = 1; i <= n; i++)
    {
        register int j = lower_bound(b + 1, b + m + 1, a[i]) - b;
        p[j] = a[i];
        a[i] = j;
        pos[i] = (i + len - 1) / len;
    }
    for (register int i = 1; i <= n; i++)
    {
        nxt[i] = n + 1;
        pre[i] = fa[a[i]];
        nxt[pre[i]] = i;
        fa[a[i]] = i;
    }
    for (register int i = 1; i <= Q; i++)
    {
        int l, r, t;
        l = read();
        r = read();
        t = read();
        query[i] = {l, r, t, i};
    }
    sort(query + 1, query + Q + 1, cmp);
    register int l = 1, r = 0;
    for (register int i = 1; i <= Q; i++)
    {
        while (l < query[i].l)
        {
            ANS ^= p[a[l]];
            // del(l++);
            if (nxt[l] > r)
                X ^= p[a[l]];
            l++;
        }
        while (r > query[i].r)
        {
            ANS ^= p[a[r]];
            if (pre[r] < l)
                X ^= p[a[r]];
            r--;
        }
        while (l > query[i].l)
        {
            l--;
            ANS ^= p[a[l]];
            if (nxt[l] > r)
                X ^= p[a[l]];
        }
        while (r < query[i].r)
        {
            r++;
            ANS ^= p[a[r]];
            if (pre[r] < l)
                X ^= p[a[r]];
        }
        if (!query[i].t)
            ans[query[i].id] = ANS;
        else
            ans[query[i].id] = ANS ^ X;
    }
    for (register int i = 1; i <= Q; i++)
        printf("%d\n", ans[i]);
    return 0;
}
/*
inline void add(int i)
{
    mp[a[i]]++;
    ANS ^= p[a[i]];
    if (mp[a[i]] == 1)
        X ^= p[a[i]];
}
inline void del(int i)
{
    mp[a[i]]--;
    ANS ^= p[a[i]];
    if (mp[a[i]] == 0)
        X ^= p[a[i]];
}
*/