卡常大战

luogu1494 小z的袜子

这道题作为一道莫队板子题，其实没有单独开一篇解题报告的意义。

我只是想记录一下这一场轰轰烈烈的卡常大战。

先说题目吧，这个题其实最难想的就是组合数了

对于一个区间[L,R]，如果a,b,c,d是颜色，我们可以想到用组合数C(a,2)来表示在a中选两个有多少种选法，

那么我们需要的答案就是

(C(a,2)+C(b,2)+C(c,2))/C(r-l+1,2)

继续往下推导

分子为(a(a-1)+b(b-1)+c(c-1))/2，分母为len(len-1)/2

上下同时乘以2，可得

(a2+b2+c2-a-b-c)/len(len-1)

-a-b-c=-(a+b+c)=len

所以我们这个题只需要通过莫队来维护每种颜色数量的平方和tot就行了

我们继续往下看，如果一个a颜色入队，那么tot要减去a2，加上(a+1)2，消去a2，就相当于tot加上2*a+1

如果是a颜色出队，那就是tot加上-2*a+1

莫队的话就是个板子，结合代码很好理解了，但是代码里面有很多玄学优化，在文末会总结到，如果不是过分追求时间优越的话可以忽略，但是部分有极大的借鉴意义。

先上代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define rint register int
#define ll long long 
#define inv inline void
#define inl inline long long
#define ini inline int 
#define maxn 50010
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1000000,stdin),S==T)?EOF:*S++)
char BB[1000000],*S=BB,*T=BB;
using namespace std;
int a[maxn],num[maxn],be[maxn];
ll tot;
ini read()
{
    rint c,r=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        r=r*10+(c^48);
        c=getchar();
    }
    return r;
}
struct node 
{
    int l,r,id;	
    ll len,w,z;
}b[maxn];
ini cmp(const node &a,const node &b)
{
    if (be[a.l]!=be[b.l]) return be[a.l]<be[b.l];
    if (be[a.l]&1) return a.r<b.r;
    return a.r>b.r;
}
ini cmp_id(const node a,const node b)
{
    return a.id<b.id;
}
inl gcd(ll a,ll b)
{
    if (b) return gcd(b,a%b);
    return a;
}
inv add(int x)
{
    tot+=(num[x]<<1)|1; ++num[x];
}
inv pop(int x)
{
    tot+=1-(num[x]<<1); --num[x];
}
int wt[30];
inv putout(ll x)
{
    if(!x) {putchar(48);return;}
    rint l=0;
    while(x) wt[++l]=x%10,x/=10;
    while(l) putchar(wt[l--]+48);
}
int main()
{
    register int n,m;
    register ll g=0;
    n=read();m=read();
    for (rint i=1;i<=n;i++) a[i]=read();
    for (rint i=1;i<=m;i++)
    {
        b[i].l=read();b[i].r=read();
        b[i].id=i;b[i].len=b[i].r-b[i].l+1;
    }
    register int block=int(n/sqrt(m*2/3));
    for (rint i=1;i<=n;i++) be[i]=((i-1)/block)+1;
    sort(b+1,b+m+1,cmp);
    for (rint i=b[1].l;i<=b[1].r;i++) add(a[i]);
    if (tot-b[1].len==0)
    {
        b[1].w=0;b[1].z=1;
    }
    else
    {
        b[1].w=tot-b[1].len;b[1].z=(b[1].len)*(b[1].len-1);
        g=gcd(b[1].z,b[1].w);
        b[1].w/=g;b[1].z/=g;
    }
    register int L=b[1].l,R=b[1].r;
    for (rint i=2;i<=m;i++)
    {
        while (b[i].l<L) add(a[--L]);
        while (b[i].l>L) pop(a[L++]);
        while (b[i].r<R) pop(a[R--]);
        while (b[i].r>R) add(a[++R]);
        if (tot-b[i].len==0)
        {
            b[i].w=0;b[i].z=1;
        }
        else
        {
            b[i].w=tot-b[i].len;b[i].z=(b[i].len)*(b[i].len-1);
            g=gcd(b[i].z,b[i].w);
            b[i].w/=g;b[i].z/=g;
        }
    }
    sort(b+1,b+m+1,cmp_id);
    for (rint i=1;i<=m;i++)
    	putout(b[i].w),putchar('/'),putout(b[i].z),putchar(10);
}

涉及到的玄学优化一览

以下的玄学优化按照代码从头到尾的顺序，建议添加的我会标粗

  1. inline 及 register 的应用

  2. fread函数读入(这个的确能加快很多，但是没有很大的添加的必要)

   #define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1000000,stdin),S==T)?EOF:*S++)
   char BB[1000000],*S=BB,*T=BB;

  1. 一个小常识，能用int的就别用long long

  2. 快读中运用位运算

  3. cmp函数不用bool类型(bool本身就比int慢，但因为cmp函数本身就玄学，不推荐使用)

  4. cmp函数用const node &a而不是直接node a

  5. 排序用奇偶分别排右端点来优化

    ini cmp(const node &a,const node &b)
{
    if (be[a.l]!=be[b.l]) return be[a.l]<be[b.l];
    if (be[a.l]&1) return a.r<b.r;
    return a.r>b.r;
}

  6. 写gcd函数时用递归写法(我也不确定这样变快还是变慢……但是代码好写啊，注意一定是较大的数在前，较小的数在后)

    inl gcd(ll a,ll b)
{
    if (b) return gcd(b,a%b);
    return a;
}

  7. 对于偶数用或1来代替+1

  8. 尽量把++放在前面，这样比放在后面要快

  9. 输出优化，利用putchar的优越性进行输出，这里迭代型的确比递归型要快

    int wt[30];
inv putout(ll x)
{
    if(!x) {putchar(48);return;}
    rint l=0;
    while(x) wt[++l]=x%10,x/=10;
    while(l) putchar(wt[l--]+48);
}

  10. 尽量多定义局部变量，但不要忘了初始化，定义的时候类型前面可以加register

  11. 分块优化。在莫队中尽量把块的大小定义成(n/sqrt(m*2/3))

  12. 可用用putchar(10)来代替输出回车

  13. 老生常谈，能用位运算就用位运算

  14. 为了防止玄学错误，要多进行类型的强制转换，装换之前也要先冷静下来仔细想想，这样转换对不对

卡常大战记

之前听毒瘤讲师noip说过，莫队是一个可以大力卡常数的数据结构，于是好奇的我决定用这个题做实验来看看到底能卡到什么地步。

于是叫上了神队友Asia 以及 zyc

三个人合力从不到300ms怒卡到244ms，冒着被封号的风险，活活刷了好几页评测记录。

之后由于太naive而黔驴技穷，叫上了真正的神杜佬dsq

杜佬在卡到240上不去了之后怒看了chen_zhe爷的代码，发现了各种玄学优化，一路高歌猛进卡进200ms。

本蒟蒻在最后一次尝试中人品爆发，最终成绩192ms

不过我也付出了惨痛的代价，一个人刷了整整五页评测记录。在我们四个做这道题之前，提交数是600多，但是现在经过一个多小时的奋战(卡常)已经接近1k了

废话不多说，有图有真相

赞 赏
蒟蒻的邮箱:xmzl200201@126.com