【单调栈 前缀和 异或】7.21序列求和

还要再细细思考的奇妙思路

题目描述

小A最近喜欢上了关于区间max的问题。她定义一个区间的价值是max(ai)(l<=i<=r)∗(alxoral+1xor...xorar)max(ai)(l<=i<=r)∗(alxoral+1xor...xorar)她想要知道，一个序列所有的连续子序列价值之和是多少。

输入格式

第一行一个正整数n接下来一行n个正整数表示aiai

输出格式

一个正整数表示答案,mod1000000007mod1000000007输出

样例输入

4

1 2 3 4

样例输出

103

数据规模与约定

对于前30%的数据，n<=1000

对于前60%的数据，满足n<=3000

对于前80%的数据，满足n<=50000

对于100%的数据，满足1<=n<=105,ai<=109

---

题目分析

常规思路

见到这题的时候真的是一脸不可做。求和涉及到区间max和区间xor的乘积，整个状态数本身就是$O(n^2)$的，即便写一个转移$O(1)$的暴力也只有60pts。

从问题的表面上来看，状态对答案贡献很难拆开统计。因为如果寻找贡献的共同之处，会发现只有$max(ai)$的地方能够共用。但是还有xor的部分，依然有$O(n^2)$不尽相同的状态。

按位拆分

不过实际上只有我这种不老练选手觉得无从下手。

引用HZQ的话：“碰到位运算+求和的问题一般都会考虑算每一位的贡献”。

这里“每一位”指的是二进制拆分后的每一位。

意识到二进制拆分之后，由于xor的性质，可以对于数位状态取方案数的前缀和。求出前缀和之后，“然后前缀xor和之后问题变成要从左区间选出一个前缀和是0，右区间选出一个前缀和是1或者从左区间选出一个前缀和是1，右区间选出一个前缀和是0的方案数。”。

换而言之就是在二进制上面一位一位算过去：当前位被算到答案里面几次。

思路挺妙的吧，但是好像对于老练的选手来说是道一眼题？……

#include<bits/stdc++.h>
const int MO = 1000000007;
const int maxn = 100035;

int n,a[maxn];
int l[maxn],r[maxn];
int stk[maxn],cnt;
int s[maxn][2];
int ans;

int read()
{
    char ch = getchar();
    int num = 0, fl = 1;
    for (; !isdigit(ch); ch = getchar())
        if (ch=='-') fl = -1;
    for (; isdigit(ch); ch = getchar())
        num = (num<<1)+(num<<3)+ch-48;
    return num*fl;
}
int main()
{
    freopen("magic.in","r",stdin);
    freopen("magic.out","w",stdout);
    n = read();
    for (int i=1; i<=n; i++) a[i] = read();
    cnt = 0;
    for (int i=1; i<=n; i++)　　　　　　//单调栈处理max左边界
    {
        while (cnt&&a[stk[cnt]] < a[i]) cnt--;
        l[i] = stk[cnt];
        stk[++cnt] = i;
    }
    cnt = 0, stk[0] = n+1;
    for (int i=n; i>=1; i--)　　　　　　//单调栈处理max右边界
    {
        while (cnt&&a[stk[cnt]] <= a[i]) cnt--;
        r[i] = stk[cnt];
        stk[++cnt] = i;
    }
    s[1][0] = 1;　　　　　　　　　　　　　//处理数位边界条件
    for (int t=1; t<=MO; t<<=1)　　　　//按位统计贡献
    {
        int tot = 0;
        for (int i=2; i<=n+1; i++)
        {
            tot ^= a[i-1];
            if (tot&t)　　　　　　　　　　//计算方案数前缀和
                s[i][1] = s[i-1][1]+1, s[i][0] = s[i-1][0];
            else s[i][1] = s[i-1][1], s[i][0] = s[i-1][0]+1;
        }
        tot = 0;
        for (int i=1; i<=n; i++)　　　　//按照方案数统计贡献
            tot = (tot+(1ll*(s[r[i]][0]-s[i][0])*(s[i][1]-s[l[i]][1])+1ll*(s[r[i]][1]-s[i][1])*(s[i][0]-s[l[i]][0]))%MO*a[i])%MO;
        ans = (ans+1ll*t*tot)%MO;　　　 //因为贡献的是这位的值，所以要乘t
    }
    printf("%d\n",ans);
    return 0;
}

END