幻想的大悲咒！龙鱼波特认为在五大学科竞赛的学习中，蕴涵着三类成功型内卷思想，这三种思想是：1、别人不卷我要卷；2、别人说我卷我就反咬一口；3、打不过我就魔法少女啊，变身友利奈绪啊怼怼怼。

FutaRimeWoawaSete · 2023-01-31 19:23:02 · 题解

sol of P8337

线性空间，线性查询你也卡常是吧？

线性空间，线性查询你也卡常是吧？

线性空间，线性查询你也卡常是吧？

然后还有更毒瘤的带空间版本，我不懂了。Ynoi 不是为了卡常而卡常。虽然也习惯了，毕竟破防演练。

最离谱的是要了三份代码对拍前两份都 UB 了。

一年前就实现过了，然后寄了。

我们先考虑转化问题，发现查询的要求子区间 [x,y] 条件等价于 [x,y] 中的数组成集合 S，满足 span(S) = S 且 0 \in S。

考虑反证法。假设存在 span(S) \not = S 且任意的 i \bigoplus j \in S。原问题限制下除非空集则 S 中必然含 0。若 span(S) \not = S 考虑一个子集 T 的按位异或和 V，我们可以递归地将其分拆成两个数按位异或的形式，例如 (x_1,x_2,x_3,x_4)，我们可以递归地将 x_1 \bigoplus x_2,x_3 \bigoplus x_4 这两个数在 S 内，然后就可以推导出来 x_1 \bigoplus x_2 \bigoplus x_3 \bigoplus x_4 在 S 内。

然后就简单了：合法的 [x,y] 满足其中的颜色数为 2 ^ k。固定右端点 r，枚举所有合法长度，对于每种长度合法左端点 l 形成了一个区间 [l_1,l_2]，用一个三元组描述就是 (l_1,l_2,r)，这样的三元组至多 O(n \log n) 个。

我们采用可扫描线的线性基即可维护固定 r 时长为一定量的线性基范围，注意特判最近的 0 的位置。

然后对于每种长度，随着 r 的递增，(l_1,l_2) 单调不下降，这个可以直接前缀和维护的，我把具体方法写代码里了，自己看吧。

时间复杂度 O(n \log n)，强制在线空间复杂度 O(n \log n)。

然后卡常：

• 基础的卡常，卡卡循环展开，指令集，还有一些 cache；

• 排线性基的 tim 序时别写 O(\log n \log \log n) 的；

• 查询时根据区间长从小长度区间问到大长度区间。

实现时我还特判了全 0，即集合颜色数为 1 的区间这种情况。

其实这道题正常写不卡常的，卡空间倒是，我也卡不过 256MB 和 1.37s。这道题也是卡着跑的，建议不要直接学实现，仅供参考。

/*
设 (l,r,R') 是贡献元组，(L,R) 是查询区间 
r >= L & l < L & R' <= R ;L <= l & r <= R。
维护 r 里面第一个大于等于 L 的区间，维护 l 里面最后一个 < L 的区间，维护 R' <= R 的最后一个区间 
(l,R')
维护 l 里面第一个 >= L 的区间，维护 R' <= R 的最后一个区间 
前缀和内维护的东西
第一类：\sum r；L 维护的系数；+1 的系数
第二类：直接区间和。
*/
const int Len = 6e5 + 5 , M = 1e6 + 5 , LOG = 30 , V = 20;
int lsh[Len],ct,a[Len],n,q,m;vector<int> rk;
inline bool cmp(int x,int y){return x > y;}
struct Linearbasis
{
    int a[LOG + 5],tim[LOG + 5]; 
    Linearbasis(){memset(a , 0 , sizeof a);memset(tim , 0 , sizeof tim);}
    inline void getSt(int x,int y)
    {
        int i = 0 , j = 0 , Sz = (int)rk.size() , tt = 0;
        vector<int> ns;ns.reserve(Sz + (!x));
        while(i < Sz && j < 1)
        {
            if(rk[i] == x && !tt) 
            {
                tt ++;
                i ++;
                continue;
            }
            if(rk[i] > y) ns.push_back(rk[i ++]);
            else ns.push_back(y) , j ++;
        }
        while(i < Sz) 
        {
            if(rk[i] == x && !tt) 
            {
                tt ++;
                i ++;
                continue;
            }
            ns.push_back(rk[i ++]);
        }
        while(j < 1) ns.push_back(y) , j ++;
        swap(ns , rk);
    }
    inline void ins(int x,int tm)
    {
        const int idd = tm;
        for(int i = LOG - 1 ; i >= 0 ; i -= 3)
        {
            if((x >> i) & 1) 
            {
                if(tim[i] < tm) swap(x , a[i]) , swap(tim[i] , tm);
                if(!tm){ct ++;break;}
                x ^= a[i];
            }
            int I = i - 1;
            if(I < 0) break;
            if((x >> I) & 1) 
            {
                if(tim[I] < tm) swap(x , a[I]) , swap(tim[I] , tm);
                if(!tm){ct ++;break;}
                x ^= a[I];
            }
            I = i - 2;
            if(I < 0) break;
            if((x >> I) & 1) 
            {
                if(tim[I] < tm) swap(x , a[I]) , swap(tim[I] , tm);
                if(!tm){ct ++;break;}
                x ^= a[I];
            }
        }
        if(tm != idd) getSt(tm , idd);
    }
}Bs;
int cc[V][Len],nm[V],idx[V];
ll sr[V][Len];
int so[V][Len],sL[V][Len];
int len[V];
ll ss[V][Len];
int sufr[V][Len],prel[V][Len],sufl[V][Len],preR[V][Len],zsm[Len];
int col[V][Len],nmm[V],idxx[V];
inline void get(const int le)
{
    while(nm[le] > (1 << le)) 
    {
        cc[le][a[idx[le]]] --;
        if(!cc[le][a[idx[le] ++]]) nm[le] --;
    }
}
inline void gtt(const int le)
{
    int tt = 0;
    while(nmm[le] >= (1 << le)) 
    {
        tt ++;
        col[le][a[idxx[le]]] --;
        if(!col[le][a[idxx[le] ++]]) nmm[le] --;
    }
    if(tt) nmm[le] ++ , idxx[le] -- , col[le][a[idxx[le]]] ++;
}
inline void add(int le,int x){if(!cc[le][x] ++) nm[le] ++;}
inline void adx(int le,int x){if(!col[le][x] ++) nmm[le] ++;}
int lstl[V],lstr[V],lstR[V],lstid[V];
int cmd[Len];int nmmm;
inline void Work()
{
    int lst0 = -1 , lsto0 = -1;for(int j = 0 ; j < V ; ++ j) idx[j] = idxx[j] = 1 , nm[j] = nmm[j] = 0;
    for(int i = 1 ; i <= n ; ++ i)
    {
        if(!cmd[a[i]] ++) nmmm ++;
        if(!lsh[a[i]]) lst0 = i;
        else lsto0 = i;
        for(int j = 0 ; j < V ; ++ j) 
        {
            add(j , a[i]) , adx(j , a[i]);
            get(j) , gtt(j);
        }
        Bs.ins(lsh[a[i]] , i);
        int l,r,L,R,ul,ur;
        if(lst0 != -1)
        {
            const int LIM = min(V , (int)rk.size());
            for(int j = 1 ; j <= LIM && (1 << j) <= nmmm ; ++ j) 
            {
                if(nm[j] >= (1 << j)) 
                {
                    l = idx[j] , r = idxx[j];
                    if(j >= (int)rk.size()) L = 1 , R = rk[j - 1];
                    else L = rk[j] + 1 , R = rk[j - 1];
                    R = min(lst0 , R);if(L > R) continue;
                    ul = max(l , L) , ur = min(r , R);if(ul > ur) continue;
                    len[j] ++;const int now = len[j];
                    sr[j][now] = sr[j][now - 1] , sL[j][now] = sL[j][now - 1] , so[j][now] = so[j][now - 1];
                    sr[j][now] += ur , sL[j][now] -- , so[j][now] ++;
                    ss[j][now] = ss[j][now - 1] + (ur - ul + 1);
                    for(int k = lstr[j] + 1 ; k <= ur ; ++ k) sufr[j][k] = now;
                    if(lstl[j] != ul)
                    {
                        for(int k = lstl[j] + 1 ; k <= ul ; ++ k) prel[j][k] = lstid[j];
                    }
                    for(int k = lstl[j] + 1 ; k <= ul ; ++ k) sufl[j][k] = len[j];
                    for(int k = lstR[j] ; k < i ; ++ k) preR[j][k] = lstid[j];
                    lstl[j] = ul , lstr[j] = ur , lstR[j] = i , lstid[j] = len[j];
                } 
            }
        }
        if(!lsh[a[i]]) 
        {
            ul = lsto0 + 1 , ur = i;int j = 0;
            len[j] ++;const int now = len[j];
            sr[j][now] = sr[j][now - 1] , sL[j][now] = sL[j][now - 1] , so[j][now] = so[j][now - 1];
            sr[j][now] += ur , sL[j][now] += -1 , so[j][now] ++;
            ss[j][now] = ss[j][now - 1] + (ur - ul + 1);
            for(int k = lstr[j] + 1 ; k <= ur ; k += 3) 
            {
                sufr[j][k] = now;
                if(k + 1 <= ur) sufr[j][k + 1] = now;
                if(k + 2 <= ur) sufr[j][k + 2] = now;
            }
            if(lstl[j] != ul)
            {
                for(int k = lstl[j] + 1 ; k <= ul ; k += 3) 
                {
                    prel[j][k] = lstid[j];
                    if(k + 1 <= ul) prel[j][k + 1] = lstid[j];
                    if(k + 2 <= ul) prel[j][k + 2] = lstid[j];
                }
            }
            for(int k = lstl[j] + 1 ; k <= ul ; k += 3) 
            {
                sufl[j][k] = len[j];
                if(k + 1 <= ul) sufl[j][k + 1] = len[j];
                if(k + 2 <= ul) sufl[j][k + 2] = len[j];
            }
            for(int k = lstR[j] ; k < i ; k += 3) 
            {
                preR[j][k] = lstid[j];
                if(k + 1 < i) preR[j][k + 1] = lstid[j];
                if(k + 2 < i) preR[j][k + 2] = lstid[j];
            }
            lstl[j] = ul , lstr[j] = ur , lstR[j] = i , lstid[j] = len[j];
        }
        if(i == n) 
        {
            for(int j = min(V , (int)rk.size()) ; j >= 0 ; -- j) 
            {
                if(nm[j] >= (1 << j)) 
                {
                    for(int k = lstl[j] + 1 ; k <= n ; ++ k) prel[j][k] = lstid[j];
                    for(int k = lstR[j] ; k <= n ; ++ k) preR[j][k] = lstid[j];
                }
            }
        }
    }
}
inline ll Q(int l,int r)
{
    l ++ , r ++;
    ll ret = 0;int L,R;const int LEN = r - l + 1;
    for(int i = 0 ; i < V && (1 << i) <= LEN ; i += 3) 
    {
        L = sufr[i][l] - 1 , R = min(prel[i][l] , preR[i][r]);
        if(~L && R && L < R) ret += (sr[i][R] - sr[i][L]) + (1ll * (sL[i][R] - sL[i][L])) * l + (so[i][R] - so[i][L]);      
        L = sufl[i][l] - 1 , R = preR[i][r];
        if(~L && R && L < R) ret += ss[i][R] - ss[i][L];
        const int I1 = i + 1 , I2 = i + 2;
        if(I1 < V && (1 << (I1)) <= LEN)
        {
            L = sufr[I1][l] - 1 , R = min(prel[I1][l] , preR[I1][r]);   
            if(~L && R && L < R) ret += (sr[I1][R] - sr[I1][L]) + (1ll * (sL[I1][R] - sL[I1][L])) * l + (so[I1][R] - so[I1][L]);        
            L = sufl[I1][l] - 1 , R = preR[I1][r];
            if(~L && R && L < R) ret += ss[I1][R] - ss[I1][L];
        }
        if(I2 < V && (1 << (I2)) <= LEN)
        {
            L = sufr[I2][l] - 1 , R = min(prel[I2][l] , preR[I2][r]);
            if(~L && R && L < R) ret += (sr[I2][R] - sr[I2][L]) + (1ll * (sL[I2][R] - sL[I2][L])) * l + (so[I2][R] - so[I2][L]);        
            L = sufl[I2][l] - 1 , R = preR[I2][r];
            if(~L && R && L < R) ret += ss[I2][R] - ss[I2][L];
        }
    } 
    return ret;
}
int ctt;
inline void init(int N,int Q,vector<int> A)
{
    n = N , m = Q;
    for(int i = 1 ; i <= n ; i ++) lsh[i] = a[i] = A[i - 1];
    sort(lsh + 1 , lsh + 1 + n);
    ctt = unique(lsh + 1 , lsh + 1 + n) - lsh - 1;int l = 1 , r = ctt , as = 0;
    for(int i = 1 ; i <= n ; i ++) 
    {
        l = 1 , r = ctt , as = 0;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(lsh[mid] >= a[i]) as = mid , r = mid - 1;
            else l = mid + 1;
        }
        a[i] = as;
    }
    Work();
}