数列询问

题目描述

有一个长度为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 }