分析:
注意序列中的数可以是负数
d[i]表示以第i个数结尾的前缀和
实质上,d[i]是i到p[i]的距离,或者称之为关系
问题关键,如何
判断矛盾
?我最开始不知道,思维很混乱@_@
每次合并区间(两个点)都是在维护这些点的关系!!!
所谓关系就是,这些点的前缀和
例如集合中有点t1、t2、t3...tn
,那么这n个点相互之间的前缀关系
都已经被确定
由
前缀和
的思想
我们每次维护一个区间[l, r]
的时候,其实是维护d[l - 1]
和d[r]
的关系
对于枚举到的一个区间[l, r]
:
如果区间没有被确定关系,那么我们合并这个区间(合并两个点,结果是用来维护这个区间的前缀关系)
如果区间已经被确定了关系,那么我们判断当前所给的区间和s
是否满足
我们前面维护的前缀关系
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, m;
int p[N], d[N];
int find(int x) // 维护每个前缀和的关系
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) p[i] = i;
int ans = 0;
while (m --)
{
int l, r;
LL s;
scanf("%d%d%lld", &l, &r, &c);
int pl = find(l - 1), pr = find(r);
if (pl != pr)
{
p[pl] = pr;
// l-1和r的前缀关系,注意d[i]实质上是i到p[i]的距离/关系,画画图就可以理解
d[pl] = c + d[r] - d[l - 1];
}
else
{ // 不满足已经存在的前缀关系
if (d[pa] != c + d[b] - d[a - 1])
ans ++;
}
}
cout << ans << endl;
return 0;
}