『序列莫队 dp预处理』

忘是亡心i 2021-12-21 21:11 247阅读 0赞

--------------------

# 序列 #

### Description ###

给定长度为n的序列：a1,a2,…,an，记为a\[1:n\]。

类似地，a\[l:r\]（1≤l≤r≤N）是指序列：al,al+1,…,ar-1,ar。若1≤l≤s≤t≤r≤n，则称a\[s:t\]是a\[l:r\]的子序列。

现在有q个询问，每个询问给定两个数l和r，1≤l≤r≤n，求a\[l:r\]的不同子序列的最小值之和。

例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a\[1:3\]有6个子序列a\[1:1\],a\[2:2\],a\[3:3\],a\[1:2\],a\[2:3\],a\[1:3\]，这6个子序列的最小值之和为5+2+4+2+2+2=17。

### Input Format ###

输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。

接下来一行，包含n个整数，以空格隔开,第i个整数为ai，即序列第i个元素的值。

接下来q行，每行包含两个整数l和r，代表一次询问。

### Output Format ###

对于每次询问，输出一行，代表询问的答案。

### Sample Input ###

5 5
    5 2 4 1 3 
    1 5 
    1 3 
    2 4 
    3 5 
    2 5

### Sample Output ###

28 
    17 
    11 
    11 
    17

### 解析 ###

回答若干个静态的区间询问，思路是莫队。

假设我们已经得到了区间\\(\[l,r\]\\)的答案，直接考虑如何转移到\\(\[l,r+1\]\\)。显然，我们只需要考虑包含\\(r+1\\)这一个点的子序列\\(\[l,r+1\],\[l+1,r+1\],...,\[r+1,r+1\]\\)即可。要求的是最小值之和，我们就设\\(\[l,r+1\]\\)在\\(a\\)序列上的区间最小值为\\(a\_p\\)，位置是\\(p\\)，那么所有左端点在\\(\[l,p\]\\)之间的区间的答案就都是\\(a\_p\\)，总共的贡献为\\(a\_p\*(p-l+1)\\)，这个问题显然可以用\\(ST\\)表解决。

那么剩下的那些区间我们考虑用\\(dp\\)来计算答案。设\\(f\[i\]\[j\]\\)代表右端点为\\(j\\)，左端点在\\(\[i,j\]\\)之间的答案之和，那么我们要求的就是\\(f\[p+1\]\[r+1\]\\)。记录下\\(prep\_i\\)代表\\(a\\)序列中\\(a\_i\\)左边第一个比他小的元素的位置(单调栈解决)，状态转移方程就是：\\\[f\[i\]\[j\]=f\[i\]\[prep\_j\]+a\_j\*(j-prep\_j)\\\]。

发现状态转移方程与\\(i\\)无关，直接将第一维舍去，那么\\(f\[j\]\\)的定义就是右端点为\\(j\\)的所有区间的答案之和。继续考虑原问题，发现必然存在一个点\\(x\\)满足\\(prep\_x=p\\)，\\(f\[r+1\]=a\_\{r+1\}\*(r+1-prep\_\{r+1\})+...+a\_x\*(x-p)+f\[p\]\\)，那么我们原来要求的\\(f\[p+1\]\[r+1\]\\)其实可以表示为\\(f\[r+1\]-f\[p\]\\)，然后预处理出\\(f\\)数组，就可在莫队当中\\(O(1)\\)转移了。

当然，我们还需要处理出反方向的\\(f\\)数组，以便莫队向左转移。如果是删除操作的话，就减去加入这个点的时候带来的贡献即可。

\\(Code:\\)

#include <bits/stdc++.h>
    using namespace std;
    const int N = 100200 , MaxlogN = 25 , INF = 2e9;
    int n,m,a[N],size;
    int Min[N][MaxlogN],Log2[N],Pow2[MaxlogN];
    int prep[N],next[N],Stack[N],top;
    long long ans[N],fl[N],fr[N],tot;
    struct Query{int l,r,id;}q[N];
    inline void init(void)
    {
        Pow2[0] = 1 , a[0] = a[n+1] = INF;
        for (int i=1;i<=MaxlogN-2;i++) 
            Pow2[i] = Pow2[i-1] << 1;
        for (int i=2;i<=n;i++)
            Log2[i] = Log2[i>>1] + 1;
        for (int i=1;i<=n;i++)
            Min[i][0] = i;
        for (int k=1;k<=Log2[n];k++)
            for (int i=1;i+Pow2[k-1]-1<=n;i++)
                if ( a[ Min[i][k-1] ] < a[ Min[i+Pow2[k-1]][k-1] ] )
                    Min[i][k] = Min[i][k-1];
                else Min[i][k] = Min[i+Pow2[k-1]][k-1];
        top = 0;
        for (int i=1;i<=n;i++)
        {
            while ( top && a[Stack[top]] > a[i] ) 
                next[ Stack[top--] ] = i;
            prep[i] = Stack[top] ; Stack[++top] = i;
        }
        while ( top ) 
        {
            prep[ Stack[top] ] = Stack[top-1];
            next[ Stack[top] ] = n+1;
            top--;
        }
    }
    inline int query(int l,int r)
    {
        int k = Log2[r-l+1];
        if ( a[ Min[l][k] ] < a[ Min[r-Pow2[k]+1][k] ] )
            return Min[l][k];
        else return Min[r-Pow2[k]+1][k];
    }
    inline void input(void)
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (int i=1;i<=m;i++)
            scanf("%d%d",&q[i].l,&q[i].r) , q[i].id = i;
    }
    inline void dp(void)
    {
        for (int i=1;i<=n;i++)
            fr[i] = fr[prep[i]] + 1LL * a[i] * (i-prep[i]);
        for (int i=n;i>=1;i--)
            fl[i] = fl[next[i]] + 1LL * a[i] * (next[i]-i);
    }
    inline bool compare(Query p1,Query p2)
    {
        if ( (p1.l/size) ^ (p2.l/size) )
            return p1.l < p2.l ;
        else if ( (p1.l/size) & 1 )
            return p1.r < p2.r ;
        else return p1.r > p2.r ;
    }
    inline void insert1(int l,int r)
    {
        int p = query(l,r);
        tot += ( 1LL * a[p] * (p-l+1) + fr[r] - fr[p] ); 
    }
    inline void insert2(int l,int r)
    {
        int p = query(l,r);
        tot += ( 1LL * a[p] * (r-p+1) + fl[l] - fl[p] );
    }
    inline void remove1(int l,int r)
    {
        int p = query(l,r);
        tot -= ( 1LL * a[p] * (p-l+1) + fr[r] - fr[p] );
    }
    inline void remove2(int l,int r)
    {
        int p = query(l,r);
        tot -= ( 1LL * a[p] * (r-p+1) + fl[l] - fl[p] );
    }
    inline void CaptainMo(void)
    {
        double val = sqrt(1.0*m*2/3);
        if ( val > n || val < 500 ) size = sqrt(n);
        else size = n * 1.0 / val;
        sort( q+1 , q+m+1 , compare );
        int l = 1 , r = 0;
        for (int i=1;i<=m;i++)
        {
            int ql = q[i].l , qr = q[i].r;
            while ( l > ql ) insert2(--l,r);
            while ( r < qr ) insert1(l,++r);
            while ( l < ql ) remove2(l++,r);
            while ( r > qr ) remove1(l,r--);
            ans[ q[i].id ] = tot;
        }
    }
    int main(void)
    {
        input();
        init();
        dp();
        CaptainMo();
        for (int i=1;i<=m;i++)
            printf("%lld\n",ans[i]);
        return 0;
    }

--------------------

转载于:https://www.cnblogs.com/Parsnip/p/10902338.html