@Scarlet 2017-03-27T11:21:31.000000Z 字数 26301 阅读 2043

# 根号算法

——如何让复杂度去掉$\frac{1}{2},\frac{1}{3}$

数据结构 算法

By $\color{red}{Scarlet}$

## 分块

### 一般分块

SIZ=(int)sqrt(n);                       //块大小for(int i=(x-1)*SIZ+1;i<=x*SIZ;i++);    //遍历块x（当然）bl[i]=(i-1)/SIZ+1                       //i\$所在块编号f[bl[a]+1][bl[b]-1]                     //a、b之间块内答案

（在线）维护XJB玩意儿。

#### BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊

/*    Author:Scarlet*/#include<iostream>#include<cstdio>#include<cmath>#define maxn 200011using namespace std;int n,m,bl[maxn],f[maxn],to[maxn],k[maxn];inline int ask(int x){int he=0;while (x<n)he+=k[x],x=to[x];return he;}inline void change(int x,int y){    int i,j=bl[x],r;    f[x]=y;r=y;    if (bl[r]==bl[x]) to[x]=to[r],k[x]=k[r]+1;    else to[x]=y,k[x]=1;    for (i=x-1;i>=0;i--)    {        if (bl[i]!=j) break;r=f[i];        if (bl[r]==bl[i]&&r<n) to[i]=to[r],k[i]=k[r]+1;        else to[i]=r,k[i]=1;    }}  int main(){    scanf("%d",&n);    int i,j,aa,bb,cc,r,sq=int(sqrt(n)),o=sq,t=0;    for (i=0;i<n;i++)    {        if (o==sq)bl[i]=++t,o=1;else bl[i]=t,o++;        scanf("%d",&f[i]);f[i]+=i;    }       for (i=n-1;i>=0;i--)    {        r=f[i];        if (bl[r]!=bl[i]||r>=n) to[i]=r,k[i]=1;        else to[i]=to[r],k[i]=k[r]+1;    }    scanf("%d",&m);    while (m--)    {        scanf("%d",&aa);        if (aa==1)scanf("%d",&bb),printf("%d\n",ask(bb));        else scanf("%d%d",&bb,&cc),cc+=bb,change(bb,cc);    }    return 0;}

#### BZOJ 2724: [Violet 6]蒲公英

cls有$(n+q)\sqrt n$技巧，但是代码复杂度太大只敢写带$\log$的.

$\sqrt n$枚举一下是哪个，$\log$时间计算一下出现了几次，就$(n+q)\sqrt n\log n$了.

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100005#define maxm 350using namespace std;typedef long long LL;#define G c=getchar()inline LL read(){    LL x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int n,m,SIZ,id,v[maxn],bl[maxn];int f[maxm][maxm];map<int,int>mp;int val[maxn],cnt[maxn];vector<int>ve[maxn];void pre(int x){    memset(cnt,0,sizeof(cnt));    int mx=0,ans=0,t;    for(int i=(x-1)*SIZ+1;i<=n;i++)    {        cnt[v[i]]++;        t=bl[i];        if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))        ans=v[i],mx=cnt[v[i]];        f[x][t]=ans;    }}int Q(int l,int r,int x){    return upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l);}int query(int a,int b){    int ans,mx,t;    ans=f[bl[a]+1][bl[b]-1];    mx=Q(a,b,ans);    for(int i=a;i<=min(bl[a]*SIZ,b);i++)    {        t=Q(a,b,v[i]);        if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;    }    if(bl[a]!=bl[b])        for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)        {            t=Q(a,b,v[i]);            if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;        }    return ans;}int main(){    n=read(),m=read();    SIZ=(int)sqrt(n);    int ans=0;    for(int i=1;i<=n;i++)    {        v[i]=read();        if(!mp[v[i]])mp[v[i]]=++id,val[id]=v[i];        v[i]=mp[v[i]];        ve[v[i]].push_back(i);    }    for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;    for(int i=1;i<=bl[n];i++)pre(i);    for(int i=1;i<=m;i++)    {        int a=read(),b=read();        a=(a+ans-1)%n+1;b=(b+ans-1)%n+1;        if(a>b)swap(a,b);        ans=val[query(a,b)];        printf("%d\n",ans);    }    return 0;}

RunID User Problem Result Memory Time Language Code_Length Submit_Time
1777662 xmc54300 2724 Accepted 35516 kb 3832 ms C++/Edit 1980 B 2017-01-06
1777222 xmc54300 2724 Accepted 3676 kb 18892 ms C++/Edit 1723 B 2017-01-06

Interesting..

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 40010#define maxm 210using namespace std;typedef long long LL;#define G c=getchar()#define ZZ t=++cnt[v[i]];if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;inline LL read(){    LL x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int n,m,SIZ,id,v[maxn],bl[maxn];int f[maxm][maxm],ff[maxm][maxm],g[maxm][maxn];map<int,int>mp;int val[maxn],cnt[maxn],tim[maxn],T;void pre(int x){    memset(cnt,0,sizeof(cnt));    int mx=0,ans=0,t;    for(int i=(x-1)*SIZ+1;i<=n;i++)    {        cnt[v[i]]++;t=bl[i];        if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))ans=v[i],mx=cnt[v[i]];        f[x][t]=ans;ff[x][t]=mx;    }}int query(int a,int b){    int ans,mx,t;++T;    ans=f[bl[a]+1][bl[b]-1];    mx=ff[bl[a]+1][bl[b]-1];    if(bl[a]==bl[b])        for(int i=a;i<=b;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=0;            ZZ        }    else    {        for(int i=a;i<=bl[a]*SIZ;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];            ZZ        }        for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];            ZZ        }    }    return ans;}int main(){    n=read(),m=read();    SIZ=(int)sqrt(n);    int ans=0;    for(int i=1;i<=n;i++)    {        v[i]=read();        if(!mp[v[i]])mp[v[i]]=++id,val[id]=v[i];        v[i]=mp[v[i]];    }    for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;    for(int i=1;i<=n;i++)        g[bl[i]][v[i]]++;    for(int i=1;i<=bl[n];i++)        for(int j=1;j<=n;j++)            g[i][j]+=g[i-1][j];    for(int i=1;i<=bl[n];i++)pre(i);    for(int i=1;i<=m;i++)    {        int a=read(),b=read();        a=(a+ans-1)%n+1;b=(b+ans-1)%n+1;        if(a>b)swap(a,b);        ans=val[query(a,b)];        printf("%d\n",ans);    }    return 0;}

#### BZOJ 4241: 历史研究

$\log$过不去

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100010#define maxm 350#define INF 200000000000000llusing namespace std;typedef long long LL;#define G c=getchar()#define ZZ t=val[v[i]]*++cnt[v[i]];t>mx?mx=t:0;inline LL read(){    LL x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int n,m,SIZ,id,v[maxn],bl[maxn];LL f[maxm][maxm];int g[maxm][maxn];map<int,int>mp;LL val[maxn],cnt[maxn];int tim[maxn],T;void pre(int x){    memset(cnt,0,sizeof(cnt));    LL mx=-INF;    for(int i=(x-1)*SIZ+1;i<=n;i++)    {        cnt[v[i]]++;        if(cnt[v[i]]*val[v[i]]>mx)mx=cnt[v[i]]*val[v[i]];        f[x][bl[i]]=mx;    }}LL query(int a,int b){    ++T;LL t,mx=f[bl[a]+1][bl[b]-1];    if(bl[a]==bl[b])        for(int i=a;i<=b;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=0;            ZZ        }    else    {        for(int i=a;i<=bl[a]*SIZ;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];            ZZ        }        for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];            ZZ        }    }    return mx;}int main(){    n=read(),m=read();    SIZ=(int)sqrt(n);    for(int i=1;i<=n;i++)    {        v[i]=read();        if(!mp[v[i]])mp[v[i]]=++id,val[id]=v[i];        v[i]=mp[v[i]];    }    for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;    for(int i=1;i<=n;i++)        g[bl[i]][v[i]]++;    for(int i=1;i<=bl[n];i++)        for(int j=1;j<=n;j++)            g[i][j]+=g[i-1][j];    for(int i=1;i<=bl[n];i++)pre(i);    for(int i=1;i<=m;i++)    {        int a=read(),b=read();        printf("%lld\n",query(a,b));    }    return 0;}

#### BZOJ 2821: 作诗(Poetize)

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100005#define maxm 305#define INF 200000000000000llusing namespace std;typedef long long LL;#define G c=getchar()inline LL read(){    LL x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int n,m,SIZ,id,v[maxn],bl[maxn];int f[maxm][maxm],g[maxm][maxn],cnt[maxn];int tim[maxn],T,c;void pre(int x){    memset(cnt,0,sizeof(cnt));    int ans=0;    for(int i=(x-1)*SIZ+1;i<=n;i++)    {        cnt[v[i]]++;        if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;        else ans++;        f[x][bl[i]]=ans;    }}int query(int a,int b){    ++T;    int ans=f[bl[a]+1][bl[b]-1],t;    if(bl[a]==bl[b])        for(int i=a;i<=b;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=0;            t=++cnt[v[i]];            if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;            else ans++;        }    else    {        for(int i=a;i<=bl[a]*SIZ;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];            t=++cnt[v[i]];            if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;            else ans++;        }        for(int i=(bl[b]-1)*SIZ+1;i<=b;i++)        {            if(tim[v[i]]!=T)tim[v[i]]=T,cnt[v[i]]=g[bl[b]-1][v[i]]-g[bl[a]][v[i]];            t=++cnt[v[i]];            if(cnt[v[i]]&1)cnt[v[i]]-1?ans--:0;            else ans++;        }    }    return ans;}int main(){    n=read(),c=read(),m=read();    int ans=0;    SIZ=(int)sqrt(n);    if((n-1)/SIZ+1>300)SIZ=350;    for(int i=1;i<=n;i++)        v[i]=read();    for(int i=1;i<=n;i++)bl[i]=(i-1)/SIZ+1;    for(int i=1;i<=n;i++)        g[bl[i]][v[i]]++;    for(int i=1;i<=bl[n];i++)        for(int j=1;j<=n;j++)            g[i][j]+=g[i-1][j];    for(int i=1;i<=bl[n];i++)pre(i);    for(int i=1;i<=m;i++)    {        int a=read(),b=read();        a=(a+ans)%n+1;b=(b+ans)%n+1;        if(a>b)swap(a,b);        printf("%d\n",ans=query(a,b));    }    return 0;}

### 树分块

/*    Author:Scarlet*/void dfs(int x)//“分块”处理，可能不是最快的姿势，另一种可以看树上莫队第一题{    if(blo[bel[fa[x]]].size==block)//块满        blo[bel[x]=++cnt].ist(a[x]),AE(bidx,bel[fa[x]],cnt);//新开一块并和父亲块连（单向）边    else        blo[bel[x]=bel[fa[x]]].ist(a[x]);//在原块内加入    for(int i=idx[x];i;i=nxt[i])//遍历原树        if(to[i]!=fa[x])            fa[to[i]]=x,dfs(to[i]);}void BDFS(int x,int y){    //块内点统计    for(int i=bidx[x];i;i=nxt[i])        BDFS(to[i],y);//遍历相邻的块，因为是单向的而且处理的是子树问题所以只要无脑遍历就行了。}void DFS(int x,int y)//求解{    //块外点统计    for(int i=idx[x];i;i=nxt[i])//遍历原树        if(to[i]!=fa[x])            if(bel[to[i]]==bel[x])//在根所在的块内要单独统计                DFS(to[i],y);            else                BDFS(bel[to[i]],y);//不在块内的就可以成块统计了}//调用：dfs(1);//构树blo[bel[x]].mdf(...);//对点x修改AE(idx,x,n);fa[n]=x;//新建点的实力伪代码if(x块满)新块加入n,x块->n块;else x块加入n;DFS(x,...);//对x的子树查询

（在线）在树上维护XJB玩意儿。

#### BZOJ 3720: Gty的妹子树

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 30300using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}struct poi{    int a[210],size;    void ist(int x)//    {        ++size;        int i=size;        for(;i>1&&a[i-1]>x;i--)a[i]=a[i-1];        a[i]=x;    }    void mdf(int x,int y)//    {        int t=lower_bound(a+1,a+size+1,x)-a;        for(;t<size&&a[t+1]<y;t++)a[t]=a[t+1];        for(;t>1&&a[t-1]>y;t--)a[t]=a[t-1];        a[t]=y;    }    int qry(int x)//    {        int t=upper_bound(a+1,a+size+1,x)-a;        return size-t+1;    }}blo[10100];#define AE(idx,u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn*2],bidx[maxn],nxt[maxn*4],to[maxn*4],Si=1;int a[maxn*2],fa[maxn*2],bel[maxn*2];int n,m,block,ans,cnt;void dfs(int x){    if(blo[bel[fa[x]]].size==block)        blo[bel[x]=++cnt].ist(a[x]),AE(bidx,bel[fa[x]],cnt);    else        blo[bel[x]=bel[fa[x]]].ist(a[x]);    for(int i=idx[x];i;i=nxt[i])        if(to[i]!=fa[x])fa[to[i]]=x,dfs(to[i]);}void BDFS(int x,int y){    ans+=blo[x].qry(y);    for(int i=bidx[x];i;i=nxt[i])BDFS(to[i],y);}void DFS(int x,int y){    if(a[x]>y)++ans;    for(int i=idx[x];i;i=nxt[i])        if(to[i]!=fa[x])            if(bel[to[i]]==bel[x])DFS(to[i],y);            else BDFS(bel[to[i]],y);}int main(){    n=read();    for(int i=1,x,y;i<n;i++)        x=read(),y=read(),AE(idx,x,y),AE(idx,y,x);    for(int i=1;i<=n;i++)        a[i]=read();    block=(int)(sqrt(n)+1e-7);    dfs(1);    m=read();    for(;m--;)    {        int p=read(),x=read(),y=read();        x^=ans,y^=ans;        if(p==0)ans=0,DFS(x,y),printf("%d\n",ans);        else if(p==1)blo[bel[x]].mdf(a[x],y),a[x]=y;        else        {            a[++n]=y;AE(idx,x,n);fa[n]=x;            if(blo[bel[x]].size==block)                blo[bel[n]=++cnt].ist(y),AE(bidx,bel[x],cnt);            else                blo[bel[n]=bel[x]].ist(y);        }    }    return 0;}

#### BZOJ 1086: [SCOI2005]王室联邦

PoPoQQQ：《手把手教你树分块系列》

(以下来自hzwer)

。。。

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 1005#define maxm 2010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int n,B,top,pro;#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn],nxt[maxm],to[maxm],Si=1;int q[maxn],size[maxn],belong[maxn],cap[maxn];void dfs(int x,int fa){    q[++top]=x;    for(int i=idx[x];i;i=nxt[i])        if(to[i]!=fa)        {            dfs(to[i],x);            if(size[x]+size[to[i]]>=B)            {                size[x]=0;cap[++pro]=x;                while(q[top]!=x)                    belong[q[top--]]=pro;            }            else size[x]+=size[to[i]];        }    size[x]++;}void paint(int x,int fa,int c){    if(belong[x])c=belong[x];else belong[x]=c;    for(int i=idx[x];i;i=nxt[i])        if(to[i]!=fa)            paint(to[i],x,c);}int main(){    n=read();B=read();    if(n<B)return puts(""),0;    for(int i=1,u,v;i<n;i++)        u=read(),v=read(),AE(u,v),AE(v,u);    dfs(1,0);    if(!pro)cap[++pro]=1;    paint(1,0,pro);    printf("%d\n",pro);    for(int i=1;i<=n;i++)printf("%d ",belong[i]);puts("");    for(int i=1;i<=pro;i++)printf("%d ",cap[i]);    return 0;}

## 膜队

### 一般莫队

inline bool cmp(const poi &a,const poi &b){return bel[a.l]==bel[b.l]?a.r<b.r:a.l<b.l;}//对询问排序for(int i=1,L=1,R=0;i<=m;i++){    for(;R<Q[i].r;)ins(a[++R]);    for(;L>Q[i].l;)ins(a[--L]);    for(;R>Q[i].r;)del(a[R--]);    for(;L<Q[i].l;)del(a[L++]);    ans[Q[i].i]=//计算答案}

#### BZOJ 3585: mex

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 200100#define maxm 450using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}struct poi{int l,r,i;}Q[maxn];int a[maxn],bel[maxn],f[maxn],ba[maxm],ans[maxn];int l[maxm],r[maxm];int n,m,SIZ;inline bool cmp(const poi &a,const poi &b){return bel[a.l]==bel[b.l]?a.r<b.r:a.l<b.l;}void ins(int x){    if(x>n)return;    if(!f[x]++)ba[bel[x]]++;}void del(int x){    if(x>n)return;    if(!--f[x])ba[bel[x]]--;}int qry(){    if(!f[0])return 0;    int i;    for(i=1;l[i];i++)if(ba[i]!=r[i]-l[i]+1)break;    for(int j=l[i];j<=r[i];j++)if(!f[j])return j;    return n;}int main(){    n=read(),m=read();    SIZ=(int)(sqrt(n)+1e-7);    for(int i=1;i<=n;i++)bel[i]=(i-1)/SIZ+1,a[i]=read();    for(int i=1;(i-1)*SIZ+1<=n;i++)        l[i]=(i-1)*SIZ+1,r[i]=min(i*SIZ,n);    for(int i=1,x,y;i<=m;i++)x=read(),y=read(),Q[i]=(poi){x,y,i};    sort(Q+1,Q+1+m,cmp);    for(int i=1,L=1,R=0;i<=m;i++)    {        for(;R<Q[i].r;)ins(a[++R]);        for(;L>Q[i].l;)ins(a[--L]);        for(;R>Q[i].r;)del(a[R--]);        for(;L<Q[i].l;)del(a[L++]);        ans[Q[i].i]=qry();    }    for(int i=1;i<=m;i++)//我m打成n也A了= =        printf("%d\n",ans[i]);    return 0;}

#### BZOJ 3809: Gty的二逼妹子序列

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100100#define maxm 350using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}struct poi{int l,r,a,b,i;}Q[1000100];int a[maxn],bel[maxn],f[maxn],ba[maxm],ans[1000100];int l[maxm],r[maxm];int n,m,SIZ;inline bool cmp(const poi &a,const poi &b){return bel[a.l]==bel[b.l]?a.r<b.r:a.l<b.l;}void ins(int x){if(!f[x]++)ba[bel[x]]++;}void del(int x){if(!--f[x])ba[bel[x]]--;}int qry(int a,int b){    int ans=0;    if(bel[a]==bel[b]){for(int i=a;i<=b;i++)if(f[i])ans++;}    else    {        for(int i=a;i<=r[bel[a]];i++)if(f[i])ans++;        for(int i=l[bel[b]];i<=b;i++)if(f[i])ans++;        for(int i=bel[a]+1;i<bel[b];i++)ans+=ba[i];    }    return ans;}int main(){    n=read(),m=read();    SIZ=(int)(sqrt(n)+1e-7);    for(int i=1;i<=n;i++)bel[i]=(i-1)/SIZ+1,a[i]=read();    for(int i=1;(i-1)*SIZ+1<=n;i++)        l[i]=(i-1)*SIZ+1,r[i]=min(i*SIZ,n);    for(int i=1,x,y,a,b;i<=m;i++)        x=read(),y=read(),a=read(),b=read(),Q[i]=(poi){x,y,a,b,i};    sort(Q+1,Q+1+m,cmp);    for(int i=1,L=1,R=0;i<=m;i++)    {        for(;R<Q[i].r;)ins(a[++R]);        for(;L>Q[i].l;)ins(a[--L]);        for(;R>Q[i].r;)del(a[R--]);        for(;L<Q[i].l;)del(a[L++]);        ans[Q[i].i]=qry(Q[i].a,Q[i].b);    }    for(int i=1;i<=m;i++)        printf("%d\n",ans[i]);    return 0;}

### 树上莫队

inline bool cmp(const poi &a,const poi &b){return bel[a.u]==bel[b.u]?dfn[a.v]<dfn[b.v]:bel[a.u]<bel[b.u];}//对询问排序void rev(int x){    vis[x]^=1;    if(vis[x]){p[c[x]]++;if(p[c[x]]==1)upd();}    else{p[c[x]]--;if(p[c[x]]==0)upd();}}void move(int u,int v){    for(;u^v;)        if(dep[u]>dep[v])rev(u),u=fa[u][0];        else rev(v),v=fa[v][0];}//爬for(int i=1;i<=m;i++)//main{    move(q[i-1].u,q[i].u);    move(q[i-1].v,q[i].v);    //搞事情}

UPD：貌似通过拆点变成贡献+1-1的dfs序就可以直接上莫队了啊QAQ

#### BZOJ 3757: 苹果树

BZOJ不能交了。

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 50010#define maxm 100010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn],nxt[maxm],to[maxm],Si=1;int bin[20],n,m,ans,top,ind,blo,blonum,root;int res[maxm],p[maxn],fa[maxn][17],dep[maxn];int c[maxn],st[maxn],dfn[maxn],bel[maxn];bool vis[maxn];struct poi{int u,v,a,b,i;}q[maxm];inline bool cmp(const poi &a,const poi &b){return bel[a.u]==bel[b.u]?dfn[a.v]<dfn[b.v]:bel[a.u]<bel[b.u];}int dfs(int x){    int size=0;    dfn[x]=++ind;    for(int i=1;i<=16;i++)        fa[x][i]=fa[fa[x][i-1]][i-1];    for(int i=idx[x];i;i=nxt[i])        if(to[i]!=fa[x][0])        {            dep[to[i]]=dep[x]+1;            fa[to[i]][0]=x;            size+=dfs(to[i]);            if(size>=blo)//这里用的是hzwer的【1086】分块技巧，听说比PoPoQQQ写的那种（即树分块模板里的）要快            {                blonum++;                for(int k=1;k<=size;k++)                    bel[st[top--]]=blonum;                size=0;            }        }    st[++top]=x;    return size+1;}int lca(int x,int y){    if(dep[x]<dep[y])swap(x,y);    for(int i=0,t=dep[x]-dep[y];bin[i]<=t;i++)        if(t&bin[i])x=fa[x][i];    if(x==y)return x;    for(int i=16;i>=0;i--)        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];    return fa[x][0];}void rev(int x){    vis[x]^=1;    if(vis[x]){p[c[x]]++;if(p[c[x]]==1)ans++;}    else {p[c[x]]--;if(p[c[x]]==0)ans--;}}void move(int u,int v){    for(;u^v;)        if(dep[u]>dep[v])rev(u),u=fa[u][0];        else rev(v),v=fa[v][0];}int main(){    freopen("w.in","r",stdin);    bin[0]=1;    for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;    n=read();m=read();    blo=sqrt(n);    for(int i=1;i<=n;i++)c[i]=read();    for(int i=1,u,v;i<=n;i++)    {        u=read(),v=read();        if(!u)root=v;else if(!v)root=u;        else AE(u,v),AE(v,u);    }    dfs(root);    blonum++;    while(top)bel[st[top--]]=blonum;    for(int i=1;i<=m;i++)    {        int u=read(),v=read(),a=read(),b=read();        if(dfn[u]>dfn[v])swap(u,v);        q[i]=(poi){u,v,a,b,i};    }    sort(q+1,q+1+m,cmp);    int t=lca(q[1].u,q[1].v);    move(q[1].u,q[1].v);    rev(t);//因为是边链，所以怎么处理大家都懂得    res[q[1].i]=ans;    if(p[q[1].a]&&p[q[1].b]&&q[1].a!=q[1].b)res[q[1].i]--;    rev(t);    for(int i=2;i<=m;i++)    {        move(q[i-1].u,q[i].u);        move(q[i-1].v,q[i].v);        t=lca(q[i].u,q[i].v);        rev(t);res[q[i].i]=ans;        if(p[q[i].a]&&p[q[i].b]&&q[i].a!=q[i].b)res[q[i].i]--;        rev(t);    }    for(int i=1;i<=m;i++)        printf("%d\n",res[i]);    return 0;}

### 带修莫队

void timeleap(int x,int y)//修改操作（好中二的名字）{    if(vis[x])rev(x),C[x]=y,rev(x);    else C[x]=y;}for(int j=q[i-1].t+1;j<=q[i].t;j++)    timeleap(c[j].x,c[j].y);//时间跳跃for(int j=q[i-1].t;j>q[i].t;j--)    timeleap(c[j].x,c[j].pre);

#### BZOJ 3052: [wc2013]糖果公园

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100010#define maxm 200010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn],nxt[maxm],to[maxm],Si=1;LL V[maxn],W[maxn],C[maxn],pre[maxn],ans,res[maxn];int bin[20],n,m,top,ind,blo,blonum;int fa[maxn][17],dep[maxn],num[maxn];int st[maxn],dfn[maxn],bel[maxn];bool vis[maxn];struct poi{int x,y,t,i;}q[maxn];struct UUZ{int x,y,pre;}c[maxn];inline bool cmp(const poi &a,const poi &b){    if(bel[a.x]==bel[b.x]&&bel[a.y]==bel[b.y])return a.t<b.t;    else if(bel[a.x]==bel[b.x])return bel[a.y]<bel[b.y];    else return bel[a.x]<bel[b.x];}int dfs(int x){    int size=0;    dfn[x]=++ind;    for(int i=1;i<=16;i++)        fa[x][i]=fa[fa[x][i-1]][i-1];    for(int i=idx[x];i;i=nxt[i])        if(to[i]!=fa[x][0])        {            dep[to[i]]=dep[x]+1;            fa[to[i]][0]=x;            size+=dfs(to[i]);            if(size>=blo)            {                blonum++;                for(int k=1;k<=size;k++)                    bel[st[top--]]=blonum;                size=0;            }        }    st[++top]=x;    return size+1;}int lca(int x,int y){    if(dep[x]<dep[y])swap(x,y);    for(int i=0,t=dep[x]-dep[y];bin[i]<=t;i++)        if(t&bin[i])x=fa[x][i];    if(x==y)return x;    for(int i=16;i>=0;i--)        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];    return fa[x][0];}void rev(int x){    if(vis[x])ans-=W[num[C[x]]]*V[C[x]],num[C[x]]--;    else num[C[x]]++,ans+=W[num[C[x]]]*V[C[x]];    vis[x]^=1;}void timeleap(int x,int y){    if(vis[x])rev(x),C[x]=y,rev(x);    else C[x]=y;}void move(int u,int v){    for(;u^v;)        if(dep[u]>dep[v])rev(u),u=fa[u][0];        else rev(v),v=fa[v][0];}int main(){    bin[0]=1;    for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;    n=read();m=read();int Q=read();    blo=pow(n,2.0/3)*0.5;    for(int i=1;i<=m;i++)V[i]=read();    for(int i=1;i<=n;i++)W[i]=read();    for(int i=1,u,v;i<n;i++)        u=read(),v=read(),AE(u,v),AE(v,u);    for(int i=1;i<=n;i++)pre[i]=C[i]=read();    dfs(1);    blonum++;    while(top)bel[st[top--]]=blonum;    int c1=0,c2=0;    for(int i=1;i<=Q;i++)    {        int typ=read(),x=read(),y=read();        if(!typ)            c[++c1]=(UUZ){x,y,pre[x]},pre[x]=y;        else        {            if(dfn[x]>dfn[y])swap(x,y);            q[++c2]=(poi){x,y,c1,c2};        }    }    sort(q+1,q+1+c2,cmp);    for(int i=1;i<=q[1].t;i++)        timeleap(c[i].x,c[i].y);    move(q[1].x,q[1].y);    int t=lca(q[1].x,q[1].y);    rev(t);res[q[1].i]=ans;rev(t);    for(int i=2;i<=c2;i++)    {        for(int j=q[i-1].t+1;j<=q[i].t;j++)            timeleap(c[j].x,c[j].y);        for(int j=q[i-1].t;j>q[i].t;j--)            timeleap(c[j].x,c[j].pre);        move(q[i-1].x,q[i].x);        move(q[i-1].y,q[i].y);        t=lca(q[i].x,q[i].y);        rev(t);res[q[i].i]=ans;rev(t);    }    for(int i=1;i<=c2;i++)        printf("%lld\n",res[i]);    return 0;}

#### BZOJ 4129: Haruna’s Breakfast

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 50010#define maxm 100010#define maxb 250using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn],nxt[maxm],to[maxm],Si=1;int a[maxn];int bin[20],n,top,ind,blo,blonum;int fa[maxn][17],dep[maxn],num[maxn];int st[maxn],res[maxn],pre[maxn],dfn[maxn],bel[maxn];bool vis[maxn];struct poi{int x,y,t,i;}q[maxn];struct UUZ{int x,y,pre;}c[maxn];inline bool cmp(const poi &a,const poi &b){    if(bel[a.x]==bel[b.x]&&bel[a.y]==bel[b.y])return a.t<b.t;    else if(bel[a.x]==bel[b.x])return bel[a.y]<bel[b.y];    else return bel[a.x]<bel[b.x];}int dfs(int x){    int size=0;    dfn[x]=++ind;    for(int i=1;i<=16;i++)        fa[x][i]=fa[fa[x][i-1]][i-1];    for(int i=idx[x];i;i=nxt[i])        if(to[i]!=fa[x][0])        {            dep[to[i]]=dep[x]+1;            fa[to[i]][0]=x;            size+=dfs(to[i]);            if(size>=blo)            {                blonum++;                for(int k=1;k<=size;k++)                    bel[st[top--]]=blonum;                size=0;            }        }    st[++top]=x;    return size+1;}int lca(int x,int y){    if(dep[x]<dep[y])swap(x,y);    for(int i=0,t=dep[x]-dep[y];bin[i]<=t;i++)        if(t&bin[i])x=fa[x][i];    if(x==y)return x;    for(int i=16;i>=0;i--)        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];    return fa[x][0];}int f[maxn],ba[maxb],bb[maxn],SIZ,l[maxb],r[maxb];void rev(int x){    if(a[x]>n)return;    if(vis[x])    {        if(!--f[a[x]])ba[bb[a[x]]]--;    }    else        if(!f[a[x]]++)ba[bb[a[x]]]++;    vis[x]^=1;}void timeleap(int x,int y){    if(vis[x])rev(x),a[x]=y,rev(x);    else a[x]=y;}void move(int u,int v){    for(;u^v;)        if(dep[u]>dep[v])rev(u),u=fa[u][0];        else rev(v),v=fa[v][0];}int qry(){    if(!f[0])return 0;    int i;    for(i=1;l[i];i++)if(ba[i]!=r[i]-l[i]+1)break;    for(int j=l[i];j<=r[i];j++)if(!f[j])return j;    return n;}int main(){    bin[0]=1;    for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;    n=read();int Q=read();    SIZ=(int)(sqrt(n)+1e-7);    blo=pow(n,2.0/3)*0.5;    for(int i=1;i<=n;i++)bb[i]=(i-1)/SIZ+1,pre[i]=a[i]=read();    for(int i=1;(i-1)*SIZ+1<=n;i++)        l[i]=(i-1)*SIZ+1,r[i]=min(i*SIZ,n);    for(int i=1,u,v;i<n;i++)        u=read(),v=read(),AE(u,v),AE(v,u);    dfs(1);    blonum++;    while(top)bel[st[top--]]=blonum;    int c1=0,c2=0;    for(int i=1;i<=Q;i++)    {        int typ=read(),x=read(),y=read();        if(!typ)            c[++c1]=(UUZ){x,y,pre[x]},pre[x]=y;        else        {            if(dfn[x]>dfn[y])swap(x,y);            q[++c2]=(poi){x,y,c1,c2};        }    }    sort(q+1,q+1+c2,cmp);    for(int i=1;i<=q[1].t;i++)        timeleap(c[i].x,c[i].y);    move(q[1].x,q[1].y);    int t=lca(q[1].x,q[1].y);    rev(t);res[q[1].i]=qry();rev(t);    for(int i=2;i<=c2;i++)    {        for(int j=q[i-1].t+1;j<=q[i].t;j++)            timeleap(c[j].x,c[j].y);        for(int j=q[i-1].t;j>q[i].t;j--)            timeleap(c[j].x,c[j].pre);        move(q[i-1].x,q[i].x);        move(q[i-1].y,q[i].y);        t=lca(q[i].x,q[i].y);        rev(t);res[q[i].i]=qry();rev(t);    }    for(int i=1;i<=c2;i++)        printf("%d\n",res[i]);    return 0;}

## 数论加速

### 分块计算

for(ans=0,i=1;i<=n&&i<=m;i=j+1)//单指标求和{    j=n/(n/i);//到块尾    ans+=(j-i+1)*(n/i);}

#### BZOJ 4407: 于神之怒加强版

$f(n)=n^k$，则$F$$f$$\mu$的狄利克雷卷积。

/*    Author:Scarlet*/#include<bits/stdc++.h>#define N 5000001#define mod 1000000007using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}inline int Pow(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)t=1LL*t*a%mod;return t;}int T,n,m,k,tot,p[N],f[N],g[N],F[N],ans;bool v[N];int main(){    T=read(),k=read();    F[1]=1;    for(int i=2;i<N;i++)    {        if(!v[i])f[i]=Pow(i,k),g[i]=i,F[i]=f[i]-1,p[tot++]=i;        for(int j=0;j<tot&&i*p[j]<N;j++)        {            v[i*p[j]]=1;            if(i%p[j])            {                g[i*p[j]]=p[j];                F[i*p[j]]=1LL*F[i]*F[p[j]]%mod;            }            else            {                g[i*p[j]]=g[i]*p[j];                F[i*p[j]]=g[i]!=i?1LL*F[i/g[i]]*F[g[i]*p[j]]%mod:1LL*F[i]*f[p[j]]%mod;                break;            }        }    }    for(int i=2;i<N;i++)F[i]=(F[i-1]+F[i])%mod;    for(int i,j;T--;)    {        n=read(),m=read();        for(ans=0,i=1;i<=n&&i<=m;i=j+1)        {            j=min(n/(n/i),m/(m/i));            ans=(1LL*(F[j]-F[i-1]+mod)*(n/i)%mod*(m/i)+ans)%mod;        }        printf("%d\n",ans);    }    return 0;}

### 分块打表

#### POJ 2689: Prime Distance加强

$2^{12}$块，每块$2^{19}$大小用std跑出块内答案，记录首尾质数。边角料一样用std跑，块间XJB合并一下..

## 询问分类

#### BZOJ 2506: calc

$p\leq 100$$p>100$

/*    Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100010#define maxp 10000#define sqrp 100using namespace std;typedef long long LL;#define G c=getchar()inline int read(){    int x=0,f=1;char G;    while(c>57||c<48){if(c=='-')f=-1;G;}    while(c>47&&c<58)x=x*10+c-48,G;    return x*f;}int f1[10010],f2[101][101],a[maxn],ans[maxn],tot;struct poi{int a,p,k,i;}q[maxn*2];inline bool cmp(const poi &a,const poi &b){return a.a<b.a;}int main(){    int n=read(),m=read();    for(int i=1;i<=n;i++)a[i]=read();    for(int i=1,l,r,p,k;i<=m;i++)    {        l=read(),r=read(),p=read(),k=read();        q[tot]=(poi){r,p,k,tot},tot++;        q[tot]=(poi){l-1,p,k,tot},tot++;    }    sort(q,q+tot,cmp);int now=0;    while(!q[now].a&&now<tot)now++;    for(int i=1;i<=n;i++)    {        f1[a[i]]++;        for(int p=1;p<=sqrp;p++)            f2[p][a[i]%p]++;        for(;q[now].a==i&&now<tot;now++)        {            poi& a=q[now];            int re=0;            if(a.p<=sqrp)re=f2[a.p][a.k];            else                for(int w=a.k;w<=maxp;w+=a.p)                    re+=f1[w];            if(a.i&1)ans[a.i>>1]-=re;            else ans[a.i>>1]+=re;        }    }    for(int i=0;i<m;i++)        printf("%d\n",ans[i]);    return 0;}

• 私有
• 公开
• 删除