题意
给定一个平面\((n,m)\)，处理如下操作：
- OPT = 1：使点\((x,y)\)处使横纵行全部0/1取反。
- OPT = 2：矩形\((x_1,y_1,x_2,y_2)\)内的和。
Tag Archives: 树状数组
[Fortuna OJ]Mar 4th – Group A 解题报告
A – 漆黑列车载运数个谎言
这道题应该是并查集域的裸题，不讲。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= 2 * n; i++)
fa[i] = i;
while (m--)
{
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if (opt == 0)
unite(x, y), unite(x + n, y + n);
else if (opt == 1 || opt == 2)
unite(x, y + n), unite(x + n, y);
else if (find(x) == find(y) || find(x + n) == find(y + n))
puts("1");
else
puts("0");
}
return 0;
}
[Fortuna OJ]绕圈跑题解
思路
好神仙啊。
这道题思路非常的巧妙。答案很容易可以知道，为
\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*C*speed[i]}{maxSpeed*C} \rfloor \]
化简得：
\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*speed[i]}{maxSpeed} \rfloor \]
如果我们统计括号内的实数集和的话，会出现一些只有在计算机上才会出现的恶心误差，所以我们可以考虑分开取整再求和。这里有一个小技巧，对于两个数而言：
\[ \lfloor a – b \rfloor = \begin{cases} \lfloor a \rfloor – \lfloor b \rfloor, a的小数部分 \leq b的小数部分 \\ \lfloor a \rfloor – \lfloor b \rfloor – 1, a的小数部分>b的小数部分 \end{cases} \]
在判断小数部分的时候，我们可以把小数部分之间的大小关系转化为余数之间的大小关系进行判断，答案默认减掉那个取整的1，然后用树状数组补全那些被误删的取整项。
代码
// FOJ2930.cpp
#include <bits/stdc++.h>
#define ll long long
#define lowbit(p) (p & -p)
using namespace std;
const ll MAX_N = 1e5 + 200;
ll n, l, c, spd[MAX_N], mxspd, f[MAX_N], tree[1000100];
void update(int num)
{
num++;
while (num <= mxspd)
tree[num] += 1, num += lowbit(num);
}
ll sum(int num)
{
num++;
ll ans = 0;
while (num)
ans += tree[num], num -= lowbit(num);
return ans;
}
int main()
{
scanf("%lld%lld%lld", &n, &l, &c);
for (int i = 1; i <= n; i++)
scanf("%lld", &spd[i]);
sort(spd + 1, spd + 1 + n), mxspd = spd[n];
for (int i = 1; i <= n; i++)
f[i] = (l * spd[i]) / mxspd;
update((l * spd[1]) % mxspd);
ll prefix = f[1], ans = 0;
for (int i = 2; i <= n; i++)
{
prefix += f[i];
ans += i * f[i] - prefix - i;
update((l * spd[i]) % mxspd);
ans += sum((l * spd[i]) % mxspd);
}
printf("%lld", ans);
return 0;
}