根号分治

lao_li · 2023-01-13 11:50:05 · 个人记录

选定一个阈值，根据数据的大小对不同的数据进行不同的操作，平衡复杂度。

一般复杂度和根号有关，看到时限较大的可以考虑。

P3396 哈希冲突

给一个序列，支持单点修改，查询\sum a_{i\mod p}，p在每次查询时给出。

不妨设一个阈值B。

如果p>B，我们在序列上暴力跳着直接加，复杂度O(\frac n B)。

如果p\leq B，不同的模数只有B种，对于每个模数暴力扫一遍序列预处理，O(nB)在更新的时候最多更新B个模数的答案，O(B)。

总复杂度O(nB+q(B+\frac n B))。

经实验，B= \sqrt[3]{n}时时间较优。

#include<bits/stdc++.h> 
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
typedef long long ll;
const int MAXN=150005;
int n,m,sz;
ll mem[390][390];
int a[MAXN];
int main(){
    read(n),read(m);
    rep(i,1,n)read(a[i]);
    sz=pow(n,0.333);
    int x,y;
    ll res;
    rep(i,1,n)
        rep(j,1,sz)mem[j][i%j]+=a[i];
    char o[5];
    while(m--){
        scanf("%s",o);
        read(x),read(y);
        if(o[0]=='A'){
            if(x<=sz)printf("%lld\n",mem[x][y]);
            else{
                res=0;
                for(int i=y;i<=n;i+=x)res+=a[i];
                printf("%lld\n",res);
            }
        }
        else{
            rep(i,1,sz)mem[i][x%i]+=y-a[x];
            a[x]=y;
        }
    }
    return 0;
}

Time to Raid Cowavans

和上题差不多，但是无修改，询问a_t+a_{t+k}+a_{t+2k}+...，并且卡空间。

把询问离线，对于每个小模数暴力重构一次后缀和序列，大模数还是直接暴力。

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
typedef long long ll;
const int MAXN=3e5+5;
int n,m,sz;
int a[MAXN];
ll s[MAXN],ans[MAXN];
struct qq{
    int t,k,id;
    bool operator<(const qq &T)const{
        return k<T.k;
    }
} q[MAXN];
void cal(int k){
    memset(s,0,sizeof(s));
    Rrep(i,n,1)
        s[i]=((i+k<=n)?s[i+k]:0)+a[i];
}
int main(){
    read(n);
    sz=sqrt(n);
    rep(i,1,n)read(a[i]);
    read(m);
    rep(i,1,m)read(q[i].t),read(q[i].k),q[i].id=i;
    sort(q+1,q+m+1);
    rep(i,1,m){
        if(q[i].k!=q[i-1].k&&q[i].k<=sz)cal(q[i].k);
        if(q[i].k<=sz)ans[q[i].id]=s[q[i].t];
        else{
            for(int j=q[i].t;j<=n;j+=q[i].k)ans[q[i].id]+=a[j];
        }
    }
    rep(i,1,m)printf("%lld\n",ans[i]);
    return 0;
}

You Are Given a Tree

先考虑如果k只有一个怎么做？

可以考虑一个类似于赛道修建的贪心，每个点维护从子树到这个点的最长路和次长路，如果加起来比k大，就合并然后将到父亲的最常路设为0。

所以对于小于等于B的k，我们可以直接预处理，O(nB)。

当k增大时，可以发现答案一定是不增的。我们可以二分答案的作用范围，每次二分复杂度O(n\log n)，每种答案都要二分一次，最多O(\frac n B)种答案，所以这部分复杂度为O(\frac {n^2\log n}{B})，在B=\sqrt{n\log n}时总复杂度较优。

这题卡常，可以把树重新建一遍，只保留父亲到儿子的边，快了10倍甚至9倍。

#include<bits/stdc++.h> 
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
const int MAXN=1e5+5;
int n,lim;
int ans[MAXN];
struct E{
    int v,nxt;
} e[2][MAXN<<1];
int cnt[2],h[2][MAXN];
void ade(int u,int v,int o){
    e[o][++cnt[o]].v=v;
    e[o][cnt[o]].nxt=h[o][u];
    h[o][u]=cnt[o];
}
void build(int u,int fa){
    for(int i=h[0][u];i;i=e[0][i].nxt){
        int v=e[0][i].v;
        if(v==fa)continue;
        ade(u,v,1);
        build(v,u);
    }
}
int res=0;
int dfs(int u,int k){
    int mx=0,sec=0,v;
    for(int i=h[1][u];i;i=e[1][i].nxt){
        v=e[1][i].v;
        int t=dfs(v,k);
        if(t>=k){res++;return 0;}
        if(t>mx)sec=mx,mx=t;
        else if(t>sec)sec=t;
    }
    if(mx+sec+1>=k){res++;return 0;}
    return mx+1;
}
int cal(int k){
    res=0;
    dfs(1,k);
    return res;
}
int main(){
    read(n);
    lim=sqrt(n*log2(n));
    int x,y;
    rep(i,1,n-1)read(x),read(y),ade(x,y,0),ade(y,x,0);
    build(1,0);
    rep(i,1,lim)ans[i]=cal(i);
    for(int i=1,pre=n+1;i<=n/lim+1;i++){
        int l=1,r=pre;
        while(l<r){
            int mid=((l+r)>>1)+1;
            if(cal(mid)>=i)l=mid;
            else r=mid-1;
        }
        rep(j,l+1,pre-1)ans[j]=i-1;
        pre=l+1;
    }
    rep(i,1,n)printf("%d\n",ans[i]);
    return 0;
}

DZY Loves Strings

考虑到询问串的长度很小，我们先预处理出所有可能的询问串的出现次数，一共有O(4n)种，然后对于出现次数>\frac {4n} B的，最多有\frac{4n}B种，做一个扫描线预处理答案。

对于两个出现次数都<B 的，把两个串的出现位置序列单独拿出来，枚举其中一个，再二分前后找最近的就行，O(Blogn)。

常数是别人的10倍甚至9倍。

#include<bits/stdc++.h> 
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
const int MAXN=5e4+5,MCNT=2e5+5,bs=27,MAXM=6e5,inf=1e9;
int n,q,lim;
string s;
int hs(int x,int y){
    int res=0;
    rep(i,x,y)res=res*bs+s[i]-'a'+1;
    return res;
}
int hs2(string x){
    int t=x.length();
    int res=0;
    rep(i,0,t-1)res=res*bs+x[i]-'a'+1;
    return res;
}
int cnt[MAXM],lst[MAXM],len[MAXM];
vector<int> pl[MAXM],nam;
unordered_map<int,int> mp[MAXM];
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    cin>>q;
    n=s.length();
    lim=sqrt(4.0*n);
    s=' '+s;
    int tt=0;
    rep(i,1,n){
        rep(k,1,4){
            if(i+k-1>n)continue;
            int t=hs(i,i+k-1);
            cnt[t]++;
            pl[t].push_back(i);
            tt=max(tt,t);
            len[t]=k;
        }
    }
    rep(i,1,tt)
        if(cnt[i]>lim)nam.push_back(i);

    rep(i,1,n){
        rep(k,1,4){
            if(i+k-1>n)continue;
            int hss=hs(i,i+k-1);
            for(int j:nam){
                if(!lst[j])continue;
                int ed=max(lst[j]+len[j]-1,i+k-1);
                int st=lst[j];
                int x=hss,y=j;
                if(x>y)swap(x,y);
                mp[x][y]=min((!mp[x][y])?inf:mp[x][y],ed-st+1);
            }
            lst[hss]=i;
        }
    }
    memset(lst,0,sizeof(lst));
    Rrep(i,n,1){
        rep(k,1,4){
            if(i+k-1>n)continue;
            int hss=hs(i,i+k-1);
            for(int j:nam){
                if(!lst[j])continue;
                int ed=max(lst[j]+len[j]-1,i+k-1);
                int st=i;
                int x=hss,y=j;
                if(x>y)swap(x,y);
                mp[x][y]=min((!mp[x][y])?inf:mp[x][y],ed-st+1);
            }
            lst[hss]=i;
        }
    }

    string a,b;
    while(q--){
        cin>>a>>b;
        int hsa=hs2(a),hsb=hs2(b);
        if(cnt[hsa]>cnt[hsb])swap(a,b),swap(hsa,hsb);

        if((!cnt[hsa])||(!cnt[hsb])){cout<<"-1"<<endl;continue;}
        if(a==b){cout<<len[hsa]<<endl;continue;}

        if(cnt[hsb]>lim){
            int x=hsa,y=hsb;
            if(x>y)swap(x,y);
            cout<<mp[x][y]<<endl;
            continue;
        }
        else{
            int res=inf;
            for(int i:pl[hsa]){
                int st,ed;
                auto t=upper_bound(pl[hsb].begin(),pl[hsb].end(),i);
                t--;

                while(t<pl[hsb].end()&&*t<=i)t++;
                if(t==pl[hsb].end()||*t>i)t--;
                if(*t<=i){
                    st=*t,ed=max(*t+len[hsb]-1,i+len[hsa]-1);
                    res=min(res,ed-st+1);
                }

                t=upper_bound(pl[hsb].begin(),pl[hsb].end(),i);
                while(t>=pl[hsb].begin()&&*t>=i)t--;
                if(t<pl[hsb].begin()||*t<i)t++;
                if(t==pl[hsb].end())t--;
                if(*t>=i){
                    st=i,ed=max(*t+len[hsb]-1,i+len[hsa]-1);
                    res=min(res,ed-st+1);
                }
            }
            cout<<res<<endl;
        }
    }
    return 0;
}

破案了，原来第二种不用二分，也做一个扫描线就行了，我真傻，真的。

String Set Queries

考虑枚举已出现过的串的长度，在模板串中枚举每个长度的子串，用哈希判定。

复杂度为什么是对的呢？

考虑最坏情况，也就是已出现串的种类尽量多，那么每个串只有一个，从1开始单调递增，1+2+3+...+x=3\times 10^5，那么x=\sqrt{6\times 10^5}，也就是说复杂度最坏是O(6\times 10^5\sqrt{6\times 10^5})。

这题卡哈希，用拉链法。

#include<bits/stdc++.h> 
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
typedef long long ll;
const int MAXN=3e5+5,mod=1e9+7,bs=29,MSZ=800,MOD=5003;
int m;
int pw[MAXN],id[MAXN],rev[MAXN],tot,has[MAXN];
struct HASH{
    struct nd{
        int ky,cnt;
    };
    vector<nd> a[MOD];
    void ins(int x){
        int t=x%MOD;
        int sz=a[t].size();sz--;
        rep(i,0,sz)
            if(a[t][i].ky==x){a[t][i].cnt++;return;}
        a[t].push_back((nd){x,1});
    }
    void del(int x){
        int t=x%MOD;
        int sz=a[t].size();sz--;
        rep(i,0,sz)
            if(a[t][i].ky==x){
                a[t][i].cnt--;
                if(!a[t][i].cnt)swap(a[t][i],a[t].back());
                a[t].pop_back();
                return;
            }
        a[t].push_back((nd){x,1});
    }
    int quy(int x){
        int t=x%MOD;
        int sz=a[t].size();sz--;
        rep(i,0,sz)
            if(a[t][i].ky==x)return a[t][i].cnt;
        return 0;
    }
} mp[MSZ];
int main(){
    ios::sync_with_stdio(false);
    cin>>m;
    pw[0]=1;
    rep(i,1,3e5)pw[i]=1ll*pw[i-1]*bs%mod;
    int o,ls;
    string s;
    while(m--){
        cin>>o>>s;
        ls=s.length();
        s=' '+s;
        if(o==1){
            int hs=0;
            rep(i,1,ls)hs=(1ll*hs*bs+s[i]-'a'+1)%mod;
            if(!id[ls])rev[id[ls]=++tot]=ls;
            mp[id[ls]].ins(hs);
        }
        else if(o==2){
            int hs=0;
            rep(i,1,ls)hs=(1ll*hs*bs+s[i]-'a'+1)%mod;
            mp[id[ls]].del(hs);
        }
        else{
            rep(i,1,ls)has[i]=(1ll*has[i-1]*bs+s[i]-'a'+1)%mod;
            int ans=0;
            rep(i,1,tot){
                int L=rev[i];
                rep(j,rev[i],ls){
                    ans+=mp[i].quy(((ll)has[j]+mod-1ll*has[j-L]*pw[L]%mod)%mod);
                }
            }
            cout<<ans<<endl;
            fflush(stdout);
        }
    }
    return 0;
}

P3645 [APIO2015] 雅加达的摩天楼

暴力建图，行不通。

我们考虑直接bfs，隐式建图。

复杂度为什么是对的呢？

对于p>\sqrt n，可到达的点不超过\sqrt n个。

对于p\leq \sqrt n，每次拓展不超过\sqrt n次。

我们可以用bitset判断每个点的每种距离是否拓展过。

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
const int MAXN=3e4+5;
int n,m,b[MAXN],p[MAXN];
struct nd{
    int x,stp,res;
};
vector<int> v[MAXN];
list<nd> q;
bitset<MAXN> vis[MAXN];
int main(){
    read(n),read(m);
    rep(i,0,m-1){
        read(b[i]),read(p[i]);
        v[b[i]].push_back(p[i]);
    }
    q.push_back((nd){b[0],p[0],0});
    nd u;
    while(!q.empty()){
        u=q.front();
        q.pop_front();
        if(u.x==b[1]){printf("%d\n",u.res);return 0;}
        if(vis[u.x][u.stp])continue;
        vis[u.x][u.stp]=1;
        if(u.x-u.stp>=0)q.push_back((nd){u.x-u.stp,u.stp,u.res+1});
        if(u.x+u.stp<=n-1)q.push_back((nd){u.x+u.stp,u.stp,u.res+1});
        for(int i:v[u.x])q.push_front((nd){u.x,i,u.res});
    }
    puts("-1");
    return 0;
}

P5309 [Ynoi2011] 初始化

先考虑修改操作。

对于每个x>B，暴力更新。

对于每个x<B，建一个\sqrt n\times \sqrt n的表，表示每个模数的每个余数位置加了什么。

然后把序列分块维护，答案就是原序列的和加上每种模数的懒标记的和。

第二种对于每个模数在序列中会呈现一个周期，然后维护表中每个每一行的前缀、后缀和就行了，修改的时候暴力更新前缀后缀和。

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
#define admd(a,b) a=(a+b>mod)?(a+b-mod):(a+b)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
const int MAXN=2e5+5,mod=1e9+7,MSZ=500;
const int lim=150;
int n,m,sz,num,a[MAXN];
int l[MSZ],r[MSZ],pos[MAXN],s[MSZ],pre[MSZ][MSZ],suf[MSZ][MSZ];
void build(){
    sz=sqrt(n);
    num=ceil(n*1.0/sz);
    rep(i,1,num)l[i]=(i-1)*sz+1,r[i]=i*sz;
    r[num]=n;
    rep(i,1,n)read(a[i]),pos[i]=(i-1)/sz+1,admd(s[pos[i]],a[i]);
}
int quy(int nl,int nr){
    int res=0;
    if(pos[nl]==pos[nr])
        rep(i,nl,nr)admd(res,a[i]);
    else{
        rep(i,nl,r[pos[nl]])admd(res,a[i]);
        rep(i,l[pos[nr]],nr)admd(res,a[i]);
        rep(i,pos[nl]+1,pos[nr]-1)admd(res,s[i]);
    }
    int ed=min(lim,n);
    rep(i,1,ed){
        int t1=(nl-1)/i+1,t2=(nr-1)/i+1;
        if(t1==t2){
            admd(res,pre[i][nr-i*(t2-1)]);
            admd(res,mod-pre[i][nl-1-i*(t1-1)]);
        }
        else{
            admd(res,1ll*pre[i][i]*(t2-t1-1)%mod);
            admd(res,pre[i][nr-i*(t2-1)]);
            admd(res,suf[i][nl-i*(t1-1)]);
        }
    }
    return res;
}
int main(){
    read(n),read(m);
    build();
    int o,x,y,z;
    while(m--){
        read(o),read(x),read(y);
        if(o==1){
            read(z);
            if(x<=lim){
                rep(i,y,x)admd(pre[x][i],z);
                Rrep(i,y,1)admd(suf[x][i],z);
            }
            else
                for(int i=y;i<=n;i+=x)admd(a[i],z),admd(s[pos[i]],z);
        }
        else printf("%d\n",quy(x,y));
    }
    return 0;
}

P5901 [IOI2009] regions

先考虑两种暴力，第一种是从根开始dfs，求得u子树内每种颜色的点有多少个。

第二种是倒着dfs。

如果r_2的点数>B，用第一种方式，在r_1里挂一个询问(i,r_2)，一遍dfs解决。

如果r_2的点数\leq B，用第二种方式，在r_2里挂一个询问(i,r_1)，一遍dfs解决。

在dfs的时候我们维护一个桶，利用更新前后的差值计算答案。

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
const int MAXN=2e5+5,MAXR=2.5e4+5;
int n,r,Q,lim;
int h[MAXN],s[MAXR],ans[MAXN],bkt[MAXN];
struct E{
    int v,nxt;
} e[MAXN];
int ecnt,hd[MAXN];
void ade(int u,int v){
    e[++ecnt].v=v;
    e[ecnt].nxt=hd[u];
    hd[u]=ecnt;
}
vector<pair<int,int> > q1[MAXN],q2[MAXN];
void dfs1(int u){
    for(auto i:q1[h[u]])ans[i.first]-=bkt[i.second];
    bkt[h[u]]++;
    for(int i=hd[u];i;i=e[i].nxt)dfs1(e[i].v);
    for(auto i:q1[h[u]])ans[i.first]+=bkt[i.second];
}
void dfs2(int u){
    bkt[h[u]]++;
    for(auto i:q2[h[u]])ans[i.first]+=bkt[i.second];
    for(int i=hd[u];i;i=e[i].nxt)dfs2(e[i].v);
    bkt[h[u]]--;
}
int main(){
    read(n),read(r),read(Q);
    lim=sqrt(n);
    read(h[1]);
    s[h[1]]++;
    int x;
    rep(i,2,n){
        read(x);
        ade(x,i);
        read(h[i]);
        s[h[i]]++;
    }
    int r1,r2;
    rep(i,1,Q){
        read(r1),read(r2);
        if(s[r2]>=lim)q1[r1].push_back(make_pair(i,r2));
        else q2[r2].push_back(make_pair(i,r1));
    }
    dfs1(1);
    memset(bkt,0,sizeof(bkt));
    dfs2(1);
    rep(i,1,Q)printf("%d\n",ans[i]);
    return 0;
}