把输出的false打成flase了…一直没注意到…
先将区间和转成前缀和 那么就知道了若干条形如 Sr−Sl−1=C 的信息 能判断出账本是假的当且仅当通过已知的信息得到的 Sr−Sl−1≠C 于是维护一个带权并查集，当 r 和l−1在同一个集合里的时候，利用维护的和根的差算出 Sr−Sl−1 判断是否和 C <script type="math/tex" id="MathJax-Element-205">C</script>相同
code：
#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long using namespace std; inline void read(int &x) { char c; int f=1; while(!((c=getchar())>='0'&&c<='9')) if(c=='-') f=-1; x=c-'0'; while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0'; x*=f; } const int maxn = 510000; const int maxm = 510000; const int maxb = 21; int n,m; int fa[maxn],fc[maxn]; int find_(const int x) { if(fa[x]==x) return x; int t=fa[x],re=find_(fa[x]); fc[x]+=fc[t]; return fa[x]=re; } int main() { int t; read(t); while(t--) { read(n); read(m); for(int i=0;i<=n;i++) fa[i]=i,fc[i]=0; bool flag=true; while(m--) { int x,y,c; read(x); read(y); read(c); x--; // y-x=c; int t1=find_(x), t2=find_(y); if(t1!=t2) { //y-t2=fcy -> t2-x=c-fcy fa[t2]=x; fc[t2]=c-fc[y]; } else //y-t=fcy,x-t=fcx -> y-x=fcy-fcx { if(fc[y]-fc[x]!=c) flag=false; } } if(flag) printf("true\n"); else printf("false\n"); } return 0; }