感觉理论复杂度正确,本地怎么造数据也都没问题,但是T三个点。想求一下造数据的指点,什么情况下会被卡。
下面是代码的问题片段(修改操作),f记的是平方次数,cnt记该线段内值大于一的点数。
void add(int p, int *x) {
x[p] = (1ll * x[p << 1] + x[p << 1 | 1]) % mod;
}
void down(int p) {
f[p << 1] += f[p]; f[p << 1 | 1] += f[p];
f[p] = 0;
}
void sq(int p, int l, int r, int ls, int rs, int op) {
if(!cnt[p]) return;
if(ls <= l && r <= rs && f[p] + op >= 0) {
f[p] += op; return;
}
if(l == r) {
if(~op) f[p]++;
else {if(f[p]) f[p]--; else t[p] = sqrt(t[p]);}
if(t[p] == 1) cnt[p] = 0;
return;
}
register int mid = l + r >> 1;
down(p);
if(ls <= mid) sq(p << 1, l, mid, ls, rs, op);
if(rs > mid) sq(p << 1 | 1, mid + 1, r, ls, rs, op);
add(p, cnt);
}