P8911 [RC-06] Minimum and Maximum

_•́へ•́╬_ · 2022-12-24 23:46:39 · 题解

思路

预处理 b[i][j] 表示区间里所有值都在 i,j 之间的区间有多少个。

回答问题时按下图容斥：大正方形减去黄正方形减去绿正方形再加上黄绿重叠就是红色要求的，白色为 0 所以不考虑。\mathcal O(1) 回答。

预处理 b 很简单。\mathcal O(nV) 预处理。

code

#include<stdio.h>
#include<vector>
#define ull unsigned long long
#define N 100005
#define M 4002
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
inline void read(ull&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int p,q,l[N],r[N];ull xorsum,s,b[M][M];
struct mod
{
    ull b;__int128 m;
    inline mod(const ull&b):b(b),m(((__int128)(1)<<64)/b){}
    inline ull reduce(const ull&a)
    {
        ull q=m*a>>64;
        ull r=a-q*b;
        return r>=b?r-b:r;
    }
}f(2);
inline ull rd(){return s^=s<<13,s^=s>>7,s^=s<<17,s;}
inline void getlr(int&l1,int&r1,int&l2,int&r2)
{
    l1=f.reduce(rd())+p;
    r1=f.reduce(rd())+p;
    l2=f.reduce(rd())+p;
    r2=f.reduce(rd())+p;
    if(l1>r1)l1^=r1^=l1^=r1;
    if(l2>r2)l2^=r2^=l2^=r2;
}
int n,m,a[N];vector<int>c[M];
main()
{
    read(n);read(m);
    for(int i=0;i<n;read(a[i]),c[a[i]].emplace_back(i),++i);
    read(p);read(q);read(s);
    f=mod(q-p+1);
    for(int i=p;i<=q;++i)
    {
        for(int i=0;i<n;l[i]=r[i]=-1,++i);
        for(int j=i;j<=q;++j)
        {
            b[i][j]=b[i][j-1];
            for(int k=0,o;k<c[j].size();++k)
            {
                o=c[j][k];l[o]=r[o]=o;++b[i][j];
                if(o&&~l[o-1])b[i][j]+=o-l[o-1],r[l[o-1]]=o,l[o]=l[o-1];
                if(o<n-1&&~l[o+1])
                    b[i][j]+=(o-l[o]+1ll)*(r[o+1]-o),
                    l[r[o+1]]=l[o],r[l[o]]=r[o+1];
            }
        }
    }//预处理
    for(int i=1,l1,r1,l2,r2;i<=m;++i)
    {
        getlr(l1,r1,l2,r2);
        if(l2>r1)continue;
        xorsum^=(b[l2][r1]-b[l2][l1-1]-b[r2+1][r1]+b[r2+1][l1-1])*i;
    }
    printf("%llu",xorsum);
}