#pragma region header #include // ソート, 二分探索, 最大・最小 #include // 固定長配列(C++11~) #include // ビット演算・フラグ管理 #include // デバッグ用の assert #include // 時間計測(C++11~) #include // int64_t, PRIu64 などのフォーマット指定 #include // INT_MAX, INT_MIN など #include // sqrt, pow, sin, cos など #include // FFT(高速フーリエ変換)など #include // printf, scanf(Cスタイル) #include // memset, memcpy #include // 両端キュー(deque) #include // 比較関数 (greater, less) #include // 小数点表示の調整(setprecision など) #include // 標準入出力 #include // イテレータ操作 #include // numeric_limits #include // std::map(連想配列) #include // gcd, lcm, accumulate など #include // 優先度付きキュー (priority_queue) #include // 乱数生成(乱択アルゴリズムなど) #include // std::set(集合) #include // 文字列ストリーム(stringstream) #include // スタック(LIFO) #include // 文字列操作 #include // tuple, tie #include // 型特性(C++11~) #include // ハッシュマップ(unordered_map) #include // ハッシュセット(unordered_set) #include // pair, swap, move など #include // 動的配列(最重要) using namespace std; struct Init{Init(){std::cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20) << fixed;}}init; using ll = long long; using ull = unsigned long long; using ld = long double; #define all(x) begin((x)), end((x)) #define pb push_back #define mp make_pair #define mt make_tuple #define uq(v) v.erase(unique(begin(v), end(v)), end(v)) #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _rep1(n) for(int i=0;i=0;i--) #define _rrep2(i,n) for(int i=(n)-1;i>=0;i--) #define _rrep3(i,a,b) for(int i=(b)-1;i>=(a);i--) #define _rrep4(i,a,b,c) for(int i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__) template using pq = priority_queue; template using pq_g = priority_queue, greater>; template bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;} template bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;} template auto min(const T& a){ return *min_element(all(a)); } template auto max(const T& a){ return *max_element(all(a)); } constexpr ll INF = (1LL << 62) - (1LL << 31); constexpr int inf = (1 << 30); constexpr ld EPS = 1e-9; constexpr ld PI = std::acos(ld(-1)); constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1 ,0, -1, 1, -1, 1, -1}; #pragma endregion header template struct RangeSet{ set> st; T TINF; RangeSet(){ TINF=numeric_limits::max()/2; st.emplace(TINF,TINF); st.emplace(-TINF,-TINF); } // [l,r] covered? bool covered(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); return ite->first<=l and r<=ite->second; } bool covered(T x){ return covered(x,x); } // [l, r]がカバーされているなら,その区間を返す. されていないなら[-TINF,-TINF]を返す pair covered_by(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return *ite; return make_pair(-TINF,-TINF); } pair covered_by(T x){ return covered_by(x,x); } // insert[l,r], 増加量を返す T insert(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return T(0); T sum_erased=T(0); if(ite->first<=l and l<=ite->second+1){ l=ite->first; sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); }else ite=next(ite); while(r>ite->second){ sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); } if(ite->first-1<=r and r<=ite->second){ sum_erased+=ite->second-ite->first+1; r=ite->second; st.erase(ite); } st.emplace(l,r); return r-l+1-sum_erased; } T insert(T x){ return insert(x,x); } // erase [l,r], 減少量を返す T erase(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second){ // 完全に1つの区間に包含されている if(ite->firstfirst,l-1); if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); return r-l+1; } T ret=T(0); if(ite->first<=l and l<=ite->second){ ret+=ite->second-l+1;// 消えた if(ite->firstfirst,l-1); ite=st.erase(ite);// 次へ }else ite=next(ite); while(ite->second<=r){ ret+=ite->second-ite->first+1; ite=st.erase(ite); } // 右端が区間の間にあるか if(ite->first<=r and r<=ite->second){ ret+=r-ite->first+1; if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); } return ret; } T erase(T x){ return erase(x,x); } // number of range int size(){ return (int)st.size()-2; } // mex [x,~) int mex(T x=0){ auto ite=prev(st.lower_bound({x+1,x+1})); if(ite->first<=x and x<=ite->second) return ite->second+1; else return x; } void output(){ cout<<"RangeSet : "; for(auto &p:st){ if(p.first==-TINF or p.second==TINF) continue; cout<<"["<> D; RangeSet st; int Q; cin >> Q; ll ans = 0; rep(Q){ ll A, B; cin >> A >> B; st.insert(A, B); auto c = st.covered_by(A, B); chmax(ans, c.second - c.first + 1); cout << ans << "\n"; } }