社区讨论

超雄根号log WA0pts求条

ttruewater
P5386[Cnoi2019] 数字游戏参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mk668rg7
此快照首次捕获于
2026/01/09 09:02
上个月
此快照最后确认于
2026/01/11 13:15
上个月
查看原帖
做法：跑完值域莫队后，使用线段树维护区间答案
复杂度分析：注意到因为莫队，所以n\sqrt n次修改才会有一次查询，考虑使用线段树顶层分块，修改的时候少遍历上面的节点优化常数。
再考虑使用线段树底层分块+压位预处理优化时间复杂度，可以减少线段树常数至20(4⋅log500164 \cdot log \frac{500}{16})，带上将莫队卡满的1.4常数，总大概会跑到3e9。时限7s（后续考虑写zkw)。
但是现在代码只过了样例，其他全部WA，请求dalao求条：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 510, K = 16, E = 1 << K, B = 200;
int n, m, len = 512, a[N], id[N], ans[N], lb[M], rb[M];
int get(int x)
{
    return (x + len - 1) / len;
}
struct GG
{
    int id, l, r, x, y;
    bool operator<(const GG &t) const
    {
        if (get(x) != get(t.x))
            return x < t.x;
        return r < t.r;
    }
} q[N];
struct GG1
{
    int pre, suf, ans, len;
} tr[M][B], init[E];
int mask[M][B];
GG1 blk_query(int blk, int l, int r)
{
    int pre = 0, suf = 0, ans = 0;
    for (int i = l; i <= r; i++)
    {
        if (a[i] <= 0)
            break;
        pre++;
    }
    for (int i = r; i >= l; i--)
    {
        if (a[i] <= 0)
            break;
        suf++;
    }
    int len = 0;
    for (int i = l + pre; i <= r - suf; i++)
    {
        if (a[i] && a[i + 1] <= 0)
        {
            ans += len * (len + 1) / 2;
            len = 0;
        }
        else if (a[i])
            len++;
    }
    return {pre, suf, ans, r - l + 1};
}
GG1 merge(GG1 L, GG1 R)
{
    GG1 tmp;
    tmp.ans = L.ans + R.ans;
    tmp.len = L.len + R.len;
    if (L.len == L.pre)
        tmp.pre = L.len + R.pre;
    else
        tmp.pre = L.pre;
    if (R.len == R.suf)
        tmp.suf = L.suf + R.len;
    else
        tmp.suf = R.suf;
    if (L.len != L.pre && R.suf != R.len)
    {
        tmp.ans += (L.suf + R.pre) * (L.suf + R.pre - 1) / 2;
    }
    return tmp;
}
GG1 query(int blk, int u, int l, int r, int L, int R)
{
    if (r - l + 1 <= K)
    {
        return blk_query(blk, max(l, L), min(r, R));
    }
    if (L <= l && r <= R)
    {
        return tr[blk][u];
    }
    int mid = (l + r) >> 1;
    if (L > mid)
        return query(blk, u << 1 | 1, mid + 1, r, L, R);
    else if (R <= mid)
        return query(blk, u << 1, l, mid, L, R);
    else
    {
        return merge(query(blk, u << 1, l, mid, L, R), query(blk, u << 1 | 1, mid + 1, r, L, R));
    }
}
void modify(int blk, int u, int l, int r, int v, int p)
{
    if (r - l + 1 <= K)
    {
        if (p)
            mask[blk][u] |= 1 << (v - l);
        else
            mask[blk][u] ^= 1 << (v - l);
        a[v] = p;
        tr[blk][u] = init[mask[blk][u]];
        return;
    }
    int mid = (l + r) >> 1;
    if (v <= mid)
        modify(blk, u << 1, l, mid, v, p);
    else
        modify(blk, u << 1 | 1, mid + 1, r, v, p);
    tr[blk][u] = merge(tr[blk][u << 1], tr[blk][u << 1 | 1]);
}
GG1 merge1(GG1 L, GG1 R)
{
    GG1 tmp;
    tmp.ans = L.ans + R.ans;
    tmp.len = L.len + R.len;
    if (L.len == L.pre)
        tmp.pre = L.len + R.pre;
    else
        tmp.pre = L.pre;
    if (R.len == R.suf)
        tmp.suf = L.suf + R.len;
    else
        tmp.suf = R.suf;
    if (L.len != L.pre && R.suf != R.len)
    {
        tmp.ans += (L.suf + R.pre) * (L.suf + R.pre + 1) / 2;
    }
    return tmp;
}
int qry(int l, int r)
{
    int blk1 = get(l), blk2 = get(r);
    GG1 T = {0, 0, 0, 0};
    if (blk1 == blk2)
    {
        T = query(blk1, 1, 1, len, l - lb[blk1] + 1, r - lb[blk2] + 1);
    }
    else
    {
        T = query(blk1, 1, 1, len, l - lb[blk1] + 1, len);
        for (int i = blk1 + 1; i < blk2; i++)
        {
            T = merge(T, query(i, 1, 1, len, 1, len));
        }
        T = merge(T, query(blk2, 1, 1, len, 1, r - lb[blk2] + 1));
    }
    if (T.suf == T.len)
    {
        return T.len * (T.len + 1) / 2;
    }
    return T.ans + T.suf * (T.suf + 1) / 2 + T.pre * (T.pre + 1) / 2;
}
void add(int x)
{
    int blk = get(id[x]);
    modify(blk, 1, 1, len, id[x] - lb[blk] + 1, 1);
}
void del(int x)
{
    int blk = get(id[x]);
    modify(blk, 1, 1, len, id[x] - lb[blk] + 1, 0);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], id[a[i]] = i;
    for (int x = 0; x < (1 << K); x++) // 底层分块预处理
    {
        int pre = 0, suf = 0, ans = 0, llen = 0;
        for (int i = 0; i < K; i++)
        {
            if ((x >> i) & 1)
                pre++;
            else
                break;
        }
        for (int i = K - 1; i >= 0; i--)
        {
            if ((x >> i) & 1)
                suf++;
            else
                break;
        }
        for (int i = pre; i < K - suf; i++)
        {
            if ((x >> i) & 1)
            {
                llen++;
                if (!(x >> (i + 1) & 1))
                {
                    ans += llen * (llen + 1) / 2;
                    llen = 0;
                }
            }
        }
        init[x] = {pre, suf, ans, K};
    }
    for (int i = 1; i <= m; i++)
    {
        q[i].id = i;
        cin >> q[i].l >> q[i].r >> q[i].x >> q[i].y;
    }
    for (int i = 1; i; i++)
    {
        lb[i] = rb[i - 1] + 1;
        rb[i] = lb[i] + len - 1;
        if (rb[i] > n)
        {
            rb[i] = n;
            break;
        }
    }
    sort(q + 1, q + 1 + m);
    for (int i = 1, l = 1, r = 0; i <= m; i++) // 值域上跑莫队
    {
        int L = q[i].x, R = q[i].y;
        while (r < R)
            add(++r);
        while (r > R)
            del(r--);
        while (l < L)
            del(l++);
        while (l > L)
            add(--l);
        ans[q[i].id] = qry(q[i].l, q[i].r);
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i] << " ";
}

回复

共 1 条回复，欢迎继续交流。

正在加载回复...