#include <bits/stdc++.h> #define ll long long #define sz(x) (int)x.size() using namespace std; void update(ll l, ll r, ll li, ll ri, ll i, vector<ll> &T, vector<ll> &lazy) { if(li == l && ri == r && l == r) { T[i]++; return; } T[2*i] += lazy[i]; T[2*i + 1] += lazy[i]; lazy[2*i] += lazy[i]; lazy[2*i + 1] += lazy[i]; lazy[i] = 0; if(li == l && ri == r) { //if(li == 4 && ri == 7) {cout << "AAAAAAA"; //if(i == 5) cout << "CAEHUO " << T[i] << '\n';} T[i]++; lazy[i]++; return; } ll m = (li + ri) / 2; if(l <= m) { update(l, min(r, m), li, m, 2*i, T, lazy); } if(m + 1 <= r) { update(max(l, m + 1), r, m + 1, ri, 2*i + 1, T, lazy); } T[i] = T[2*i] + T[2*i + 1]; } ll query(ll x, ll li, ll ri, ll i, vector<ll> &T, vector<ll> &lazy) { if(li == ri && li == x && ri == x) { return T[i]; } T[2*i] += lazy[i]; T[2*i + 1] += lazy[i]; lazy[2*i] += lazy[i]; lazy[2*i + 1] += lazy[i]; lazy[i] = 0; ll m = (li + ri) / 2; if(x <= m) { return query(x, li, m, 2*i, T, lazy); } else { return query(x, m + 1, ri, 2*i + 1, T, lazy); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, m; cin >> n >> m; ll s = 1; while(s < n) s *= 2; vector<vector<ll> > T(3, vector<ll>(2*s + 10, 0)); vector<vector<ll> > lazy(3, vector<ll>(2*s + 10, 0)); for(int i = 0; i < m; i++) { ll l, r, k; cin >> l >> r >> k; l--;r--;k--; update(l, r, 0, s - 1, 1, T[k], lazy[k]); //cout << "--------------" << '\n'; //for(int i = 0; i < n; i++) cout << query(i, 0, s - 1, 1, T[0], lazy[0]) << ' ' << query(i, 0, s - 1, 1, T[1], lazy[1]) << ' ' << query(i, 0, s - 1, 1, T[2], lazy[2]) << '\n'; //cout << "--------------" << '\n'; } ll ans = 0; for(int i = 0; i < n; i++) { if(query(i, 0, s - 1, 1, T[0], lazy[0]) > 0 && query(i, 0, s - 1, 1, T[1], lazy[1]) > 0 && query(i, 0, s - 1, 1, T[2], lazy[2]) == 0) ans++; } cout << ans << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #include <bits/stdc++.h> #define ll long long #define sz(x) (int)x.size() using namespace std; void update(ll l, ll r, ll li, ll ri, ll i, vector<ll> &T, vector<ll> &lazy) { if(li == l && ri == r && l == r) { T[i]++; return; } T[2*i] += lazy[i]; T[2*i + 1] += lazy[i]; lazy[2*i] += lazy[i]; lazy[2*i + 1] += lazy[i]; lazy[i] = 0; if(li == l && ri == r) { //if(li == 4 && ri == 7) {cout << "AAAAAAA"; //if(i == 5) cout << "CAEHUO " << T[i] << '\n';} T[i]++; lazy[i]++; return; } ll m = (li + ri) / 2; if(l <= m) { update(l, min(r, m), li, m, 2*i, T, lazy); } if(m + 1 <= r) { update(max(l, m + 1), r, m + 1, ri, 2*i + 1, T, lazy); } T[i] = T[2*i] + T[2*i + 1]; } ll query(ll x, ll li, ll ri, ll i, vector<ll> &T, vector<ll> &lazy) { if(li == ri && li == x && ri == x) { return T[i]; } T[2*i] += lazy[i]; T[2*i + 1] += lazy[i]; lazy[2*i] += lazy[i]; lazy[2*i + 1] += lazy[i]; lazy[i] = 0; ll m = (li + ri) / 2; if(x <= m) { return query(x, li, m, 2*i, T, lazy); } else { return query(x, m + 1, ri, 2*i + 1, T, lazy); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, m; cin >> n >> m; ll s = 1; while(s < n) s *= 2; vector<vector<ll> > T(3, vector<ll>(2*s + 10, 0)); vector<vector<ll> > lazy(3, vector<ll>(2*s + 10, 0)); for(int i = 0; i < m; i++) { ll l, r, k; cin >> l >> r >> k; l--;r--;k--; update(l, r, 0, s - 1, 1, T[k], lazy[k]); //cout << "--------------" << '\n'; //for(int i = 0; i < n; i++) cout << query(i, 0, s - 1, 1, T[0], lazy[0]) << ' ' << query(i, 0, s - 1, 1, T[1], lazy[1]) << ' ' << query(i, 0, s - 1, 1, T[2], lazy[2]) << '\n'; //cout << "--------------" << '\n'; } ll ans = 0; for(int i = 0; i < n; i++) { if(query(i, 0, s - 1, 1, T[0], lazy[0]) > 0 && query(i, 0, s - 1, 1, T[1], lazy[1]) > 0 && query(i, 0, s - 1, 1, T[2], lazy[2]) == 0) ans++; } cout << ans << '\n'; } |