vjudge上莫队专题

真的是要吐槽自己(自己的莫队手残写了2个bug)

s=sqrt(n) 是元素的个数而不是询问的个数(之所以是sqrt(n)使得左端点每个块左端点的范围嘴都是sqrt(n))
在重载<是将q[i].l/s<q2[i].l/s 写成q1[i].l<s<q2[i].l<s 导致一下午都在调bug疯了

Sona

比小Z的袜子简单，直接维护区间频度的^3
需要离散化(离散化化的标号应提前准备好,如果用时在二分查找会增加复杂度)
还有比较坑的一点是多case,但样例只有一个case;多case一定要注意那些结构需要清空

cf:221D Little Elephant and Array

维护x=freq(x)的个数

Little Elephant and Array

维护区间相异元素的个数(通过出现次数便可很好写[L,R]->[L-1,R]...的转移)
转移有一种非常简单的写法:先减去关于元素q的信息，然后更新(可能删除或加上q),然后重新加上元素q相关信息

D-query

维护区间\(s*freq(s)^2\),freq(s)是s出现的次数
这里有个int溢出的坑(如注释所示)

inline void move(ll& now,int p,int v){

    now-=(ll)num[c[p]]*num[c[p]]*tmp[p];//不强制转换为ll会WA

    num[c[p]]+=v;

    now+=(ll)num[c[p]]*num[c[p]]*tmp[p];

    //printf("db1 %lld %d %d %d %d\n",now,c[p],p,num[c[p]],v);

    /*

    if(v==1){

        now+=(1+2*num[c[p]])*tmp[p];//这种从数学上简化一步缩小增量大小，也可以

        num[c[p]]++;

    }

    else{

        now+=(1-2*num[c[p]])*tmp[p];

        num[c[p]]--;

    }

    */

    /*

    printf("db1 %lld %d %d %d\n",now,p,num[c[p]],v);

    for(int i=1;i<=n;i++){

        printf("%d\t",num[c[i]]);

    }

    printf("\n");

    */

}

Fast Queries

比较卡时间，经时间证明 ,下面写法能卡过

struct Query{

    int l,r,id;

    bool operator < (const Query&a) const{

        if(l / s != a.l / s) return l / s < a.l / s;

        return r < a.r;

    }

    /*

    void read(int i){

        scanf("%d %d",&l,&r);

        id = i;

    }

    */

}ques[maxm];

对运算符号重载的另一种写法不能卡过

struct Query{

    int l,r,id;

    inline friend bool operator <(const Query& q1,const Query&q2){

        if(q1.l/s!=q2.l/s) return q1.l/s<q2.l/s;

        return q1.r<q2.r;

    }

}ques[maxn];

总结一下自己对这种裸的模板题的坑:

n,m的含义不要混淆
分块s=sqrt(n)
注意离散化开的数组含义，一起询问的l,r是下标，需要通过数组才能得到真正信息
防止整形溢出
运算重载的写法能优化速度

巴特西

Sona && Little Elephant and Array && Little Elephant and Array && D-query && Powerful array && Fast Queries (莫队)

vjudge上莫队专题

真的是要吐槽自己(自己的莫队手残写了2个bug)

Sona

cf:221D Little Elephant and Array

Little Elephant and Array

D-query

Fast Queries

总结一下自己对这种裸的模板题的坑:

加油不要手残呀

最新文章

热门文章