分块TLE on #9求助

P2801 教主的魔法

紊莫 @ 2022-12-04 11:06:01

算法的正确性没有问题，但是可能我人傻常数大，求助大佬应该怎么修改？？

code

by dxy2020 @ 2022-12-04 11:31:35

把块内排序改成归并试试？

不过按理说不用啊，是不是 $STL$ 常数大

by Albert_Wei @ 2022-12-04 11:41:59

@Velvet 时间复杂度是 O(n \sqrt n log n)，过不了吧……

by 紊莫 @ 2022-12-04 11:55:06

@Unbeliveble 不是O(n\sqrt{n}\log\sqrt{n})吗？

by 紊莫 @ 2022-12-04 11:56:14

是O(q...)，询问次数才3000

by 紊莫 @ 2022-12-04 12:00:56

艹破案了，在： 

for(int i=1;i<=sq;++i){
    for(int j=st[i];j<=ed[i];j++){
        v[i].push_back(a[j]);
    }
    sort(v[i].begin(),v[i].end());
}

没加bl[j]=i;

但是还是很疑惑，这么离谱却没导致WA而是复杂度退化？？

by 紊莫 @ 2022-12-04 12:01:47

懂了，此贴结

by Albert_Wei @ 2022-12-04 12:02:54

@Velvet 额那没事了

|