$$\color{Purple}{kuangbin题解目录}$$
描述
有一个长度为 $N$ 的整数序列。
下面会按顺序给出 $M$ 个对该序列的描述,每个描述给定三个整数 $l,r,s$,表示该序列的第 $l$ 个元素至第 $r$ 个元素相加之和为 $s$。
对于每个描述,你需要判断该描述是否会与前面提到的描述发生冲突,如果发生冲突,则认为该描述是错误的。
如果一个描述是错误的,则在对后续描述进行判断时,应当将其忽略。
请你计算一共有多少个描述是错误的。
输入格式
第一行包含两个整数 $N,M$。
接下来 $M$ 行,每行包含三个整数 $l,r,s$,表示一个描述。
输出格式
一个整数,表示错误描述的数量。
数据范围
$1 \\le N \\le 2 \\times 10^5$,
$1 \\le M \\le 40000$,
$1 \\le l \\le r \\le N$,
$1 \\le s \\le 2 \\times 10^9$,
保证任何子序列的和都在 $\[1,2 \\times 10^9\]$ 范围内。
输入样例:
10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1
输出样例:
1
思路
- 利用
权值并查集
解决.带权并查集的核心能力就是维护多个元素之间的连通
以及偏移关系
,甚至可以维护多个偏移关系
.而偏移量可以理解为当前结点
到根结点
的距离之和
.其核心运算是向量运算.- 首先,利用
前缀和
的思想,即区间$[l,r]$的区间和
通常表示为$s[r]-s[l-1]$,故此处取的时候也应取$l-1$,而不是$l$
- 其次,设$roota$是$a$的根结点,$rootb$是$b$的根结点,$sum$是$a\to b$的关系值,$d[x]$是某结点$x$到其根结点的关系值(如距离).
- 当
roota!=rootb
时,将$roota$与$rootb$合并(即$roota$的父结点是$rootb$)
- 令$dist[a\to b]$表示$a$到$b$的距离
- 此时$dist[roota\to rootb]=d[roota]$,同时$dist[b\to rootb]=d[b]$,$dist[a\to roota]=d[a]$,已知$dist[a\to roota]+dist[roota \to rootb]=d[a]+d[roota]=dist[a\to b]+dist[b\to rootb]=sum+d[b]$,故合并后$d[rooota]=sum+d[b]-d[a]$,即每次合并时更新$d[roota]$和$fa[roota]$
- 当
roota==rootb
时,已知$dist[a\to roota]=d[a]=dist[a\to b]+dist[b \to rootb]=sum’+d[b]$,此时只需判断当前的$sum$是否等于$sum’=dist[a\to roota]-dist[b\to rootb]=d[a]-d[b]$.
代码
// Problem: 多少个答案是错误的
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4289/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-27 20:33:47
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 200010
using namespace std;
typedef long long ll;
int n,m;
int fa[MAXN],d[MAXN];
int find(int x)
{
if(fa[x]!=x)
{
int root=find(fa[x]);
d[x]+=d[fa[x]];
fa[x]=root;
}
return fa[x];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
while(cin >> n >> m)
{
for(int i=0;i<=n;i++)
fa[i]=i,d[i]=0;
int res=0;
for(int i=1;i<=m;i++)
{
int l,r,sum;
cin >> l >> r >> sum;
//类似于前缀和思想sum=s[r]-s[l-1]
int fx=find(l-1),fy=find(r);
if(fx!=fy)
{
fa[fx]=fy;
d[fx]=sum+d[r]-d[l-1];
}
else if(fx==fy)
{
if(d[l-1]-d[r]!=sum)
res++;
}
}
cout << res << endl;
}
return 0;
}
读完题一脸懵,看到你这一下悟了ORZ ORZ
%%%