HDU 5530：Pipes Selection

题意：

给定长度为\(L\)，元素总和为\(S\)的非负整数序列\(A\)，对于每一个\(1 \leq i \leq S\)，求出：所有满足\(\sum_{j=l}^rA_j=i\)的二元组\((l,r)\)排序后的中位数。

二元组的比较方式：先比较\(l\)，小的在先；\(l\)相同比较\(r\)，小的在先。

\(1 \leq L , S \leq 30000\)

思路：

易见可以把二元组\((l,r)\)看作一个左端点落在\(l-1\)与\(l\)之间，右端点落在\(r\)与\(r+1\)之间的区间。

那么若连续\(c\)个零的下标为\(i\)到\(i+c-1\)，则一个区间的左/右端点落在\(i-1\)与\(i\)之间，或\(i\)与\(i+1\)之间，……，或\(i+c-1\)到\(i+c\)之间，不影响其总和。那么，我们可以把这\(c+1\)个落点合并为一个（不妨用\(i-1\)和\(i\)之间的那个来代表），并给它标上权值\(c+1\)，意味着如果一个区间选取它为端点，就会产生另外\(c\)个与之相同的区间。

同样的，我们把一个非零元素\(a\)拆成\(a-1\)个权值为0的落点和随后紧邻的1个权值为1的落点。可以认为，任何区间都不能以权值为0的落点作为端点。

来自不同元素的落点，按照原先元素的顺序排列。

这样做的意义在于，经过变换之后，区间\([i,j]\)（其中\(i\)和\(j\)是变换之后落点的编号）在序列\(A\)的总和为\(j-i\)，且共有\(m_i \cdot m_j\)个与之完全相同的区间，其中\(m_i\)是落点\(i\)的权值。

hint：对于零元素落点的合并操作，注意到\(i-1\)与\(i\)之间的落点，实际上就是前一个非零元素拆成的最后一个落点，所以合并时直接执行\(m_{last}\)+=\(c\)即可。

看到这里，有没有嗅到一股法法塔的气息！！！

对\(m\)序列求得卷积序列\(cnt\)，满足：

\[cnt_i=\sum_{j-k=i}m_j \cdot m_k
\]

而\(cnt_i\)就是\(A\)数组中总和为\(i\)的连续子序列数量！

这样可以求出对每一个\(i\)，二元组\((l,r)\)的数量，进而可以知道（对每一个\(i\)）二元组排序后中位数的下标。

知道下标之后，就是常规操作了。注意到如果把\(m\)与自己的一个前缀做卷积，得到的\(cnt_i\)，就是\(A\)中总和为\(i\)，且左端点下标不超过\(k\)的区间数量，这里的\(k\)是与\(m\)前缀的长度正相关的一个值。

对于每一个\(i\)，可以对所求二元组的左端点二分答案，并每次用前缀卷积得到的\(cnt_i\)判断。但是直接暴力做会超时，整体二分又用不了（单轮check的复杂度只与\(L\)相关，不满足使用整体二分的条件），所以考虑分块。

把\(m\)序列分成大小为\(\sqrt[2]{L \cdot \log L}\)的块，并通过\(O(\sqrt[2]{\frac{L}{\log L}})\)次卷积，确定对每一个\(i\)，其所求二元组的\(l\)在哪一块里。

最后对每一个\(i\)，在块内暴力找到准确的左端点和右端点即可。记得把\(m\)序列中的下标映射回到\(A\)序列中去。

复杂度\(O(L \cdot \sqrt[2]{L \cdot \log L})\)。

代码：

#include<iostream>

#include<cstdio>

#include<ctime>

#include<vector>

#include<cstring>

using namespace std;

#define iinf 2000000000

#define linf 1000000000000000000LL

#define ulinf 10000000000000000000ull

#define MOD1 1000000007LL

#define mpr make_pair

typedef long long LL;

typedef unsigned long long ULL;

typedef unsigned long UL;

typedef unsigned short US;

typedef pair < int , int > pii;

clock_t __stt;

inline void TStart(){__stt=clock();}

inline void TReport(){printf("\nCurrent Case Taken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}

template < typename T > T MIN(T a,T b){return a<b?a:b;}

template < typename T > T MAX(T a,T b){return a>b?a:b;}

template < typename T > T ABS(T a){return a>0?a:(-a);}

template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}

template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}

const LL MODG=998244353,G=3;

int powM(int num,int pw,LL moD=MODG){

    int ret=1;

    while(pw){

        if(pw&1) ret=((LL)ret*(LL)num)%moD;

        num=((LL)num*(LL)num)%moD;

        pw>>=1;

    }

    return (int)ret;

}

int n,s,rk[30005],lv[30005],a[30005],v[60005],ln,ld[60005],pcnt[60005],cnt[140005],A[140005],B[140005];

int SZ,SZINV,BUC;

void ntt(int *a,int l,bool r){

    int i,j=l/2,k;

    for(i=1;i<l;++i){

        if(i<j) swap(a[i],a[j]);

        for(k=l/2;j&k;k>>=1) j^=k;

        j^=k;

    }

    for(i=1;(1<<i)<=l;++i){

        int cl=(1<<i);

        int w=powM(G,(MODG-1)/cl);

        if(r) w=powM(w,MODG-2);

        for(j=0;j*cl<l;++j){

            int cur=1;

            for(k=0;k<(cl>>1);k++){

                int v1=a[j*cl+k],v2=((LL)a[j*cl+k+(cl>>1)]*(LL)cur)%MODG;

                a[j*cl+k]=(v1+v2)%MODG;

                a[j*cl+k+(cl>>1)]=(v1-v2+MODG)%MODG;

                cur=((LL)cur*(LL)w)%(LL)MODG;

            }

        }

    }

}

void getcnt(int pre){

    int i,j,k;

    memset(A,0,sizeof(int)*(SZ+5));

    memset(B,0,sizeof(int)*(SZ+5));

    memset(cnt,0,sizeof(int)*(SZ+5));

    for(i=0;i<ln;++i){

        A[i]=v[i];

    }

    ntt(A,SZ,0);

    for(i=0;i<pre;++i){

        B[ln-1-i]=v[i];

    }

    ntt(B,SZ,0);

    for(i=0;i<SZ;++i){

        A[i]=((LL)A[i]*(LL)B[i])%MODG;

    }

    ntt(A,SZ,1);

    for(i=0;i<SZ;++i){

        if(i+1-ln>=0){

            cnt[i+1-ln]=((LL)A[i]*(LL)SZINV)%MODG;

        }

    }

}

void solve(){

    // inputting start

    // 数据结构记得初始化！ n，m别写反！

    int i,j,k;

    scanf("%d",&n);

    s=0;

    for(i=0;i<n;++i){

        scanf("%d",a+i);

        s+=a[i];

    }

    #ifdef LOCAL

        TStart();

    #endif

    // calculation start

    // 数据结构记得初始化！ n，m别写反！

    ln=v[0]=1;

    ld[0]=-1;

    for(i=0;i<n;++i){

        if(a[i]>0){

            for(j=0;j<a[i]-1;++j){

                ld[ln]=i;

                v[ln++]=0;

            }

            ld[ln]=i;

            v[ln++]=1;

        }

        else{

            for(j=i;j<n && a[j]==0;++j) ++v[ln-1];

            i=j-1;

        }

    }

    for(BUC=2;BUC*BUC<ln*60;++BUC);

    for(SZ=4;SZ<ln*2;SZ<<=1);

    SZINV=powM(SZ,MODG-2);

    getcnt(ln);

    for(i=1;i<=s;++i){

        rk[i]=(cnt[i]+1)/2-1;

        lv[j]=-1;

    }

    for(i=0;i<=ln;i+=BUC){

        getcnt(i);

        for(j=1;j<=s;++j){

            if(cnt[j]<=rk[j])

                lv[j]=i;

            else if(lv[j]==i-BUC)

                rk[j]-=pcnt[j];

        }

        memcpy(pcnt,cnt,sizeof(int)*(s+3));

    }

    LL resL=0,resR=0;

    for(i=s;i>=1;--i){

        while(rk[i]>=v[lv[i]+i]*v[lv[i]]){

            rk[i]-=v[lv[i]+i]*v[lv[i]];

            ++lv[i];

        }

        if(rk[i]>=0) resL+=(LL)(ld[lv[i]]+2+rk[i]/v[lv[i]+i]);

        if(rk[i]>=0) resR+=(LL)(ld[lv[i]+i]+rk[i]%v[lv[i]+i]+1);

        resL=(resL*233LL)%MOD1;

        resR=(resR*233LL)%MOD1;

    }

    printf("%d %d\n",(int)resL,(int)resR);

    #ifdef LOCAL

        TReport();

    #endif

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        solve();

    }

    return 0;

}

巴特西

HDU 5530：Pipes Selection

题意：

思路：

代码：

最新文章

热门文章