消灭劳嗝

ZnPdCo · 2024-08-09 07:15:52 · 题解

发现 |S_x\cup S_y|=|S_x|+|S_y|-|S_x\cap S_y|，前面两项容易通过前缀和计算，所以我们只需要求出最后一项就好了。发现 |S_x\cap S_y|=\min_{i=x}^{y-1} |S_i|-1，证明不难理解，就是从后往前做单调栈时，单调栈内元素最少的一刻就是两集合的交。

所以现在我们的问题就变成了求：

定义 L_i=\sum_{1\le x < y\le i} \min_{i=x}^{y-1}|S_i|，R_i=\sum_{i\le x < y\le n} \min_{i=x}^{y-1}|S_i|。

考虑怎么快速计算上述的值，可以考虑每加入一个数对答案的贡献，发现 L_i 比 L_{i-1} 多了一个以 i 为右端点的贡献，分为对比他大的区间的贡献与比他小的区间的贡献，用单调栈即可维护。

根据容斥，上述式子的值为 L_r+R_l-L_n。

综上，总复杂度 O(n)。

#include <bits/stdc++.h>
#define N 10000010
#define P 998244353
#define ll long long
using namespace std;
namespace IO{
    const int sz=1<<22;
    char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
    inline char gc(){
        return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
    }
    template<class T> void read(T& x){
        x=0; char c=gc();
        for(;c<'0'||c>'9';c=gc());
        for(;c>='0'&&c<='9';c=gc())
            x=x*10+(c-'0');
    }
    inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
    inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
    template<class T> void write(T x,char c='\n'){
        if(x<0) pc('-'), x=-x;
        if(x==0) pc('0'); int t=0;
        for(;x;x/=10) p[++t]=x%10+'0';
        for(;t;--t) pc(p[t]); pc(c);
    }
    struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;
int n, c, q, a[N], nxt[N], f[N], sta[N], top;
ll L[N], R[N], sum, s[N], X;
int main() {
    read(n), read(X), read(c);
    for(int i = 1; i <= n; i ++) {
        a[i] = i;
    }
    for(int i = 1; i <= c; i ++) {
        int l, r;
        l = (X * (X ^ i)) % n + 1;
        r = (X ^ (1ll * i * i)) % n + 1;
        swap(a[l], a[r]);
    }
    top = 0, sta[top] = n + 1;
    for(int i = n; i >= 1; i --) {
        while(top && a[sta[top]] < a[i]) top --;
        nxt[i] = sta[top];
        sta[++ top] = i;
    }
    for(int i = n; i >= 1; i --)
        f[i] = 1 + f[nxt[i]];
    for(int i = 1; i <= n; i ++)
        s[i] = (s[i - 1] + f[i]) % P;
    top = 0, sta[top] = 0;
    for(int i = 1; i < n; i ++) {
        while(top && f[sta[top]] > f[i]) {
            sum -= 1ll * (f[sta[top]] - 1) * (sta[top] - sta[top - 1]) % P;
            sum = (sum % P + P) % P;
            top --;
        }
        sum += 1ll * (f[i] - 1) * (i - sta[top]) % P;
        sum = (sum % P + P) % P;
        sta[++ top] = i;
        L[i] = (L[i - 1] + sum) % P;
    }
    top = 0, sum = 0, sta[top] = n;
    for(int i = n - 1; i >= 1; i --) {
        while(top && f[sta[top]] > f[i]) {
            sum -= 1ll * (f[sta[top]] - 1) * (sta[top - 1] - sta[top]) % P;
            top --;
        }
        sum += 1ll * (f[i] - 1) * (sta[top] - i) % P;
        sum = (sum % P + P) % P;
        sta[++ top] = i;
        R[i] = (R[i + 1] + sum) % P;
    }
    read(q);
    ll res = 0;
    for(ll i = 1; i <= q; i ++) {
        int l, r;
        l = min((X * i + (X ^ (X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
        r = max((X * i + (X ^ (X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
        ll ans = (s[r] - s[l - 1]) * (r - l) % P - 
            s[l - 1] * (n - r) % P - 
            (s[n] - s[r]) * (l - 1) % P - 
            (L[r - 1] + R[l] - L[n - 1]) % P +
        (s[r] - s[l - 1]) % P;
        ans = (ans % P + P) % P;
        res ^= ans;
    }
    write(res);
}