"""
一个实现起来很简单的思路，通过80%用例，考试时很实用，不知道改成C或java是不是还超时
对于示例1，所有左右边界组成的集合(1, 2, 3, 4, 6, 7, 8, 10)，分成七段；
借助字典从前到后为每一段赋值海报编号，
最后 每一段的值代表最上边可以看到的海报编号，
对字典的值求集合的长度，即为可见海报的张数
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    n = int(input().strip())
    a = []
    for _ in range(n):
        a.append(list(map(int, input().strip().split())))
    b = sorted(list(set(sum(a, []))))
    d = dict()
    for i in range(n):
        for j in range(b.index(a[i][0]), b.index(a[i][1])):
            d[str(b[j]) + '-' + str(b[j + 1])] = i
    ans = len(set(d.values()))
    print(ans)  

/*
对每一张海报t，
计算上一层海报未覆盖的(可见)区域(x,y)，
递归调用，直到t>n，海报t仍可以被看到，返回True；
或者直到某一层将可见区域完全覆盖，返回False。
by the way: 最后一个测试用例是错的吧，通过仔细对比已通过程序，26行改为27行通过全部用例 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 10000
int n;
int a[N][2];

bool cover(int  x, int  y, int t)
{
    if (x >= y)
        return false;
    if (t >= n)
        return true;
    if (a[t][0] <= x && y <= a[t][1])
        return false;
    else if (a[t][0] >= y || a[t][1] <= x)
        return cover(x, y, t + 1);
    else if (x <= a[t][0] && a[t][1] <= y)
//        return cover(x, a[t][0], t + 1) || cover(a[t][1], y, t + 1)
        return cover(x, y, t + 1);
    else if (x < a[t][1] && a[t][1] < y)
        return cover( a[t][1], y, t + 1);
    else if (x < a[t][0] && a[t][0] < y)
        return cover( x, a[t][0], t + 1);
    return false;//所有情况都考虑到了，此句不需要；删除此句有时会编译不通过
}

int main()
{
//    freopen("input.txt", "r", stdin);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    int ans = 0;
    for(int t = 0; t < n; t++)
        if(cover(a[t][0], a[t][1], t + 1))
            ans += 1;
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x, y, Min=INT_MAX, Max=0;
    vector<int> m(10000001, 0);
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d%d", &x, &y);
        Min = min(Min, x);
        Max = max(Max, y);
        for(int j=x;j<=y;j++)
            m[j] = i;
    }
    set<int> S;
    for(int i=Min;i<=Max;i++)
        if(m[i])
            S.insert(m[i]);
    cout<<S.size()<<endl;
    return 0;
}

#优化过的顺序dp插入判断方法，很好理解，百分百通过
def main():
    N = int(input())
    k = [[0, i, -1] for i in range(N*2)]
    maxs = 0
    i = 0
    while i < N*2:
        a, b = map(int, input().split())
        k[i][0] = a
        k[i+1][0] = b
        i += 2
#    print(k)
    k.sort(key=lambda x:x[0])
    k[0][2] = 0
    count = 0
    for i in range(1, len(k)):
        if k[i][2] == k[i-1][2]:
            k[i][2] = count
        else:
            count += 1
            k[i][2] = count
#    print("count", count)
    dp = [-1] * (count+1)
#    print(k)
    k.sort(key=lambda x:x[1])
#    print(k)
    i = 0
#    print(dp)
    while i < len(k):
        left = k[i][2]
        right = k[i+1][2]
        for j in range(left, right+1, 1):
            dp[j] = i
        i += 2
#    print(dp)
    dic = dict()
    for i in range(len(k)):
        dic[dp[i]] = dic.get(dp[i], 0)+1
#    print(dic)
    print(len(dic))
if __name__ == "__main__":
    main()

招商银行信用卡中心2019秋招IT笔试(AI、开发、测试开发方向)第一批

https://blog.csdn.net/FlushHip/article/details/84137906

我感觉数据有误

#include<bits/stdc++.h>
using namespace std;
const int max_n = 1e5;
//int seg[4*max_n];
// 懒惰标记，用于延迟传播
int add[4*max_n];
// 建树
//void create(int l,int r,int rt)
//{
//    if(l==r)
//        return;
//    create(l,(l+r)>>1,rt<<1);
//    create(((l+r)>>1)+1,r,rt<<1|1);
//}
// 下推函数
void pushDown(int rt)
{
    if(add[rt])
    {
        // 将标记下推到左右子区间
        add[rt<<1] = add[rt]; 
        add[rt<<1|1] = add[rt];
        // 清除本节点的标记
        add[rt] = 0;
    }
}
void update(int L,int R,int l,int r,int rt,int val)
{
    if(L<=l&&R>=r)
    {
        add[rt] = val; //子区间仍需要根据add值进行调整
        return;
    }
    //if(l==r)  //  叶子节点更新
    //{
    //    add[rt] = val;
    //    return;
    //}
    // 下推标记
    pushDown(rt);
    // 继续寻找区间
    int mid = (l+r)>>1;
    if(L<=mid) update(L,R,l,mid,rt<<1,val);
    if(R>mid) update(L,R,mid+1,r,rt<<1|1,val);

}
// 区间查询不重复的海报数目
void query(int l,int r,int rt,set<int>& se)
{
    if(add[rt])
    {
       // if(l==r)
       // {
            se.insert(add[rt]);
            return;
      //  }
       // else pushDown(rt);
    }
    // 到叶节点了 返回
    if(l==r) return;
    query(l,(l+r)>>1,rt<<1,se);
    query(((l+r)>>1)+1,r,rt<<1|1,se);
}
int main()
{
    int n;
    cin>>n;
    int a,b;
    vector<pair<int,int>>data;
    // 辅助数组
    vector<int>xs;
    for(int i=1;i<=n;++i)
    {
       cin>>a>>b;
       data.push_back({a,b});
       xs.push_back(a);
       xs.push_back(b);
    }
    // 排序
    sort(xs.begin(),xs.end());
    // 去重
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    //create(1,xs.size(),1);
    set<int>se;
    for(int i=1;i<=n;++i)
    {
        // 离散化 节约线段树需要开辟的空间
       int l = lower_bound(xs.begin(),xs.end(),data[i-1].first)-xs.begin()+1;
       int r = lower_bound(xs.begin(),xs.end(),data[i-1].second)-xs.begin()+1;
        // 更新
       update(l,r,1,xs.size(),1,i);
    }
    // 统计数目
    query(1,xs.size(),1,se);
    cout<<se.size()<<endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String args[]) {
        int min = Integer.MAX_VALUE;
        int max = -1;
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] temp = new int[10000001];
        for(int i = 1; i <= N; i++) {
            int Li = in.nextInt();
            int Ri = in.nextInt();
            min = Math.min(Li,Ri);
            max = Math.max(Ri,Li);
            for(int j = min; j <= max; j++) {
                temp[j] = i;
            }
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < temp.length; i++) {
            if(temp[i] != 0) 
                set.add(temp[i]);
        }
        System.out.println(set.size());
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Set <Integer> set = new HashSet<>();
        int T[]= new int[10000001];
        Arrays.fill(T,-1);
        int n = in.nextInt();
        int [][]arr = new int[n][2];
        for(int i=0;i<n;i++){
            arr[i][0]=in.nextInt();
            arr[i][1]=in.nextInt();
        }
        for(int i=0;i<n;i++){
            for(int j=arr[i][0];j<=arr[i][1];j++){
                T[j]=i;
            }
        }
        for(int i=0;i<10000001;i++){
            if(T[i]==-1) continue;
            set.add(T[i]);
        }
        System.out.println(set.size());
    }
}

#include <iostream>
(720)#include <string>
#include <vector>
(721)#include <map>
using namespace std;

int main() {

    //cout << "jisenquan" << endl;
    vector<pair<int, int>> data;
    int n;
    int res;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        pair<int, int> temp;
        cin >> temp.first >> temp.second;
        data.push_back(temp);
    }

    map<int, int> m1;
    m1[data[n - 1].first] = data[n - 1].second;
    res = 1;
    for (int i = n - 2; i >= 0; i--) {
        pair<int, int> temp = data[i];
        bool flag = true;
        for (auto it = m1.begin(); it != m1.end(); it++) {
            if (temp.first >= it->first && temp.second <= it->second) {
                flag = false;
                break;
            }
            if (it->second < temp.first || temp.second < it->first) {
                continue;
            }
            auto it2 = it;
            it2++;
            while (it2 != m1.end() && it2->first <= temp.second) {
                if (it2->second >= temp.second) {
                    it2++;
                    break;
                }
                it2++;
            }
            it2--;
            temp.first = it->first > temp.first ? temp.first : it->first; 
            if (it2 != m1.end())
            {
                temp.second = temp.second > it2->second ? temp.second : it2->second;
            }
            it2++;
            m1.erase(it, it2);
            //it = it2;
            break;
        }
        if (flag) {
            res++;
            m1[temp.first] = temp.second;
        }
    }

    cout << res << endl;
    //system("Pause");
    return 0;
}

import java.util.*;
public class Main{

    public static void main(String[] args){
        //输入
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        if(num==0||num==1) {
            System.out.println(num);
            return;
        }
        scanner.nextLine();
        String[] str = new String[num];
        for(int i=0;i<num;i++) {
            if(scanner.hasNext()) {
                String s = scanner.nextLine();
                str[i] = s;
            }
        }
        scanner.close();
        if(str==null){
            System.out.println(0);
            return;
        }
        ArrayList<Node> arr = new ArrayList<Node>();
        for(String s:str) {
            String[] s1 = s.split(" ");
            int leftval = Integer.valueOf(s1[0]);
            int rightval = Integer.valueOf(s1[1]);
            arr.add(new Node(leftval,rightval));
        }
        //把第一张海报贴到墙上
        ArrayList<ArrayList<Node>> Wall = new ArrayList<ArrayList<Node>>();
        ArrayList<Node> poster1 = new ArrayList<Node>();
        poster1.add(arr.get(0));
        Wall.add(poster1);
        //每加入一张海报，先对墙上的每一个海报段求补集，修改原来的海报段露出的部分的区间
        for(int i=1;i<arr.size();i++) {//新加入的海报
            for(int j=0;j<Wall.size();j++) {//已经贴好的每一张海报
                int index = Wall.get(j).size();
                for(int k=0;k<index;k++) {//每张海报段
                    ArrayList<Node> newPosterDuan = Overlap
                        (Wall.get(j).get(k),arr.get(i));//老海报段对新海报的补集
                    if(newPosterDuan==null) {
                        Wall.get(j).set(k,null);
                    }else {
                        Wall.get(j).remove(k);
                        for(int m=0;m<newPosterDuan.size();m++) {
                            Wall.get(j).add(k,newPosterDuan.get(m));
                        }
                    }
                }
            }
            ArrayList<Node> temp =new ArrayList<Node>();//加入新海报
            temp.add(arr.get(i));
            Wall.add(temp);
        }
        //求总的不为空的海报数量
        int count = 0;
        for(int i=0;i<Wall.size();i++) {
            boolean flag = false;
            ArrayList<Node> temp = Wall.get(i);
            for(int k=0;k<temp.size();k++) {
                if(temp.get(k)!=null) {
                    flag = true;
                }
            }
            if(flag==true) {
                count++;
            }
        }
        System.out.println(count);
    }
    public static ArrayList<Node> Overlap(Node node1,Node node2) {//求node1的补集
        ArrayList<Node> newPosterDuan = new ArrayList<Node>();
        if(node1==null) {
            return null;
        }
        if(node1.left>=node2.left && node1.right<=node2.right ) {
            return null;
        }
        else if(node1.left<=node2.left && node1.right<=node2.right && 
                node2.left<=node1.right) {
            node1.right = node2.left;
            if(node1.left!=node1.right) {
                newPosterDuan.add(node1);	
            }
        }else if(node1.left<=node2.right&&node1.left>=node2.left&&
                 node1.right>=node2.right) {
            node1.left = node2.right;
            if(node1.left!=node1.right) {
                newPosterDuan.add(node1);	
            }
        }else if(node1.left<=node2.left&&node1.right>=node2.right) {
            Node newNode1 = new Node(node1.left,node2.left);
            Node newNode2 = new Node(node2.right,node1.right);
            if(node1.left!=node1.right) {
                newPosterDuan.add(newNode1);	
            }
            if(node2.left!=node2.right) {
                newPosterDuan.add(newNode2);	
            }
        }else {
            newPosterDuan.add(node1);
        }
        return newPosterDuan;
    }
}
class Node{
    int left;
    int right;
    public Node(int left,int right) {
        this.left = left;
        this.right = right;
    }
    @Override
    public String toString() {
        return "Node [left=" + left + ", right=" + right + "]";
    }
}

#include <bits/stdc++.h>
using namespace std;

struct poster {
    int l, r, id; // id为海报标识
    // set比较函数后必须加const
    bool operator<(const poster &b) const {
        return l < b.l;
    }
};
set<poster> s;
set<poster>::iterator it1, it2;

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int a, b;
        scanf("%d%d", &a, &b);
        s.insert({a, b, 0});
        for (int i = 1; i < n; i++) {
            scanf("%d%d", &a, &b);
            // 查询左右边界
            it1 = s.upper_bound({a, 0, 0});
            it2 = s.upper_bound({b, 0, 0});
            if (it1 == s.begin()) { //位于所有海报前面
                if (it2 == s.begin()) {
                    s.insert({a, b, i});
                } else {
                    it2--;
                    int r = it2->r, id = it2->id;
                    s.erase(it1, ++it2);
                    s.insert({a, b, i});
                    s.insert({b, r, id});
                }
            } else {
                it1--; it2--;
                int l = it1->l, r = it2->r, id1 = it1->id, id2 = it2->id;
                s.erase(it1, ++it2);
                if (r <= a) { // 位于所有海报后面
                    s.insert({l, r, id1});
                    s.insert({a, b, i});
                } else { //位于海报中间
                    if(l < a) s.insert({l, a, id1});
                    s.insert({a, b, i});
                    if (r > b) s.insert({b, r, id2});
                }
            }
        }
        unordered_set<int> hs;
        int ans = 0;
        for (it1 = s.begin(); it1 != s.end(); it1++) {
            if (hs.find(it1->id) == hs.end()) {
                ans++;
                hs.insert(it1->id);
            }
        }
        s.clear();
        printf("%d\n", ans);
    }
    return 0;
}

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    int n,left,right,res=0;
    cin>>n;
    vector<pair<int,int>> hb;
    set<pair<int,int>> tmp;
    for(int i=0;i<n;i++){
        cin>>left>>right;
        hb.push_back(make_pair(left,right));
    }
    tmp.insert(hb[n-1]);
    res++;
    set<pair<int,int>>::iterator iter;
    for(int i=n-2;i>=0;i--){
        iter=tmp.begin();
        if(iter->first>=hb[i].second){
            if(iter->first==hb[i].second){
                hb[i].second=iter->second;
                tmp.erase(iter);
                tmp.insert(hb[i]);
            }else
                tmp.insert(hb[i]);
            res++;
            continue;
        }
        while(iter!=tmp.end()&&hb[i].first>iter->second){
            iter++;
        }
        if(iter==tmp.end()){
            tmp.insert(hb[i]);
            res++;
            continue;
        }
        if(hb[i].first>=iter->first&&hb[i].second<=iter->second)
            continue;
        if(hb[i].second<iter->first){
            tmp.insert(hb[i]);
            res++;
            continue;
        }
        pair<int,int> ni;
        res++;
        ni.first=min(iter->first,hb[i].first);
        ni.second=max(iter->second,hb[i].second);
        set<pair<int,int>>::iterator iter2=iter;
        iter2++;
        while(iter2!=tmp.end()&&iter2->first<=ni.second){
            ni.second=max(ni.second,iter2->second);
            tmp.erase(iter2);
            iter2=iter;
            iter2++;
        }
        tmp.erase(iter);
        tmp.insert(ni);
    }
    if(n==0)
        cout<<0<<endl;
    else
        cout<<res<<endl;
    return 0;
}

//#include "utils.cpp"
#include <bits/stdc++.h>
using namespace std;


vector<int> li,ri;
int N;
//求[l,r]被k以后海报遮掩的情况
bool f(int l,int r,int k){
    if(k==N) return false;
	//1.两者无交集
	if(li[k]>=r&nbs***bsp;ri[k]<=l) return f(l,r,k+1);
    //2.被完全遮掩
    if(li[k]<=l and ri[k]>=r) return true;
    //3.左半边被完全遮掩
    if(li[k]<=l and ri[k]<r) return f(ri[k],r,k+1);
    //4.右半边被完全遮掩
    if(ri[k]>=r and li[k]>l) return f(l,li[k],k+1);
    //5.中间一部分被遮掩
    if(li[k]>l and ri[k]<r){
		//PR(f(l,li[k],k+1) , f(ri[k],r,k+1));
        return f(l,li[k],k+1) && f(ri[k],r,k+1);
    }
    
    
}

int main(){
	//freopen("temp.in","r",stdin);
    cin>>N;
    li.resize(N);
    ri.resize(N);
    for(int i=0;i<N;i++){
        cin>>li[i]>>ri[i];
    }
    int ans = 0;
    for(int i=0;i<N;i++){
        if(f(li[i],ri[i],i+1)) continue;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<pair<int,int>> m;
    int s,t;
    while(n)
    {
        cin>>s>>t;
        n--;
        m.push_back(make_pair(s,t));
    }
    for(auto it=m.begin();it!=m.end();it++)
    {
        auto ot=it;
        ot++;
        for(;ot!=m.end();ot++)
        {
            if((ot->first<it->second)&&(ot->second>=it->second))
                it->second=ot->first;
            else if((ot->second>it->first)&&(ot->first<=it->first))
                it->first=ot->second;
           // else if((ot->first>it->first)&&(ot->second<it->second))
           // {
                
            //}
        }
    }
    int sum=0;
    for(auto it:m)
    {
        if(it.first<=it.second)
            sum++;
    }
    cout<<sum;
}