哪儿 TLE 了,
查看原帖
哪儿 TLE 了,
809729
SJZ2010楼主2023/11/12 22:29

代码,Trie 上打懒标记,哪里会导致 TLE???

#include <cstdio>
#include <vector>

const int N = 2e5 + 5;

int n, m, op, x, y, v;
long long ans;

struct Segment_Trie
{
    int cnt;
    int next[N * 24][2], tag[N * 24], size[N * 24];
    long long sum[N * 24];

    void pushdown(int idx)
    {
        if (!tag[idx])
            return;
        int nxt;
        if (next[idx][0])
        {
            nxt = next[idx][0];
            tag[nxt] += tag[idx];
            sum[nxt] += tag[idx] * size[nxt];
        }
        if (next[idx][1])
        {
            nxt = next[idx][1];
            tag[nxt] += tag[idx];
            sum[nxt] += tag[idx] * size[nxt];
        }
        tag[idx] = 0;
    }

    void Insert(int key, int val)
    {
        int i, pos(0);
        for (i = 0; i < 24; i++)
        {
            sum[pos] += val;
            size[pos]++;
            if (!next[pos][key & (1 << i)])
                pos = next[pos][key & (1 << i)] = ++cnt;
            else
                pos = next[pos][key & (1 << i)];
        }
        sum[pos] = val;
        size[pos] = 1;
    }
    
    void Modify(int depth, int key, int val)
    {
        int i, pos(0);
        std::vector < int > visit;
        if ((1 << x) > n && y <= n)
            depth = 24;
        for (i = 0; i < depth; i++)
        {
            pushdown(pos);
            visit.push_back(pos);
            if (!next[pos][key & (1 << i)])
                return;
            pos = next[pos][key & (1 << i)];
            key >>= 1;
        }
        sum[pos] += 1ll * size[pos] * val;
        tag[pos] += val;
        for (i = 0; i < visit.size(); i++)
            sum[visit[i]] += 1ll * size[pos] * val;
    }
    long long Query(int depth, int key)
    {
        int i, pos(0);
        for (i = 0; i < depth; i++)
        {
            pushdown(pos);
            if (!next[pos][key & (1 << i)])
                return 0;
            pos = next[pos][key & (1 << i)];
        }
        return sum[pos];
    }
} Trie;

int read()
{
    int res(0), ch(getchar());
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
    {
        res = res * 10 + (ch ^ '0');
        ch = getchar();
    }
    return res;
}

int main()
{
    n = read(), m = read();
    int i;
    for (i = 1; i <= n; i++)
        Trie.Insert(i, read());
    while (m--)
    {
        op = ((read() + ans) & 1);
        if (op)
        {
            x = read(), y = read();
            ans = Trie.Query(x, y & ((1 << x) -1));
            printf("%lld\n", ans);
        }
        else
        {
            x = read(), y = read(), v = read();
            Trie.Modify(x, y & ((1 << x) -1), v);   
        }
    }
    return 0;
}
2023/11/12 22:29
加载中...