P11283 题解

· · 题解

1. 题目分析

首先简化一下肿胃数的定义，每次任意选连续的三个数，删除其中的中位数，在 n - 3 次操作后，剩下的三个数的中位数的最大值即是肿胃数。
其实我们只需要看有哪些区间中的最大值一定可以作为最终的答案，从中取所有的最大值即可。

判断哪些区间中最大值可以作为最终答案

首先对于总区间，其最大值和最小值都不能作为最终答案，这是显然的。
接下来我们通过手推发现以下区间中的最大值是可以作为最终答案的（我们用 mx 表示总区间最大值，用 dmn 表示在总区间最大值的左边和右边的区间中更大的最小值，用 xmn 表示在总区间最大值左边和右边的区间中更小的最小值）：

证明：
对于两个红色区间中的最大值，因为 dmn 或 xmn 都小于它们，所以如果只在红色区间操作的话，红色区间中除了最大值外的数一定可以作为中位数被全部删完，故红色区间中的最大值可以被保留。
而对于绿色和蓝色区间，因为它们中的最大值又小于 mx，最小值又大于 dmn 或 xmn，所以一定可以全部作为中位数被删去。
接下来就只剩左红色区间最大值、dmn、mx、xmn、右红色区间最大值。现在若我们想要保留左红色区间最大值，那么我们可以先选择右边三个数操作将右红色区间最大值删去，再选择两个最小值和总区间的最大值，将 dmn 删去，最后得到最终答案为左红色区间最大值。保留右红色区间最大值的操作是保留左红色区间最大值的镜像操作。
故两个红色区间的最大值都可以被保留。
证毕。
简单推一下，我们发现可以先将左右红色区间最大值先删去，所以 dmn 也可以被保留，dmn 也可能是肿胃数，大家不要遗漏了。
那么就只有这两个区间的最大值可以被保留吗？答案是否定的。
设在 mx 右边第一个小于 dmn 的数为 x，那么区间 x 到 xmn - 1 中的最大值是可以被保留的。
证明：
因为 x 到 xmn - 1 的右边有蓝色和右红色区间的共同最小值 xmn，所以我们可以在不删去 x 的情况下将此区间中的最大值保留下来。至于在 x 左边的蓝色区间则直接用 dmn 和 mx 全部删掉即可。
我这里用 qmx 表示 x 到 xmn - 1 的最大值（假设最大值不是 x，其实后面你仔细想想如果最大值是 x 也没影响），用 hmx 表示右红色区间最大值，左红色区间最大值很显然可以被删掉就不表示了。
最后情况的处理如下（这里保证 qmx > hmx）：

如果 hmx > qmx 呢，那么请问，如果 hmx > qmx，你为什么要选 qmx 而不选更大的 hmx 呢，对吧。
证毕。
对于其他区间中的数，因为有 dmn 和 xmn，所以无论怎样都不会成为最终答案的，会直接被当成中位数删掉。
至于 dmn 和 xmn 的位置交换之后也一样。
如果没有 dmn 的话，我们可以直接取 x 为 mx - 1 或 mx + 1（根据 xmn 在 mx 的左边还是右边而定）。

2. 题目做法

对于这道题，我们需要求出 dmn、mx、x、xmn 的位置。 

#include<bits/stdc++.h>
#define ll long long
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
using namespace std;
int n,m; 
unsigned seed,A,B,C;
inline unsigned rnd() {
    seed=A*seed*seed+B*seed+C;
    seed=seed^(seed<<27);
    seed=seed^(seed>>19);
    return seed;
}
int l,r;
inline void gen() {
    do {
        l = rnd() % n + 1;
        r = rnd() % n + 1;
    } while (abs(l - r) < 2);
    if(l>r)
        l^=r^=l^=r;
}
const int N=1000010,M=20;
inline unsigned read()
{
    unsigned x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
inline int max(int x,int y)
{
    return x>y?x:y;
}
int a[N];
int w[N],mx[M][N],mn[M][N];
void init()
{
    for(int i=1;i<=n;i++)
        mx[0][i]=mn[0][i]=i;
    for(int i=1;i<=w[n];i++)
    {
        int t1=n-(1<<i)+1,t2=1<<i-1;
        for(int j=1;j<=t1;j++)
        {
            mx[i][j]=a[mx[i-1][j]]>a[mx[i-1][j+t2]]?mx[i-1][j]:mx[i-1][j+t2];
            mn[i][j]=a[mn[i-1][j]]<a[mn[i-1][j+t2]]?mn[i-1][j]:mn[i-1][j+t2];
        }
    }
}
inline int qmx(int l,int r)
{
    if(l>r)
        return 0;
    int t1=w[r-l+1],t2=(1<<t1)-1;
    return a[mx[t1][l]]>a[mx[t1][r-t2]]?mx[t1][l]:mx[t1][r-t2];
}
inline int qmn(int l,int r)
{
    if(l>r)
        return 0;
    int t1=w[r-l+1],t2=(1<<t1)-1;
    return a[mn[t1][l]]<a[mn[t1][r-t2]]?mn[t1][l]:mn[t1][r-t2];
}
stack<int>s;
int l1[N],r1[N];
ll ans;
int main()
{
    n=read(),m=read(),seed=read(),A=read(),B=read(),C=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=2;i<=n;i++)
        w[i]=w[i>>1]+1;
    init();
    a[0]=INT_MAX;
    for(int i=1;i<=n;i++)
    {
        while(!s.empty()&&a[s.top()]>a[i])
            r1[s.top()]=i,s.pop();
        s.push(i);
    }
    while(!s.empty())//记得清空！ 
        s.pop();
    for(int i=n;i;i--)
    {
        while(!s.empty()&&a[s.top()]>a[i])
            l1[s.top()]=i,s.pop();
        s.push(i);
    }
    for(ll i=1;i<=m;i++)
    {
        gen();
        int zmx=qmx(l,r),lmn=qmn(l,zmx-1),rmn=qmn(zmx+1,r);
        if(a[lmn]<a[rmn])
            rmn?lmn=l1[rmn]:lmn=zmx-1;
        else if(a[lmn]>a[rmn])
            lmn?rmn=r1[lmn]:rmn=zmx+1;
        ans^=i*max(lmn?a[qmx(l,lmn)]:0,rmn?a[qmx(rmn,r)]:0);
    }
    printf("%lld",ans);
    return 0;
}