HDU3038 带权并查集

题目连接http://acm.hdu.edu.cn/showproblem.php?pid3038题意给出m个区间范围为1到n每给出一个区间要求判断是否与前面的区间矛盾如果矛盾则不处理最终输出矛盾区间的个数。范围1n2e5 1m40000思路带权并查集考虑区间的几种状态1.区间相离 2.区间相交 3. 区间内含 4.区间相切区间相离不会出现矛盾直接进行区间合并区间相交通过调整还是能满足每个区间和为某个值区间内含两个区间不会相互影响直接合并即可区间相切相切的话能合并则合并如果已经存在共同根节点则查询是否矛盾因为要考虑前一个区间与这个区间的关系所以左端点需要-1在查找的时候对该点到根节点的距离进行更新。如图输入左端点为x右端点为yx-y为zsum为当前点到根节点的距离则合并之后sum[r2]z-sum[y]sum[x]需要注意方向#includebits/stdc.h using namespace std; #define maxn 200005 #define ll long long #define inf 1000000000000000009 #define IOS ios::sync_with_stdio(false) int ff[maxn],sum[maxn]; int find(int x) { if(ff[x]x) return x; int tff[x]; ff[x]find(ff[x]); sum[x]sum[t]; return ff[x]; } int main() { IOS; int n,m; while(cinnm) { for(int i0; in; i) ff[i]i,sum[i]0; int ans0; for(int i0; im; i) { int x,y,z; cinxyz; x--;//区间为左开右闭 int nxfind(x),nyfind(y); if(nxny) { if(sum[y]-sum[x]!z)ans; } else { ff[ny]nx; sum[ny]z-sum[y]sum[x]; } } coutans\n; } return 0; }