$Milk\ Measurement$

题目链接：jzoj 6660 / luogu 4087

题目

最初，农夫约翰的每头奶牛每天生产$G$加仑的牛奶$(1≤G≤10^9)$。由于随着时间的推移，奶牛的产奶量可能会发生变化，农夫约翰决定定期对奶牛的产奶量进行测量，并将其记录在日志中。
他的日志中的记录如下:
$35\ 1234\ -2$
$14\ 2345\ +3$
第一个条目表明：在第$35$天，$1234$号奶牛的产奶量比上次测量时降低了$2$加仑。
第二个条目表明：在第$14$天，$2345$号奶牛的产奶量比上次测量时增加了$3$加仑。
农夫约翰只有在任何一天内做最多一次测量的时间（即每天最多做一次测量，但可能不做）。不幸的是，约翰有点杂乱无章，他不一定按照时间顺序记下测量结果。为了保持奶牛的产奶动力，农夫约翰自豪地在谷仓的墙上展示了目前产奶量最高的奶牛的照片（如果有若干头奶牛的产奶量最高，他就会展示所有的图片）。

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

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

输入

第一行是两个整数$N$和$G$，分别表示测量的次数和初始产奶量。
接下来$N$行，每行为一次测量。每行三个数：分别表示日期一（在整数$1...10^6$范围内），奶牛的编号（在整数$1...10^9$范围内），该奶牛的产奶量变化值（一个非负数）。无论如何，每头奶牛的产奶量永远保证在$0...10^9$范围
内。

输出

请输出约翰总共调整所展示的照片的次数。

样例输入

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

样例输出

3

思路

这道题可以用线段树做，但是我用的是模拟。
就是维护第一大和第二大（这样才能省时间），具体怎么搞看代码吧。
（代码中的找新的第二名就是直接暴力找）

代码

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;struct node {int day, num, add;
}a[1000001];
int n, G, cnt = 100, cow[1000001], maxn, maxx, sec, sex, ans;
map<int, int>mapp;bool cmp(node x, node y) {return x.day < y.day;
}void findsec() {//暴力找到第二名sec = -2147483647;sex = 0;for (int j = 1; j <= cnt; j++) {if (cow[j] != maxn && cow[j] > sec) {sec = cow[j];sex = 1;}else if (cow[j] == sec) sex++;}
}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", &a[i].day, &a[i].num, &a[i].add);//读入}sort(a + 1, a + n + 1, cmp);//按时间排序for (int i = 1; i <= n; i++) {if (!mapp[a[i].num]) mapp[a[i].num] = ++cnt;//离散化if (cow[mapp[a[i].num]] == maxn) {//原来是最大cow[mapp[a[i].num]] += a[i].add;//数量改变if (a[i].add > 0) {//产奶量增加if (maxx != 1) {//原来第一名不止一个sec = maxn;sex = maxx - 1;maxx = 1;ans++;}maxn = cow[mapp[a[i].num]];}else {//产奶量减少if (maxx != 1) {//原来第一名不止一个maxx--;ans++;if (cow[mapp[a[i].num]] > sec) {//还比原来的第一名大sec = cow[mapp[a[i].num]];sex = 1;}else if (cow[mapp[a[i].num]] == sec) sex++;//跟原来的第二名一样大}else {//原来第一名只有一个if(cow[mapp[a[i].num]] > sec) maxn = cow[mapp[a[i].num]];//还是比第二名高else if(cow[mapp[a[i].num]] == sec) {//跟第二名一样高（第二名变成了第一名，要重新找第二名）maxn = sec;maxx = sex + 1;findsec();ans++;}else {//比第二名低maxn = sec;maxx = sex;findsec();ans++;}}}}else if (cow[mapp[a[i].num]] == sec) {//原来是第二名cow[mapp[a[i].num]] += a[i].add;//加h值if(a[i].add < 0) {//产量减少sex--;if(!sex) findsec();//要重新去找第二名}else {//产量增加if (cow[mapp[a[i].num]] == maxn) {//现在跟第一名一样多sex--;maxx++;ans++;if (!sex) findsec();}else if (cow[mapp[a[i].num]] > maxn) {//超过了第一名sec = cow[mapp[a[i].num]];sex = 1;swap(maxn, sec);swap(maxx, sex);ans++;}else {//没有超过第一名（那肯定是第二名）sec = cow[mapp[a[i].num]];sex = 1;}}}else {//原来不是第一也不是第二cow[mapp[a[i].num]] += a[i].add;//加值if (cow[mapp[a[i].num]] == maxn) {//已经是和第一同样大了 maxx++;ans++;}else if (cow[mapp[a[i].num]] == sec) {//已经和第二同样大了sex++;}else if (cow[mapp[a[i].num]] > maxn) {//已经是最大的了sec = cow[mapp[a[i].num]];sex = 1;swap(maxn, sec);swap(maxx, sex);ans++;}else if (cow[mapp[a[i].num]] > sec){//比第二大，但是比第一小sec = cow[mapp[a[i].num]];sex = 1;}}}printf("%d", ans);//输出//	fclose(stdin);
//	fclose(stdout);return 0;
}