根号分治

用户头像 发布于 7 小时前 4 次阅读 OI

根号分治

P3396 哈希冲突

一眼根号分治，小就暴力，大就预处理，没啥好说的。

代码：

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

#define int long long
const int N=1.5e5+5;
int a[N],dp[1000][1000];
int n,m,x,y;
char c;

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) for(int j=1;j<=sqrt(n);j++) dp[j][i%j]+=a[i]; 
	while(m--){
		cin>>c>>x>>y;
		if(c=='A'){
			if(x<=sqrt(n)) cout<<dp[x][y]<<"\n";
			else{
				int ans=0;
				for(int i=y;i<=n;i+=x) ans+=a[i];
				cout<<ans<<"\n";
			}
		} 
		else{
			for(int i=1;i<=sqrt(n);i++) dp[i][x%i]+=y-a[x]; 
			a[x]=y;
		}
	} 
	return 0;
}

P5309 [Ynoi2011] 初始化

分块+根号分治。

大于根号时直接暴力加，小于根号时，计算前后缀同一周期同一位置的加减情况。

查询分两个部分，一个是暴力加的，一个可以用前后缀的信息计算，代码：

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

#define int long long
const int sz=128,N=2e5+5,md=1e9+7;
const int Z=N/sz+2;
int n,m,bl,a[N],s[Z],L[Z],R[Z],pr[sz][sz],sf[sz][sz];
#define bel(x)((x-1)/sz+1)

inline void upd(int &x){x+=x>>31&md;}

int qry(int l,int r){
    int bl=bel(l),br=bel(r),res=0;
    if(bl==br) for(int i=l;i<=r;i++) upd(res+=a[i]-md);
    else{
        for(int i=R[bl];i>=l;i--) upd(res+=a[i]-md);
        for(int i=L[br];i<=r;i++) upd(res+=a[i]-md);
        for(int i=bl+1;i<br;i++) upd(res+=s[i]-md);
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n>>m;
    bl=bel(n);
    for(int i=1;i<=bl;i++) L[i]=R[i-1]+1,R[i]=i*sz;
    R[bl]=n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=bl;i++) for(int j=L[i];j<=R[i];j++) upd(s[i]+=a[j]-md);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,y,z;
			cin>>x>>y>>z;
			z-=md;
            if(x>=sz) for(int i=y;i<=n;i+=x) upd(a[i]+=z),upd(s[bel(i)]+=z);
            else{
                for(int i=x;i>=y;i--) upd(pr[x][i]+=z);
                for(int i=1;i<=y;i++) upd(sf[x][i]+=z);
            }
        }
		else{
            int l,r;
			cin>>l>>r;
            int ans=qry(l,r);
            for(int i=1;i<sz;i++){
                int bl=(l-1)/i+1,br=(r-1)/i+1;
                if(bl==br) upd(ans+=pr[i][(r-1)%i+1]-md),upd(ans-=pr[i][(l-1)%i]);
                else ans=(ans+(br-bl-1)*pr[i][i])%md,upd(ans+=pr[i][(r-1)%i+1]-md),upd(ans+=sf[i][(l-1)%i+1]-md);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

P8250 交友问题

用 bitset 维护每个点的邻居，bitset 的计算根号分治一下即可，

代码：

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

const int N=2e5+5;
int n,m,q;
int dig[N];
map<int,bitset<N>> mp;
vector<int> g[N];

bitset<N> get(int u){
    bitset<N> res;
    for(int v:g[u]) res[v]=1;
    return res;
}

signed main(){
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        dig[u]++,dig[v]++;
    }
    for(int i=1;i<=n;i++) if(dig[i]>1000) mp[i]=get(i);
    for(int i=1;i<=q;i++){
        int u,v;
        cin>>u>>v;
        bitset<N> x=(dig[u]>1000?mp[u]:get(u));
        bitset<N> y=(dig[v]>1000?mp[v]:get(v));
        y[v]=1;
        cout<<(x&(~y)).count()<<"\n";
    }
    return 0;
}

P5901 [IOI 2009] Regions

对于其中一个是点数大于根号的颜色，预处理一下，一个是差分子树加，一个是前缀和单点加。

同样的思路运用到小于根号的在线，用树状数组维护即可。

注意卡常，代码：

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

const int N=2e5+5;
const int M=425;
int n,r,q,idx,sum;
int fa[N],h[N],dfn[N],siz[N],big[N],tag[N],a[N],ans1[25005][M+5],ans2[M+5][25005];
vector<int> t[N],c[N];

inline int read(){
    int x=0; 
    char ch=getchar_unlocked();
    while(ch<'0'||ch>'9') ch=getchar_unlocked();
    while(ch>='0'&&ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar_unlocked();
    }
    return x;
}

inline void put(int x){
    if(x<0){
        putchar_unlocked('-');
        x=-x;
    }
    if(x==0){
        putchar_unlocked('0');
        return;
    }
    static int st[20];
    int top=0;
    while(x) st[++top]=x%10,x/=10;
    while(top) putchar_unlocked(st[top--]+'0');
}

inline void add(int x){
    for(int i=x;i<=n;i+=i&-i) a[i]++;
}

inline int query(int x){
    int res=0;
    for(int i=x;i>0;i-=i&-i) res+=a[i];
    return res;
}

void dfs(int u){
    dfn[u]=++idx,siz[u]=1;
    for(int v:t[u]) dfs(v),siz[u]+=siz[v];
}

inline int get(int u,int v){
    int res=0,ans=0;
    for(int x:c[u]) res+=query(dfn[x]+siz[x]-1)-query(dfn[x]-1);
    for(int x:c[v]) add(dfn[x]);
    for(int x:c[u]) ans+=query(dfn[x]+siz[x]-1)-query(dfn[x]-1);
    return ans-res;
}

signed main(){
    n=read(),r=read(),q=read();
    h[1]=read(),c[h[1]].push_back(1);
    for(int i=2;i<=n;i++){
        fa[i]=read(),h[i]=read();
        t[fa[i]].push_back(i);
        c[h[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=r;i++){
        if(c[i].size()<=M) continue;
        big[i]=++sum;
        for(int j=1;j<=n;j++) tag[j]=0;
        for(int u:c[i]) tag[dfn[u]]++;
        for(int j=1;j<=n;j++) tag[j]+=tag[j-1];
        for(int j=1;j<=n;j++) if(h[j]!=i) ans1[h[j]][big[i]]+=tag[dfn[j]+siz[j]-1]-tag[dfn[j]-1];
        for(int j=1;j<=n;j++) tag[j]=0;
        for(int u:c[i]) tag[dfn[u]]++,tag[dfn[u]+siz[u]]--;
        for(int j=1;j<=n;j++) tag[j]+=tag[j-1];
        for(int j=1;j<=n;j++) if(h[j]!=i) ans2[big[i]][h[j]]+=tag[dfn[j]];
    }
    while(q--){
        int u,v;
        u=read(),v=read();
        if(big[u]) put(ans2[big[u]][v]);
        else if(big[v]) put(ans1[u][big[v]]);
        else put(get(u,v));
        putchar_unlocked('\n');
        fflush(stdout);
    }
    return 0;
}