GYM 101350 F. Monkeying Around

When the monkey professor leaves his class for a short time, all the monkeys go bananas. N monkeys are lined up sitting side by side on their chairs. They each have the same joke book. Before the professor returns, M jokes were heard.

Each of the M jokes are said in the order given and have the following properties:

x_i - position of the monkey who said it.

l_i – index of the joke in the book.

k_i – volume the monkey says that joke.

When the monkey at position x_i says the joke l_i, all monkeys at a distance less than or equal to k_i from that monkey (including the monkey who said the joke) will fall off their chairs in laughter if they have never heard the joke l_i before.

If the joke l_i has been heard anytime during the past before, and the monkey hears it again, then he will sit back up in his chair.

A monkey can fall off his chair more than once (every time he hears a new joke), and if he is already on the ground and hears a new joke, he will stay on the ground.

Can you figure out how many monkeys will be in their seats by the time the professor comes back?

Input

The first line of input is T – the number of test cases.

The first line of each test case is N, M (1 ≤ N ≤ 10⁵) (1 ≤ M ≤ 10⁵) – the number of monkeys in the class, and the number of jokes said before the professor returns.

The next M lines contain the description of each joke: x_i, l_i, k_i (1 ≤ x_i ≤ N) (1 ≤ l_i ≤ 10⁵) (0 ≤ k_i ≤ N).

Output

For each test case, output on a line a single integer - the number of monkeys in their seats after all jokes have been said.

Example

Input

Output

【题解】

考虑每一个人站着还是坐下取决于最后一个他听到的笑话
这个可以线段树nlogn求出
然后
我们依次考虑每一个笑话
看他覆盖的区间
此笑话决定的人那个人被覆盖0或>1次则坐下否则站起来
也可以线段树
综上复杂度nlogn

（这是我跟某dalao的聊天记录直接放这里了）

网上有用扫描线做的，不是很明白。。。

待我理解理解

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <algorithm>
  7 #define min(a, b) ((a) < (b) ? (a) : (b))
  8 #define max(a, b) ((a) > (b) ? (a) : (b))
  9 
 10 inline void swap(long long &x, long long &y)
 11 {
 12     long long tmp = x;x = y;y = tmp;
 13 }
 14 
 15 inline void read(long long &x)
 16 {
 17     x = 0;char ch = getchar(), c = ch;
 18     while(ch < '0' || ch > '9')c = ch, ch = getchar();
 19     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
 20     if(c == '-')x = -x;
 21 }
 22 
 23 const long long INF = 0x3f3f3f3f;
 24 const long long MAXN = 1000000 + 10;
 25 
 26 struct Node
 27 {
 28     long long x, l, k, t;
 29 }node[MAXN];
 30 
 31 long long n, m, l[MAXN], r[MAXN], tot, cnt[MAXN];
 32 
 33 
 34 //第一颗线段树，用来维护最晚时间颜色coloe 
 35 long long color[MAXN], num[MAXN];
 36 
 37 void pushup1(long long o, long long l, long long r)
 38 {
 39     long long mid = (l + r) >> 1;
 40     if(!color[o << 1]) color[o << 1] = color[o];
 41     if(!color[o << 1 | 1]) color[o << 1 | 1] = color[o]; 
 42 }
 43 
 44 void modify1(long long ll, long long rr,long long col, long long o = 1, long long l = 1, long long r = n)
 45 {
 46     pushup1(o, l, r);
 47     if(color[o]) return;
 48     if(ll <= l && rr >= r)
 49     {
 50         if(!color[o])color[o] = col;
 51         pushup1(o, l, r);
 52         return;
 53     }
 54     long long mid = (l + r) >> 1;
 55     if(mid >= ll)modify1(ll, rr, col, o << 1, l, mid);
 56     if(mid < rr) modify1(ll, rr, col, o << 1 | 1, mid + 1, r);
 57 } 
 58 
 59 void build1(long long o = 1, long long l = 1, long long r = n)
 60 {
 61     if(l == r)
 62     {
 63         num[l] = color[o];
 64         return;
 65     }
 66     pushup1(o, l, r);
 67     long long mid = (l + r) >> 1;
 68     build1(o << 1, l, mid);
 69     build1(o << 1 | 1, mid + 1, r);
 70 }
 71 
 72 //第二颗线段树，维护特定颜色作用于某个点多少次 
 73 long long data[MAXN], lazy[MAXN];
 74 
 75 void pushup2(long long o, long long l, long long r)
 76 {
 77     if(lazy[o])
 78     {
 79         long long mid = (l + r) >> 1;
 80         lazy[o << 1] += lazy[o];
 81         lazy[o << 1 | 1] += lazy[o];
 82         data[o << 1] += lazy[o] * (mid - l + 1);
 83         data[o << 1 | 1] += lazy[o] * (r - mid);
 84         lazy[o] = 0;
 85     }
 86 }
 87 
 88 void modify2(long long ll, long long rr, long long x, long long o = 1, long long l = 1, long long r = n)
 89 {
 90     pushup2(o, l, r);
 91     if(ll <= l && rr >= r)
 92     {
 93         lazy[o] += x;
 94         data[o] += (r - l + 1) * x;
 95         return;
 96     }
 97     long long mid = (l + r) >> 1;
 98     if(mid >= ll)modify2(ll, rr, x, o << 1, l, mid);
 99     if(mid < rr) modify2(ll, rr, x, o << 1 | 1, mid + 1, r);
100     data[o] = data[o << 1] + data[o << 1 | 1];
101 }
102 
103 long long ask2(long long p, long long o = 1, long long l = 1, long long r = n)
104 {
105     if(l == r && l == p)
106         return data[o];
107     pushup2(o, l, r);
108     long long mid = (l + r) >> 1;
109     if(p <= mid)return ask2(p, o << 1, l, mid);
110     else return ask2(p, o << 1 | 1, mid + 1, r);
111 }
112 
113 long long cmppp(Node a, Node b)
114 {
115     return a.l < b.l; 
116 }
117 
118 long long cmp(Node a, Node b)
119 {
120     return a.t > b.t; 
121 }
122 
123 long long cmpp(long long a, long long b)
124 {
125     return num[a] < num[b];
126 }
127 
128 long long ans, t;
129 
130 int main()
131 {
132 //    freopen("data.txt", "r", stdin);
133 /*long long n, m,cnt[MAXN];
134 */
135     read(t);
136     for(;t;-- t)
137     {
138         ans = 0;tot = 0;
139         memset(color, 0, sizeof(color));
140         memset(num, 0, sizeof(num));
141         memset(data, 0, sizeof(data));
142         memset(lazy, 0, sizeof(lazy));
143         memset(l, 0, sizeof(l));
144         memset(r, 0, sizeof(r));
145         memset(node, 0, sizeof(node));
146         memset(cnt, 0, sizeof(cnt));
147         read(n), read(m);
148         for(register long long i = 1;i <= m;++ i)
149         read(node[i].x), read(node[i].l), read(node[i].k), node[i].t = i;
150         for(register long long i = 1;i <= n;++ i) cnt[i] = i;
151         for(register long long i = m;i >= 1;-- i)
152             modify1(node[i].x - node[i].k, min(n, node[i].x + node[i].k), node[i].l);
153         build1();
154         std::sort(node + 1, node + 1 + m, cmppp);
155         std::sort(cnt + 1, cnt + 1 + n, cmpp);
156         long long now = node[1].l;tot = 1;l[1] = 1;
157         for(register long long i = 2;i <= m;++ i)
158             if(now != node[i].l)r[tot] = i - 1, ++ tot, now = node[i].l, l[tot] = i;
159         r[tot] = m;
160         for(register long long i = 1, p = 1;i <= tot;++ i)
161         {
162             for(register long long j = l[i];j <= r[i];++ j)
163                 modify2(node[j].x - node[j].k, min(n, node[j].x + node[j].k), 1);
164             long long tmp = 0, flag = p;
165             while(num[cnt[p]] == node[l[i]].l)
166             {
167                 long long tmp = ask2(cnt[p]);
168                 if(tmp == 0 || tmp > 1) ++ ans;
169                 ++ p;
170             }
171             for(register long long j = l[i];j <= r[i];++ j)
172                 modify2(node[j].x - node[j].k, min(n, node[j].x + node[j].k), -1);
173         }
174         printf("%I64d
", ans);
175     }
176     return 0;
177 }

GYM 101350F