「題解」洛谷 CF1000F One Occurrence

題目

CF1000F One Occurrence

簡化題意

一個長為 \(n\) 的序列，每次詢問一個區間内隻出現過一次的數是什麼。

思路

莫隊 + 大力卡常 + O3。

考慮莫隊怎麼維護隻出現過一次的數，開個棧，棧中元素都是隻出現過一次的，如果一個數原本出現過一次在一次操作後不再是隻出現一次了，就把他在棧中的位置替換成棧頂的元素，清空一下各種标記啥的。最後棧中元素都是隻出現過一次的。

用到的卡常小技巧

• 奇偶性優化
• 塊大小開 \(\large\frac{n}{\sqrt{m}}\)
• O(3)

Code

#pragma GCC optimize (3)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 500001

inline void read(int &T) {
    int x = 0;
    bool f = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = !f;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    T = f ? -x : x;
}

void write(int x) {
    if (x / 10) write(x / 10);
    putchar(x % 10 + '0');
}

int n, m, top, a[MAXN], s[MAXN], pos[MAXN];
int sqrn, num[MAXN], cnt[MAXN], ans[MAXN];
struct query {
    int x, y, id;
    friend bool operator < (query q1, query q2) {
        return (num[q1.x] ^ num[q2.x]) ? num[q1.x] < num[q2.x] : (num[q1.x] & 1) ? q1.y < q2.y : q1.y > q2.y;
    }
}q[MAXN];

void add(int x) {
    ++cnt[x];
    if (cnt[x] == 1) {
        s[++top] = x, pos[x] = top;
    }
    else if (cnt[x] == 2) {
        s[pos[x]] = s[top];
        pos[s[top]] = pos[x];
        s[top--] = pos[x] = 0;
    }
}

void del(int x) {
    --cnt[x];
    if (cnt[x] == 1) {
        s[++top] = x, pos[x] = top;
    }
    else if (!cnt[x]) {
        s[pos[x]] = s[top];
        pos[s[top]] = pos[x];
        s[top--] = pos[x] = 0;
    }
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    read(m), sqrn = n / sqrt(m);
    for (int i = 1; i <= n; ++i) num[i] = (i - 1) / sqrn + 1;
    for (int i = 1; i <= m; ++i) {
        read(q[i].x), read(q[i].y);
        q[i].id = i;
    }
    std::sort(q + 1, q + m + 1);
    int l = 1, r = 1; add(a[l]);
    for (int i = 1; i <= m; ++i) {
        while (l > q[i].x) add(a[--l]);
        while (r < q[i].y) add(a[++r]);
        while (l < q[i].x) del(a[l++]);
        while (r > q[i].y) del(a[r--]);
        ans[q[i].id] = s[top];
    }
    for (int i = 1; i <= m; ++i) {
        write(ans[i]);
        puts("");
    }
    return 0;
}