数据请求加强

这个题对于大于

\sqrt{n}

的部分单次复杂度为

O(m+size)

，但是注意到对于当前分治处理的树，其儿子数可能过大，如果全部采用上述做法，其单次复杂度实际上为

O((son+1)(m+size))

，其中

son

为儿子个数，复杂度显然不对。

正确做法应该是容斥儿子时，对儿子的大小也根号分治。

以下数据生成器能卡掉网上大部分题解和洛谷两篇题解中的一篇（另一篇没看懂

CPP

#include<bits/stdc++.h>
using namespace std;

int make(int l,int r);
int main(){
    freopen("in","w",stdout);
    int n=50000,m=50000;
    cout<<n<<" "<<m<<endl;
    for (int i=2;i<=n;i++) cout<<1<<" "<<i<<endl;
    for (int i=1;i<=n;i++) cout<<(char)make('a','c');cout<<endl;
    for (int i=1;i<=m;i++) cout<<(char)make('a','c');cout<<endl;
    fclose(stdout);return 0;
}
int make(int l,int r){
    double dou=1.0*rand()/RAND_MAX;
    return min(r,(int)(dou*(r-l+1)+l));
}

chen_zhe

讨论操作

回复

相关推荐

数据请求加强