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

根号算法

——如何让复杂度去掉 $\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玩意儿。

无修: 维护一些JB玩意儿比如块内答案、块间答案，然后询问的时候 $\sqrt n、\sqrt n\log n$ 大力出奇迹。
带修: 考虑打标记或者以一定频率重构块。

BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊

感觉地球人都会听说过而且都会做.
以及我去年2月份代码真好看.

/*
    Author:Scarlet
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#define maxn 200011
using 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 350
using 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;
}

但是我不知怎地就看到了PoPoQQQ的无 $\log$ 分块技巧，比在下带 $\log$ 的好写到不知道哪里去了（但是并不短）。
姿势水平++。

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 210
using 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 200000000000000ll
using 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)

做题前先吟一句诗：苟
这套路贼JB明显。

但是出题人您为什么要卡内存啊，幸好在下分块可以调节块的大小，但还是MLE+RE了不知道几发

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100005
#define maxm 305
#define INF 200000000000000ll
using 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的妹子树

树分块板子题，也是板子来源..
在板子里讲得很清楚了w

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 30300
using 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：《手把手教你树分块系列》

简单来说就是用一遍dfs实现自下而上的贪心
(以下来自hzwer)

一个省至少要有B，如果子树大小超过B，直接子树划个省，根为省会
。。。
剩余的部分小于B的话随便扔哪都是合法的吧

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1005
#define maxm 2010
using 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;
}

咦...树分块好像没有会做的题目了？
没智商可减.jpg

膜队

一般莫队

板子&&原理

序列上的莫队一般是先维护一个区间 $[L\pm 1,R\pm 1]$ 的答案（一般来说这个维护起来十分simple），再通过对离线询问的特殊排序，做到均摊 $n\sqrt n$ 的高妙复杂度。

相信直接看上面一段都看不懂。

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

先离线套个莫队冷静以下，然后问题就变成了如何快速求mex。

考虑到莫队 $O(n\sqrt n)$ 转移， $O(1)$ 计算的特性，明显我们希望有一个 $O(1)$ 插入， $O(\sqrt n)$ 查询的数据结构，这样可以把复杂度降到 $O((n+q)\sqrt n)$ 。

还能怎么办？分块！

对权值分块，记录每个块中数字出现个数以及是否已满。
插入、删除：找到所在块，cnt更新，判断size， $O(1)$
询问：找到第一个未满的块，在块内查询， $O(\sqrt n)$
没了？没了。。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 200100
#define maxm 450
using 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;
}

当然这道题有十分优秀的树状数组离线 $n\log n$ 和主席树在线 $n\log n$ 算法然而并不在讨论范围之中

~~当你点进hzwer的BIT题解时发现他并没有写BIT，反而是写了一个奇慢无比的线段树然后想来把我批判一番时，那么抱歉在下已经用这个算法艹进第一页了~~

BZOJ 3809: Gty的二逼妹子序列

还是十分simple的一道题，一模一样的处理吧。
块间枚举、边角料枚举。
时限挺宽的，卡个毛线常数啊。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100100
#define maxm 350
using 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;
}

树上莫队

板子&&原理

树上莫队一般是先求出一个dfs序，然后把树分块。就可以十分simple地维护一条链的答案。再通过对离线询问的特殊排序，做到均摊 $n\sqrt n$ 的高妙复杂度。

相信直接看上面一段都看不懂。

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: 苹果树

维护链上颜色数。。
暴力莫队啊QAQ。

BZOJ不能交了。
跑了5sRE安慰自己。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 50010
#define maxm 100010
using 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;
}

带修莫队

板子&原理

带修莫队，就是带修改的莫队，同样适合序列上和树上。
考虑每次修改实际上就是时间推移，那么我们把询问带上时间戳，修改一下块的大小为 $n^\frac{2}{3}$ 就能在 $n^\frac{5}{3}$ 内跑了。

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]糖果公园

因为糖果是按序吃按序得分的，而且同样的糖果，123吃法和321的得分是一样的。那么就可以大力莫队了

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100010
#define maxm 200010
using 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

树上求mex，不能再套路了吧。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 50010
#define maxm 100010
#define maxb 250
using 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;
}

数论加速

从丧心病狂的分块莫队过渡到了这儿。
~~没错，我只是想做几道数论题冷静一下。~~

分块计算

板子&原理

大家都知道 $\lfloor\frac{n}{i}\rfloor$ 最多有 $\sqrt n$ 个取值。
那么 $\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$ 只要把 $\sqrt n$ 个取值出现了几次搞一搞就好了。

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

BZOJ 4407: 于神之怒加强版

题解：From Claris

$\begin{eqnarray*} &&\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k\\ &=&\sum_d d^k\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\\ &=&\sum_d d^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\\ &=&\sum_d d^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{u|i,u|j}\mu(u)\\ &=&\sum_d d^k\sum_{u}\mu(u)\lfloor\frac{n}{du}\rfloor\lfloor\frac{m}{du}\rfloor\\ &=&\sum_D \lfloor\frac{n}{D}\rfloor\lfloor\frac{m}{D}\rfloor\sum_{d|D}d^k\mu(\frac{D}{d})\\ &=&\sum_D \lfloor\frac{n}{D}\rfloor\lfloor\frac{m}{D}\rfloor F(D) \end{eqnarray*}$
设

$f(n)=n^k$ ，则

$F$ 为

$f$ 和

$\mu$ 的狄利克雷卷积。
对于

$F$ 的计算，质数时直接快速幂，质数的幂递推计算，其它数可以通过线性筛得到。
对于每次询问，分块求和即可。

时间复杂度 $O(n+T\sqrt n)$ 。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define N 5000001
#define mod 1000000007
using 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;
}

分块打表

原理

没什么好说的，大块答案记录，边角料暴力

BZOJ 3798: 特殊的质数

题意：求 $[L,R]$ 中能被表示乘两数平方和的质数个数

懒癌

POJ 2689: Prime Distance加强

题意：在 $[L,R]$ 中找出距离相距最近和最远的两个相邻质数， $1\leq L\leq R < 2^{31}$

先假设大家都会做原题..
好，那么大家都会做加强版了。

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

~~我TM就是个天才~~

询问分类

什么是询问分类？
就是把询问分成两类（或更多），由每一类的特性分别统计答案获得全局较低复杂度。

经典题三元环的个数

题意：给定一个 $n$ 个点， $m$ 条边的简单图，求三元环的个数， $n,m\leq200000$

当点的度不足 $\sqrt m$ 时，称为轻点，否则为重点。
显然重点的数目不超过 $\sqrt m$ 个，考虑枚举其中三个点直接统计，复杂度 $m\sqrt m$
又轻点的出边不足 $\sqrt m$ ，可以枚举两条出边判断三个点是否为三元环，每条边被枚举了 $2$ 次。复杂度 $m\sqrt m$
总复杂度 $m\sqrt m$ ，十分优秀。

找不到OJ中有这道题啊。

BZOJ 2506: calc

题意：给一个长度为 $n$ 的非负整数序列 $A_1,A_2\dots A_n$ 。现有 $m$ 个询问，每次询问给出 $l,r,p,k$ ，问满足 $l\leq i\leq r$ 且 $A_i\mod p = k$ 的值 $i$ 的个数。

离线，询问拆分并分成两类
$p\leq 100$ 和 $p>100$
前者可以用f1[i][j]表示加入的元素对i取模余数为j的个数
后者用f2[i]表示大小为i的数的个数，因为 $p>100$ 只要将f[k],f[k+p],f[k+2*p]……最多 $100$ 个数相加即可

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100010
#define maxp 10000
#define sqrp 100
using 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;
}

HDU 4858: 项目管理

度大于 $\sqrt m$ 的点叫重点，否则叫轻钦点。
把重点之间构苟一个“重图”。

轻点更新：更新邻居答案， $O(\sqrt m)$
轻点查询：求所有邻居和， $O(\sqrt m)$
重点更新：更新自己， $O(1)$
重点查询：把来自于轻点的答案加上“重图”上的邻居和， $O(\sqrt m)$

完美解决

~~然而我这题模拟直接过我并没有写代码~~

结语

当我花一个星期写完这些文章的时候，发现分块和莫队都已经成为了时代的眼泪（HNOI：？？？）。
幸好数论求和这类JB玩意儿仍是现今的考点（但是你推不出公式并没有什么乱用）。
所以大家还是要从套路性根号算法中学到一些优化思想，再用到更加现代化的题目上去。

祝一题一题看到这里的选手省选暴力进队。

根号算法

分块

一般分块

BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊

BZOJ 2724: [Violet 6]蒲公英

BZOJ 4241: 历史研究

BZOJ 2821: 作诗(Poetize)

树分块

BZOJ 3720: Gty的妹子树

BZOJ 1086: [SCOI2005]王室联邦

膜队

一般莫队

BZOJ 3585: mex

BZOJ 3809: Gty的二逼妹子序列

树上莫队

BZOJ 3757: 苹果树

带修莫队

BZOJ 3052: [wc2013]糖果公园

BZOJ 4129: Haruna’s Breakfast

数论加速

分块计算

BZOJ 4407: 于神之怒加强版

分块打表

BZOJ 3798: 特殊的质数

POJ 2689: Prime Distance加强

询问分类

经典题 三元环的个数

BZOJ 2506: calc

HDU 4858: 项目管理

结语

内容目录

经典题三元环的个数