题目描述
有一个长度为n的数列，数列中每个数都是[0,p-1]之间的整数。
小明不知道数列中每个数的值，所以向小红做了m次询问。
每次小明会向小红询问一个区间[l,r] 中所有数的和对p取模的结果。
问完所有问题后，小明发现小红的回答中似乎存在矛盾。
现在小明想找到最大的 X，满足小红的前X次回答中不存在矛盾（ X有可能等于m ）。
输入格式
第一行三个整数n,m,p。分别 表示数列长度 ，询问个数 和模数 。
之后m行， 每行三个整数l,r,k ， 表示小红回答区间[l,r] 中所有数的和对 p 取模结果为 k 。
输出格式
输出最大的 ，满足小红的前 次回答中不存在矛盾。
样例
样例输入
10 5 2
1 2 0
3 4 1
5 6 0
1 6 0
7 10 1
样例输出
3
数据范围与提示
分析：
一个数列确定后，各区间的和是确定的。不同区间的和之间是有关系的。
譬如：若数列A的 【1，5】区间和是25，【1，2】区间和是11，那么【3，5】的区间和一定是14，若不是14就矛盾了。
如果两个区间有相同的左边界，那两个区间的差区间的区间和是固定的，可以用这个固定值来判定对这个差区间询问是否矛盾。
A数列区间[L,R] 的和 可以用前缀和的差来表示：preS[R]-preS[L-1]
于是使用前缀和把各区间的之间的关系转化为点与点之间的关系。
一个询问 L,R,K 就表示 preS[R]-preS[L-1]=k 那么preS[R]=preS[L-1]+k
如何判定当前询问的区间是之前某两个区间的差区间呢？
我们用并查集来维护若干连续区间。fa[R]=L-1。
询问1：区间【1，5】和为 25;
含义是:preS[5]-preS[0]=25；
因fa[5]<>fa[0] 所以令 fa[5]=0
询问2：区间【1，2】和为 11;
含义是:preS[2]-preS[0]=11；
因fa[2]<>fa[0] 所以令 fa[2]=0
询问3：区间【3，5】和为 14;
含义是:preS[5]-preS[2]=14；
因fa[5]==fa[2] ==0，区间的两个端点拥有共同的左边界.(说明它是某个两个区间的差区间)
参考代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define re register 4 #define LL long long 5 inline int read(){ 6 int f=1,lzx=0; char c=getchar(); 7 while((c>'9')||(c<'0')){if(c=='-') f=-f; c=getchar();} 8 while(c<='9' && c>='0'){lzx=lzx*10+c-'0';c=getchar();} 9 return lzx*f; 10 }//快读 11 12 const int MAXN = 1e6+10; 13 int n,m,p,fa[MAXN]; 14 int preS[MAXN];//preS[i] 表示a1、a2 ……ai 之和。前缀和。l、r间的区间 和可以用preS[r]-preS[l-1]表示 15 16 inline int find(int x){ 17 if(fa[x]==x) return x; 18 int fax=fa[x]; 19 fa[x]=find(fa[x]); 20 preS[x]=(preS[x]+preS[fax]) %p; 21 return fa[x] ; 22 } 23 24 inline void merge(int a,int b,int c){ 25 int l=find(a),r=find(b); 26 fa[r]=l; 27 preS[r]=(preS[a]+c-preS[b]+p)%p; 28 return ; 29 } 30 int main() { 31 n=read();m=read();p=read(); 32 for(re int i=1;i<=n;i++) fa[i]=i; 33 34 int ans=m; 35 for(int i=1;i<=m;i++){ 36 int a=read()-1,b=read(),c=read(); 37 int l=find(a),r=find(b); 38 if(l!=r) merge(a,b,c); 39 else{ 40 if((preS[a]+c)%p!=(preS[b]%p)) { 41 ans=i-1; 42 break; 43 } 44 } 45 } 46 printf("%d\n",ans); 47 return 0; 48 }