解题思路

这道题目要求我们检查一系列区间和查询操作是否与之前的操作冲突。如果冲突，则输出正确的区间和；否则，接受该操作。关键在于如何高效地维护和查询这些区间和的关系。

方法思路

1. 离散化处理：由于区间的端点可能非常大（达到$10^9$），直接处理会消耗过多内存。因此，首先将所有出现过的区间端点进行离散化处理，将它们映射到一个连续的范围内。
2. 并查集维护区间和关系：使用并查集（Disjoint Set Union, DSU）来维护各个离散化后的点之间的和关系。每个节点存储到其父节点的相对差值（即部分和）。通过路径压缩和合并操作，可以高效地查询和更新区间和。
3. 查询与合并：
   • 查询：对于每个操作sum(i, j) = v，检查离散化后的区间[i-1, j]的和是否与之前记录的一致。如果父节点相同，则比较计算的和与给定的v是否一致；如果不一致，则输出正确的和。
   • 合并：如果父节点不同，则合并两个集合，并更新相对差值以保证区间和的正确性。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const int MAXN=110000;
int a[MAXN],b[MAXN],p[MAXN];
long long c[MAXN],d[MAXN];
vector<int> points; // Renamed from 'hash' to 'points'

long long findp(int x) {
    if(p[x]==-1) {
        return x;
    }
    int ret=findp(p[x]);
    d[x]+=d[p[x]];
    return p[x]=ret;
}

int main() {
    int m;
    while(scanf("%d",&m)==1) {
        points.clear();
        memset(p,-1,sizeof(p));
        memset(d,0,sizeof(d));
        for(int i=0; i<m; i++) {
            scanf("%d%d%lld",&a[i],&b[i],&c[i]);
            if(a[i]>b[i]) {
                swap(a[i],b[i]);
            }
            points.push_back(a[i]-1);
            points.push_back(b[i]);
        }
        sort(points.begin(),points.end());
        points.erase(unique(points.begin(),points.end()),points.end());
        for(int i=0; i<m; i++) {
            a[i]=lower_bound(points.begin(),points.end(),a[i]-1)-points.begin();
            b[i]=lower_bound(points.begin(),points.end(),b[i])-points.begin();
            int px=findp(a[i]);
            int py=findp(b[i]);
            if(px==py) {
                if(d[b[i]]-d[a[i]]==c[i]) {
                    puts("Accept");
                } else {
                    printf("Bug Detected %lld\n",d[b[i]]-d[a[i]]);
                }
            } else {
                if(px>py) {
                    swap(a[i],b[i]);
                    swap(px,py);
                    c[i]=-c[i];
                }
                d[py]=d[a[i]]+c[i]-d[b[i]];
                p[py]=px;
                puts("Accept");
            }
        }
    }
    return 0;
}