风间
分析:
暴力
实现:
int a[N], b[N];
void solve()
{
res = 0;
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%lld", &b[i]);
for (int i = 1; i <= n; i++)
{
if (abs(a[i] - b[i]) & 1)
{
puts("-1");
return;
}
res += abs(a[i] - b[i]) / 2;
int t = a[i] - b[i];
if (i == n && t != 0)
{
puts("-1");
return;
}
if (t == 0)
continue;
else if (t > 0)
a[i + 1] += t;
else if (t < 0)
a[i + 1] += t;
}
printf("%lld\n", res);
}
梦迹
分析:
快速求出数组中满足 x + num ≤ w 的num的个数,树状数组维护前缀和
(数组中有0,加偏移量处理)
实现:
int tr[N], a[N];
int lowbit(int x)
{
return x & -x;
}
void update(int x, int c) // 位置x加c
{
for (int i = x; i <= N; i += lowbit(i))
tr[i] += c;
}
int query(int x) // 返回前x个数的和
{
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
void solve()
{
cin >> n >> q >> w;
w += 2;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i]++;
update(a[i], 1);
res += query(w - a[i]);
}
for (int i = 1, pos, x; i <= q; i++)
{
cin >> pos >> x;
x++;
int num = a[pos];
res -= query(w - num);
update(a[pos], -1);
a[pos] = x;
update(x, 1);
res += query(w - x);
cout << res << endl;
}
}
标签:练习赛,int,res,pos,update,牛客,108,num,query
From: https://www.cnblogs.com/Aidan347/p/17255384.html