题解 P3372 【【模板】线段树 1】

· · 题解

去了wc2019的同学应该对 指令集 有些印象，没去的同学 ( 比如我 ) 可能也通过一些途径了解到了这个暴力踩标程的毒瘤 ( 据说现场踩 Ynoi五彩斑斓的世界 ) 。但是由于我太弱，实在过不了那道题 dllxl Orz ，所以我就来拿这道题练手了。

一、指令集是什么？

其实就是压位，常用的是压256位。也有能压512位的，但大部分情况不支持 ( 硬件 + 软件 ) 。

二、它为什么快？

就像压位高精会比裸高精快， bitset 比 bool数组 快一样，你把8个32位的 int 压成一个256位的玩意儿，每次操作可以看成是同时对8个 int 进行操作 ( 但其实并不是这样 ) ，所以理论上常数会是原来的 \frac{1}{8} ( 但其实做不到 \frac{1}{8} ) 。

三、它要怎么用？

请自行摸索

首先你需要 immintrin.h 库，里面啥都有然后再在程序前加上 #pragma GCC target("avx,avx2") ，这样你就可以把你的 int 啊 long long 啊什么的压成 __m256i ，把 float 压成 __m256 ，还能把 double 压成 __m256d 。

什么你问我具体怎么做？我不知道啊.jpg

这里是连快读都没用的O\left(n^2\right)暴力评测记录。

最后附上这道题的程序，想学学指令集的可以看看：

#pragma GCC optimize("Ofast,fast-math")
#pragma GCC target("avx,avx2")
#include <cstdio>
#include <immintrin.h>

int n,m,num,x[5],opt,p,q,k;
__m256i a[25010];

inline void add(int l,int r,int v)
{
    while(((l-1)&3)&&l<=r)((long long*)(a+(l>>2)+1))[(l&3)-1]+=v,++l;
    if(l==r+1)return;
    while((r&3)&&l<=r)((long long*)(a+(r>>2)+1))[(r&3)-1]+=v,--r;
    if(l==r+1)return;
    l=(l>>2)+1,r>>=2;
    __m256i s=_mm256_set_epi64x(v,v,v,v);
    while(l<=r)a[l]=_mm256_add_epi64(a[l],s),++l;
}

inline long long query(int l,int r)
{
    long long ans(0);
    while(((l-1)&3)&&l<=r)ans+=((long long*)(a+(l>>2)+1))[(l&3)-1],++l;
    if(l==r+1)return ans;
    while((r&3)&&l<=r)ans+=((long long*)(a+(r>>2)+1))[(r&3)-1],--r;
    if(l==r+1)return ans;
    l=(l>>2)+1,r>>=2;
    __m256i s=_mm256_set_epi64x(0,0,0,0);
    while(l<=r)s=_mm256_add_epi64(a[l],s),++l;
    for(int i=0;i<4;++i)
        ans+=((long long*)&s)[i];
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);num=n>>2;
    for(int i=1;i<=num;++i)
    {
        for(int j=1;j<=4;++j)
            scanf("%d",x+j);
        a[i]=_mm256_set_epi64x(x[4],x[3],x[2],x[1]);
    }
    for(int i=1;i<=(n&3);++i)
        scanf("%d",x+i);
    a[++num]=_mm256_set_epi64x(x[4],x[3],x[2],x[1]);

    while(m--)
    {
        scanf("%d%d%d",&opt,&p,&q);
        if(opt==1)
            scanf("%d",&k),add(p,q,k);
        else
            printf("%lld\n",query(p,q));
    }
    return 0;
}

这道题要开 long long ，如果是 int 的话程序第一句的 Ofast 优化去掉也能过！

最后的最后，如果你从这篇题解中学到了些东西，请动动手帮忙点赞，谢谢啦！