洛谷偶遇超强数据线段树哈希题,拼尽全力无法战胜
查看原帖
洛谷偶遇超强数据线段树哈希题,拼尽全力无法战胜
657413
Ayxrakzil楼主2025/6/17 21:39

一次又一次地找到 hack 数据,已力竭,跪求条/ll

#include <bits/stdc++.h>

#define int long long
#define ls k << 1
#define rs k << 1 | 1

const int N = 5e5 + 5, base = 23333, mod = 998244353;

int n, a[N], b[N];
struct node {
    int l, r;
    int h1, h2;
} c[N << 2];

int read() {
    int res = 0, i = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') i = -i;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res * i;
}

void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

void build(int k, int l, int r) {
    c[k].l = l, c[k].r = r;
    c[k].h1 = c[k].h2 = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void pushup(int k) {
    c[k].h1 = c[ls].h1 * b[c[rs].r - c[rs].l + 1] % mod + c[rs].h1;
    c[k].h2 = c[rs].h2 * b[c[ls].r - c[ls].l + 1] % mod + c[ls].h2;
}

void modify(int k, int pos) {
    if (c[k].l == c[k].r) {
        c[k].h1 = c[k].h2 = 1;
        return;
    }
    int mid = c[k].l + c[k].r >> 1;
    if (pos <= mid) modify(ls, pos);
    else modify(rs, pos);
    pushup(k);
}

int query1(int k, int l, int r) {
    // write(k), putchar(' '), write(l), putchar(' '), write(r), puts("");
    if (l <= c[k].l && c[k].r <= r) return c[k].h1;
    int mid = c[k].l + c[k].r >> 1;
    if (r <= mid) return query1(ls, l, r);
    if (l > mid) return query1(rs, l, r);
    return query1(ls, l, mid) * b[r - mid] % mod + query1(rs, mid + 1, r);
}

int query2(int k, int l, int r) {
    if (l <= c[k].l && c[k].r <= r) return c[k].h2;
    int mid = c[k].l + c[k].r >> 1;
    if (r <= mid) return query2(ls, l, r);
    if (l > mid) return query2(rs, l, r);
    return query2(rs, mid + 1, r) * b[mid - l + 1] % mod + query2(ls, l, mid);
}

void Main() {
    n = read();
    b[0] = 1;
    for (int i = 1; i <= n; ++i) b[i] = b[i - 1] * base % mod;
    for (int i = 1; i <= n; ++i) a[i] = read();
    build(1, 1, n);
    // for (int i = 1; i <= n; ++i) modify(1, i);
    // write(query1(1, 2, 5)), puts("");
    for (int i = 1, l, r, h1, h2; i <= n; ++i) {
        modify(1, a[i]);
        l = std::max(1ll, a[i] * 2 - n);
        r = std::min(n, a[i] * 2 - 1);
        // write(a[i]), putchar(' '), write(l), putchar(' '), write(r), puts("");
        if (a[i] == 1 || a[i] == n) continue;
        // write(l), putchar(' '), write(a[i] - 1), putchar(' '), write(a[i] + 1), putchar(' '), write(r), puts("");
        h1 = query1(1, l, a[i] - 1), h2 = query2(1, a[i] + 1, r);
        // write(h1), putchar(' '), write(h2), puts("");
        if (h1 != h2) {
            puts("Y");
            return;
        }
    }
    puts("N");
}

signed main() {
    int T = read();
    while (T--) Main();
    return 0;
}
/*
1
10
1 9 5 3 7 4 8 10 2 6
*/
2025/6/17 21:39
加载中...