代码,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;
}