UVALive 6911 Double Swords （Set，贪心，求区间交集）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int N = 1e5+5;
const int M = 1e6+6;
set<int>st;
set<int>:: iterator it;
map<int,int> id;
struct Edge {
    int l,r,A,ok;
    void Set(int x,int y,int a) {
        l = x;
        r = y;
        A = a;
        ok = 0;
    }
} e[N];
int sum[M];
bool cmp(Edge a,Edge b) {
    if(a.l != b.l) return a.l < b.l;
    return a.r < b.r;
}
int main() {
//    freopen("F.in.cpp","r",stdin);
    int T,n,a,b,c,ans,ca=0,Max,Min,cnt;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        st.clear();
        id.clear();
        Max = -1;
        Min = 1e8;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d",&a,&b,&c);
            id[a] = i;
            e[i].Set(b,c,a);
            st.insert(a);
            Max = max(max(Max,a),e[i].r);
            Min = min(min(Min,a),e[i].l);
        }
        cnt = 0;
        for(int i = Min-1; i <= Max; i++) {
            if(id[i]) cnt++;
            sum[i] = cnt;
        }
        ans = st.size();
//        printf("ans1 = %d\n",ans);
        for(int i = 1; i <= n; i++) {
            if(sum[e[i].r] - sum[e[i].l-1] == 1) {
                it = st.lower_bound(e[i].l);
                if(*it != e[i].A) e[i].ok = 1;
            }
            if(sum[e[i].r] - sum[e[i].l-1] > 1) e[i].ok = 1;
        }
        sort(e+1,e+n+1,cmp);
        int tr=-1;
        for(int i = 1; i <= n; i++) {
            if(e[i].ok == 1) continue;
            if(tr == -1 || tr < e[i].l) {
                tr = e[i].r;
                ans++;
            } else if(tr >= e[i].l) {
                tr = min(e[i].r,tr);
            }
        }
        printf("Case #%d: %d\n",++ca,ans);
    }
    return 0;
}