Description

Each of Farmer John’s cows initially produces G gallons of milk per day (1≤G≤109). Since the milk output of a cow is known to potentially change over time, Farmer John decides to take periodic measurements of milk output and write these down in a log book. Entries in his log look like this:
35 1234 -2
14 2345 +3
The first entry indicates that on day 35, cow #1234’s milk output was 2 gallons lower than it was when last measured. The next entry indicates that on day 14, cow #2345’s milk output increased by 3 gallons from when it was last measured. Farmer John has only enough time to make at most one measurement on any given day. Unfortunately, he is a bit disorganized, and doesn’t necessarily write down his measurements in chronological order.

To keep his cows motivated, Farmer John proudly displays on the wall of his barn the picture of whichever cow currently has the highest milk output (if several cows tie for the highest milk output, he displays all of their pictures). Please determine the number of days on which Farmer John would have needed to change this display.

Note that Farmer John has a very large herd of cows, so although some of them are noted in his log book as changing their milk production, there are always plenty of other cows around whose milk output level remains at G gallons.
最初，农夫约翰的每头奶牛每天生产G加仑的牛奶(1≤G≤10^9)。由于随着时间的推移，奶牛的产奶量可能会发生变化，农夫约翰决定定期对奶牛的产奶量进行测量，并将其记录在日志中。
他的日志中的记录如下:
35 1234 -2
14 2345 +3
第一个条目表明：在第35天，1234号奶牛的产奶量比上次测量时降低了2加仑。
第二个条目表明：在第14天，2345号奶牛的产奶量比上次测量时增加了3加仑。
农夫约翰只有在任何一天内做最多一次测量的时间（即每天最多做一次测量，但可能不做）。不幸的是，约翰有点杂乱无章，他不一定按照时间顺序记下测量结果。为了保持奶牛的产奶动力，农夫约翰自豪地在谷仓的墙上展示了目前产奶量最高的奶牛的照片（如果有若干头奶牛的产奶量最高，他就会展示所有的图片）。

请求出约翰需要调整所展示的照片的次数。

请注意，农夫约翰有一大群奶牛。所以尽管日志中记录了一些奶牛改变了产奶量，但仍然还有很多奶牛的产奶量保持在G加仑。

Input

The first line of input contains the number of measurements N that Farmer John makes (1≤N≤100,000), followed by G. Each of the next N lines contains one measurement, in the format above, specifying a day (an integer in the range 1…10^6), the integer ID of a cow (in the range 1…10^9), and the change in her milk output since it was last measured (a nonzero integer). Each cow’s milk output will always be in the range 0…10^9.
第一行是两个整数N和G，分别表示测量的次数和初始产奶量。
接下来N行，每行为一次测量。每行三个数：分别表示日期一（在整数1…10^{6范围内），奶牛的编号（在整数1…10}9范围内），该奶牛的产奶量变化值（一个非零整数）。无论如何，每头奶牛的产奶量永远保证在0…10^9范围内。

Output

Please output the number of days on which Farmer John needs to adjust his motivational display.
请输出约翰总共调整所展示的照片的次数。

Sample Input

4 10
7 3 +3
4 2 -1
9 3 -1
1 1 +2

Sample Output

3

Solution

这题比赛时刚开始看起来很简单，不就是把最大值搞来搞去嘛。仔细思考起来，发现了很多不同的情况，如果想得太简单很容易WA。

算法：离散化+线段树

首先我们看到题目的牛的编号特别大，但是由于日志顶多有100000个，所以涉及的奶牛最多有100000头，而且编号并不是太重要我们只需要区分每头奶牛即可，所以我第一时间想到了离散化。

我们研究一下什么时候需要更新照片，这个情况有点复杂而且细节很多（有比我这个简单很多的）：

现在我们在处理一条日志，设$pre$表示这头牛之前的产奶量，$now$表示这头奶牛之后的产奶量。$max$表示这头牛的产奶量改变之前所有牛中最大的产奶量，$maxs$则表示这头牛的产奶量改变之前所有牛中产奶量最大的牛有多少个，$max_2$表示这头牛的产奶量改变之前所有牛中第二大的产奶量。当出现这几种情况时我们需要把答案$+1$

1. $pre<max,now \geq max$
2. $pre=max,now>max,maxs>1$
3. $pre=max,now<max,now \leq max_2$
4. $pre=max,now<max,maxs>1$

维护$max和maxs$我们可以用线段树，但是$max_2$的维护有点难（其他人的一些方法不用），我于是想出了一个很low的做法就是试探，把当前的最大值抹去然后得到的就是第二大的…

CODE

#include<cstdio>
#define max(a,b) (a>b?a:b)
int n,g,lg[100005][3],t[100005][3],mx,a[100005],last,id,tree[400005][2],num,ans,mxs;
void msort(int l,int r,int p){if(l==r) return;int mid=l+r>>1,p1=l,p2=mid+1,p3=l;msort(l,mid,p);msort(mid+1,r,p);while(p1<=mid&&p2<=r)if(lg[p1][p]<lg[p2][p]){t[p3][0]=lg[p1][0];t[p3][1]=lg[p1][1];t[p3][2]=lg[p1][2];p1++;p3++;}else{t[p3][0]=lg[p2][0];t[p3][1]=lg[p2][1];t[p3][2]=lg[p2][2];p2++;p3++;}while(p1<=mid){t[p3][0]=lg[p1][0];t[p3][1]=lg[p1][1];t[p3][2]=lg[p1][2];p1++;p3++;}while(p2<=r){t[p3][0]=lg[p2][0];t[p3][1]=lg[p2][1];t[p3][2]=lg[p2][2];			p2++;p3++;}for(int i=l;i<=r;i++){lg[i][0]=t[i][0];lg[i][1]=t[i][1];lg[i][2]=t[i][2];}
}
void treeModify(int x,int p,int l,int r){if(l==r) tree[p][0]=num,tree[p][1]=1;else{int mid=l+r>>1;if(x<=mid)treeModify(x,2*p,l,mid);elsetreeModify(x,2*p+1,mid+1,r);tree[p][0]=max(tree[2*p][0],tree[2*p+1][0]);if(tree[2*p][0]<tree[2*p+1][0])tree[p][1]=tree[2*p+1][1];if(tree[2*p][0]>tree[2*p+1][0])tree[p][1]=tree[2*p][1];if(tree[2*p][0]==tree[2*p+1][0])tree[p][1]=tree[2*p][1]+tree[2*p+1][1];}
}
int main(){freopen("measurement.in","r",stdin);freopen("measurement.out","w",stdout);scanf("%d%d",&n,&g);for(int i=1;i<=n;i++)scanf("%d%d%d",&lg[i][0],&lg[i][1],&lg[i][2]);msort(1,n,1);last=0;for(int i=1;i<=n;i++)if(lg[i][1]!=last){last=lg[i][1];lg[i][1]=++id;}else lg[i][1]=id;
//	for(int i=1;i<=n;i++)
//		printf("1!%d\n",lg[i][1]);msort(1,n,0);
//	for(int i=1;i<=n;i++)
//		printf("2!%d\n",lg[i][1]);for(int i=1;i<=n;i++){mx=max(tree[1][0],0);if(mx>0)mxs=tree[1][1];else mxs=10;if(a[lg[i][1]]<mx&&a[lg[i][1]]+lg[i][2]>=mx||a[lg[i][1]]==mx&&a[lg[i][1]]+lg[i][2]>mx&&mxs>1){ans++;//	printf("!%d\n",i);}else{if(a[lg[i][1]]==mx&&a[lg[i][1]]+lg[i][2]<mx){if(mxs>1){ans++;//	printf("!%d\n",i);}else{num=0;treeModify(lg[i][1],1,1,n);mx=max(tree[1][0],0);if(a[lg[i][1]]+lg[i][2]<=mx){ans++;//	printf("!%d\n",i);}}}}a[lg[i][1]]+=lg[i][2];num=a[lg[i][1]];treeModify(lg[i][1],1,1,n);}printf("%d",ans);return 0;
}