CF2227G （2000）树状数组+条件转化

原题链接

题目不再赘述

首先，我们要判断什么样的数组是好数组。好数组通过操作可以最后变为1个且每次操作将3个数缩为1个数，因此得出第一个条件好数组的长度一定是奇数。

再者，有一个需要记忆的二级结论：将a_i替换成a_i-1+a_i+1-a_i(>0）之后[i-1,i+1]的交替和没有改变，仍为a_i-1-a_i+a_i+1.进一步会发现，经过无限次操作后如果只剩一个数，那个数的大小就等于原数组的交替和，所以好数组的条件是：1.区间长度为奇数 2.区间交替和>0

首先，我们定义p数组=a[1]-a[2]+a[3]-a[4]....之后对于区间[l,r]的区间，交替和=(-1)^{^l-1}(p[r]-p[l-1]);

之后由于区间长度为奇数，l和r肯定同奇偶，l-1和r肯定不同奇偶。因此要枚举r或者l-1，且时间复杂度要小于n

此时我们想到了树状数组，那么我们要如何用树状数组实现实时查询比p[r]小或者大的l-1的个数呢？

我们可以想到，离散化p数组的值，然后每枚举一个r就按奇偶性让对应树状数组里面对应离散下标的位置++，而比p[r]小只需要去查询在对应树状数组中[1,id]的总个数即可（因为r+1往后的下标值还没加入树状数组当中）

因此代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=2e5+5;
struct BIT{int n;vector<int> c;void init(int x){n=x+1,c.clear();for(int i=0;i<=n;i++)c.push_back(0);}void add(int id){while(id<n)c[id]++,id+=id&-id;}int sum1(int r){int ans=0;while(r>0)ans+=c[r],r-=r&-r;return ans;}int sum(int l,int r){if(l>r)return 0;return sum1(r)-sum1(l-1);}
}tji,tou;void solve(){int n;cin>>n;vector<int> a(n+1),p(n+1,0);for(int i=1;i<=n;i++){cin>>a[i];if(i&1)p[i]=p[i-1]+a[i];else p[i]=p[i-1]-a[i];}vector<int> b=p;sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());auto id=[&](int x){return lower_bound(b.begin(),b.end(),x)-b.begin()+1;};tji.init(b.size()),tou.init(b.size());tou.add(id(0));int ans=0;for(int i=1;i<=n;i++){int x=id(p[i]);if(i&1){ans+=tou.sum1(x-1);tji.add(x);}else{ans+=tji.sum(x+1,b.size());tou.add(x);}}cout<<ans<<'\n';}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;cin>>_;while(_--)solve();
}
/*
4
3
10 20 10
5
1 1 1 1 1
4
5 1 5 1
1
100*/