求助线段树TLE

感觉理论复杂度正确，本地怎么造数据也都没问题，但是T三个点。想求一下造数据的指点，什么情况下会被卡。

下面是代码的问题片段（修改操作），f记的是平方次数，cnt记该线段内值大于一的点数。

CPP

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);
}

讨论操作

回复

相关推荐

求助线段树TLE