题目
link
求偶数子序列
满足
的个数。
分析
首先, 我们先把每一对a[i] + a[j]存起来, 这样就可以把题目的偶数个条件无视了。
设 T[i,j] = a[i] + a[j]; 因为我们是要求序列个数, 所以对于 [i,j]区间, 我们
要找出 [i,j] 内有多少对满足 T[x,y] < T[i,j] 的。
把 (i,j)想成坐标系的点, 那么上面求的就是 平面矩形 {[i,i],[j,j]} 中有多少点。
利用前缀和 和矩形相减就可以快速得出了。所以用二维的树状数组维护就有了。
Code
取余是一个特殊值, 可以直接用unsigned更加简便。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1LL<<32;
const int maxn = 500 + 31;
struct Point {
int x, y;
LL sum;
Point(int _x, int _y, LL _s):\
x(_x),y(_y),sum(_s){}
bool operator < (const Point a) const {
if(sum == a.sum) {
return x == a.x ? y < a.y : x < a.x;
} else return sum < a.sum;
}
};
vector<Point> Tmp;
LL Num[maxn][maxn];
LL A[maxn], B[maxn];
///BIT
int lowbit(int x) { return x&(-x); }
LL Sum(int x, int y) {
LL ret = 0;
int xx = x;
while(xx > 0) {
int yy = y;
while(yy > 0)
{
ret = (ret + Num[xx][yy]) % MOD;
yy -= lowbit(yy);
}
xx -= lowbit(xx);
}
return ret;
}
void Add(int x, int y, LL Val) {
int xx = x;
while(xx < maxn)
{
int yy = y;
while(yy < maxn)
{
Num[xx][yy] = (Num[xx][yy] + Val) % MOD;
yy += lowbit(yy);
}
xx += lowbit(xx);
}
}
int main() {
//cout << MOD <<endl;
int t, n;
scanf("%d",&t);
for(int kase = 1; kase <= t; ++kase)
{
Tmp.clear();
memset(Num,0,sizeof(Num));
scanf("%d",&n);
for(int i = 0; i < n; ++i)
scanf("%lld",A+i);
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
{
Tmp.push_back(Point(i+1,j+1,(A[i]+A[j])%MOD));
}
sort(Tmp.begin(), Tmp.end());
LL Ans = 0;
for(int i = 0; i < Tmp.size(); ++i)
{
Point t = Tmp[i];
LL ss = (Sum(t.y-1,t.y-1) - Sum(t.x,t.y-1) + MOD) % MOD;
ss = (ss - Sum(t.y-1,t.x) + Sum(t.x,t.x) + MOD) % MOD;
ss = (ss+1) % MOD;
Ans = (Ans + ss) % MOD;
Add(t.x,t.y,ss);
}
//Ans %= MOD;
printf("Case %d: %lld\n",kase, Ans);
}
return 0;
}