自动搬运

查看原文

来自洛谷，原作者为

	Heptagon18 Where there is a will, there is a way.

搬运于2025-08-24 22:50:20，当前版本为作者最后更新于2023-08-21 19:33:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Description

原题链接。

更好的浏览体验。

---

Solution

Part 0 - 一些提示

“对 $4294967296$ 取模”本质上其实就是 $\text {unsigned int}$ 自然溢出。

“以...为峰的序列”看上去性质很难发掘，尝试将它分解成多个简单条件？

操作没有修改数之间的相对关系。预处理的可能性？

然后，就没有然后了。

Part 0.5 - 写在前面

主要算法：方案数 DP，树状数组优化前缀和。

感谢 @youyou2007 @英雄趁年少6 帮忙验题！

Part 1 - 发掘题面信息

题面首先给出了“峰”的定义。

考虑将“峰”的定义拆解为“以 $a_s$ 结尾的严格单调递增序列”与“以 $a_s$ 开头的严格单调递减序列”，$a_s$ 处的答案即为这两种序列方案数的乘积。

以“以 $a_s$ 结尾的严格单调递增序列”为例，考虑 DP 转移。

设 $pre_s$ 表示以 $a_s$ 结尾的严格单调递增序列

容易得到：$pre_s=\sum\limits_{i=1}^{s-1} pre_i \;(a_s>a_i)$。

直接使用该方程转移复杂度是 $O(n^2)$ 的。

基于此，我们可以对于每次询问暴力求解，总时间复杂度 $O(qn^2)$，获得 $10\%$ 的分数。

考虑优化。

观察条件“$a_s>a_i$”，发现其本质是一个值域上的前缀和。

于是可以用树状数组优化。

严格单调递减序列同理。

至此，我们完成了预处理的全部工作，时间复杂度 $O(n\log a_{\max}))$。

Part 2 - 观察操作性质

经过预处理后，我们得到了 $pre$ 数组（存严格单调递增序列方案数）与 $nxt$ 数组（存严格单调递减序列方案数），考虑一次交换操作对两个数组的影响。

我们先考虑对 $pre$ 数组的影响。

（这里的影响都是考虑不相等的两个数，两个相等的数交换后对答案没有产生任何影响。)

观察交换操作中的两个数，可以发现，较小数的 $pre$ 并没有改变。

感性理解一下，无论较大数处于什么位置，较小数的 $pre$ 都不可能由较大数的 $pre$ 转移而来。

现在我们知道了较小数的 $pre$ 不变，较大数的 $pre$ 就好处理了。

如果 $a_k<a_{k+1}$，那么在预处理时，$pre_{k+1}$ 由 $pre_k$ 转移过来了，而交换后不能转移，需要将 $pre_{k+1}$ 减去 $pre_k$。

$a_k>a_{k+1}$ 同理，将 $pre_k$ 加上 $pre_{k+1}$ 即可。

考虑剩下的数。

发现在交换过程中仅有较大数的 $pre$ 发生变化，则仅有从较大数转移 $pre$ 值的数会发生变化，即为 $i>k+1,a_i>\max(a_k,a_{k+1})$ 的所有数。

$nxt$ 修改同理。

于是可以用预处理的思路暴力修改 + 转移，时间复杂度 $O(qn)$，可以通过 $30\%$ 的数据。

发现值域较小，可以在值域上修改 + 转移，时间复杂度 $O(qa_{\max})$，跑不满，可以通过 $60\%$ 的数据。

Part 3 - 优化

观察最后一个部分分，发现 $q$ 达到了 $10^6$ 的级别， $O(q\times???)$ 必然会超时。

考虑在询问前预处理出全部答案。

回顾操作性质，发现转移仅和两个要素有关：元素值、位置。

进一步发现位置仅分为两部分：$[1,k-1]$ 和 $[k+2,n]$。

使用扫描线的思想，动态维护这两个区间。

接着思考，在区间中需要维护什么信息。

还是以 $pre$ 数组为例，考虑一次交换操作的贡献。

首先考虑其它数不互相影响的情况。

设较大数的 $pre$ 最后加上了 $g_1$，$nxt$ 最后加上了 $g_2$，满足 $i\in[k+2,n],a_i>\max(a_k,a_{k+1})$ 的集合为 $f\;(|f|=m)$，满足 $i\in[1,k-1],a_i>\max(a_k,a_{k+1})$ 的集合为 $p\;(|p|=o)$。

则 $g_1$ 最终对答案的贡献为 $g_1\times nxt_{f_1}+g_1\times nxt_{f_2}+\cdots+g_1\times nxt_{f_m} = g_1\times(nxt_{f_1}+nxt_{f_2}+\cdots+nxt_{f_m}) = g_1\times \sum\limits_{i=1}^m nxt_{f_i}$。

再结合上 $f_i>\max(a_k,a_{k+1})$，容易发现，维护的是 $[k+2,n]$ 范围内值域上的 $nxt$ 后缀和。

同理可得，$nxt$ 数组需要维护的是 $[1,k-1]$ 范围内值域上的 $pre$ 后缀和。

接着考虑其它数相互影响的情况。

发现刚才的做法有个致命的缺陷：由于区间内仍然存在大小关系，一个数减去的不一定是 $g$，而可能是 $2g,3g$ 等。

举个例子，假如当前 $[k+2,n]$ 区间内的数为 $[5,8,3,9]$，当前的 $\max(a_k,a_{k+1})=4$。

则因为 $5>4$，$5$ 的 $pre$ 需要减去 $g$。

又因为 $8>5,4$，$8$ 的 $pre$ 需要减去 $2g$。

以此类推。

观察可以得知，在每个数加进区间时，比它大的所有数均需要多减去一个 $g$。

那么我们定义带权权值数组 $prey$ 和 $nxty$，$prey_d,nxty_d$ 分别表示当取 $a_d$ 这个数时，总共在两个区间内分别需要减的 $pre,nxt$ 之和。

可以发现，带权权值对应的即为两个区间内值域上的 $pre$ 后缀和与 $nxt$ 后缀和。

那么总共需要减去的就是 $g_1\times\sum\limits_{i=1}^m nxty_{f_i}+g_2\times\sum\limits_{j=1}^o prey_{p_j}$。

用树状数组动态更新即可。

时间复杂度 $O(n\log a_{\max})$，总时间复杂度 $O(n\log a_{\max}+q)$，可以通过本题。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline ll read()
{
    ll x=0,r=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') r=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*r;
}

void write(long long t)
{
    if(t<0)
    {
        putchar('-');
        t=-t;
    }
    if(t>=10)write(t/10);
    putchar(t%10+'0');
}

long long n,q;
long long a[1000005];
unsigned int tree[10005][15];
unsigned int pre[1000005];
unsigned int nxt[1000005];
unsigned int prey[1000005];
unsigned int nxty[1000005];
unsigned int del[1000005];
unsigned int ans[1000005];

long long lowbit(long long t)
{
    return t&(-t);
}

void update(long long x,long long k,long long n,long long op)
{
    for(long long i=x;i<=n;i+=lowbit(i)) 
        tree[i][op]+=k;
}

unsigned int query(long long t,long long k)
{
    long long ans=0;
    for(long long i=t;i>=1;i-=lowbit(i)) ans+=tree[i][k];
    return ans;
}

int Answer(unsigned int ans)
{
    unsigned int BASE=998244353ll*ans+ans*ans+ans/9991+ans%2159;
    BASE^=9810;
    BASE^=51971;
    BASE=BASE>>7;
    BASE=BASE<<11;
    BASE^=751669;
    BASE^=23465695622566ll;
    return BASE%(n-1)+1;
}

signed main()
{
    n=read();
    q=read();
    long long maxx=0;
    for(long long i=1;i<=n;i++)
    {
        a[i]=read();
        maxx=max(maxx,a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        pre[i]=1;
        pre[i]+=query(a[i]-1,0);
        update(a[i],pre[i],maxx,0);
    }
    unsigned int prey_cnt=0;
    unsigned int nxty_cnt=0;
    unsigned int cnt=0;
    for(int i=n;i>=1;i--)
    {
        nxt[i]=1;
        nxt[i]+=query(a[i]-1,1);
        update(a[i],nxt[i],maxx,1);
        cnt+=nxt[i]*pre[i];
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]=cnt;
        prey[i]=prey_cnt-query(a[i],2)+pre[i];
        prey_cnt+=prey[i];
        update(a[i],prey[i],maxx,2);
    }
    for(int i=n;i>=1;i--)
    {
        nxty[i]=nxty_cnt-query(a[i],3)+nxt[i];
        nxty_cnt+=nxty[i];
        update(a[i],nxty[i],maxx,3);
    }
    for(int i=1;i<n;i++)
    {
        if(a[i]<a[i+1])
        {
            del[i]=-query(a[i]-1,4)-1;
            ans[i]+=del[i]*(nxty[i+1]-nxt[i+1]);
        }
        else if(a[i]>a[i+1])
        {
            del[i]=query(a[i+1]-1,4)+1;
            ans[i]+=del[i]*(nxty[i]-nxt[i]);
        }
        update(a[i],pre[i],maxx,4);
    }
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]<a[i+1])
        {
            unsigned int op=query(a[i]-1,5)+1;
            ans[i]+=op*(prey[i+1]-pre[i+1]);
            ans[i]-=pre[i+1]*nxt[i+1]-(pre[i+1]+del[i])*(nxt[i+1]+op);
        }
        else if(a[i]>a[i+1])
        {
            unsigned int op=-query(a[i+1]-1,5)-1;
            ans[i]+=op*(prey[i]-pre[i]);
            ans[i]-=pre[i]*nxt[i]-(pre[i]+del[i])*(nxt[i]+op);
        }
        update(a[i+1],nxt[i+1],maxx,5);
    }
    int k;
    k=read();
    for(int i=1;i<=q;i++)
    {
        write(ans[k]);
        putchar('\n');
        k=Answer(ans[k]);
    }
    return 0;
}