启发式分治

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

玛卡巴卡正在玩一个游戏，在他面前有若干堆石子，他可以选择一对相邻的石子堆，并且分别在这两堆石子中取走一个石子。如果一个石子堆被取完，那么原本与之相邻的石子堆在这堆石子取完后相邻。

现在有 nnn 个石子堆，玛卡巴卡想知道有多少对 l,r (l≤r)l,r (lleq r)l,r (l≤r)，满足将编号为 lll 到 rrr 的石子堆单独取出进行游戏时他能取完所有的石子。

第一行一个数 n (1≤n≤105)n (1leq nleq 10^5)n (1≤n≤105)。

接下来一行 nnn 个正整数 ai (1≤ai≤109)a_i (1leq a_ileq 10^9)ai​ (1≤ai​≤109)，表示每堆石子的石子数。

一个整数，表示答案。

#include
using namespace std;
#define int long long
const int maxn=1e5+5;
int a[maxn];int st[maxn][40];int lg[maxn];
int sum[maxn];int odd[maxn];int even[maxn];
int get(int l,int r)
{
    int t=lg[r-l+1];
    return a[st[l][t]]=num)
                {
                    loc=m;
                    rr=m-1;
                }
                else ll=m+1;
            }
            //cout<=pos+1)
    solve(pos+1,r);
}
signed main()
{
    int n;cin>>n;
    lg[1]=0;
    for(int i=2;i>a[i];
        sum[i]=sum[i-1]+a[i];
        st[i][0]=i;
    }
    for(int i=1;i<=n;i++)
    {
        odd[i]=odd[i-1],even[i]=even[i-1];
        if(sum[i]%2==1) odd[i]=odd[i-1]+1;
        else even[i]=even[i-1]+1;
    }
    for(int j=1;(1<