python问题，难倒同学无数_(:з」∠)_

问题遇到的现象和发生背景
题目要求：
输入
5（输入的个数）
1 10 （1-10)
7 9
3 8
4 7 （4-7）
5 5 （5:5 只有5）
输出
1 1 （1、计算1出现的次数）
2 1（2、2出现的次数，为1）
3 2（3、3出现的次数，为2）
4 3
5 4
6 3
7 3
8 3
9 2
10 1

问题相关代码，请勿粘贴截图

a=int(input())
c = [[],[]]
for i in range(a):
    b = [int(n) for n in input().split()]
    c[0].append(b[0])
    c[1].append(b[1])
for i in range(min(c[0]),max(c[1])+1):
    m = len([n for n in c[0] if n<=i])
    n = len([n for n in c[1] if n<i])
    if m-n>0:
        print(i,m-n)

运行结果及报错内容
此代码可以实现功能，但是时间复杂度大，需要优化

我的解答思路和尝试过的方法
PS:
教授上课讲的方法，仅供参考
假如需要查找6出现的个数
因为在[1 10]这个数组里
(我是数轴)—[1—6—10]—→√
在[7 9]这个数组里
(我是数轴)—6—[7—8—9]—→X
因此[a,b]如果满足
(我是数轴)—[a—6—b]—→√
(我是数轴)—6—[a—b]—→X
(我是数轴)—[a—b]—6—→X
现在将示例中5个数组
[1 10]
[7 9]
[3 8]
[4 7]
[5 5]
写成2个数组
A=[1 7 3 4 5] 左列
B=[10 9 8 7 5] 右列
找到A里≤6的数有4个（可能有6的数组数量）
B里<6的数有1个（在可能有6的数量里，没有6的数组数量）
所以6的出现的次数为4-1=3个

按照你老师的算法，两个列表排序之后用二分法查找，试试

def BinarySearch(li,n,k):
    if k<li[0]:
        return 0
    if k>=li[-1]:
        return n
    left=0
    right=n-1
    while left<=right:
        middle=(left+right)//2
        if li[middle]<=k:
            left=middle+1
        if li[middle]>k:
            right=middle-1
    return left;

n = int(input())
li1 = []
li2 = []
for i in range(n):
    a,b = map(int,input().split())
    li1.append(a)
    li2.append(b)
li1.sort()
li2.sort()
for i in range(li1[0],li2[-1]+1):
    a = BinarySearch(li1,n,i)
    b = BinarySearch(li2,n,i-1)
    m = a-b
    if m>0:
        print(i,m)

    a=int(input())
    c = []
    for i in range(a):
        x,y=[int(n) for n in input().split()]
        c += range(x,y+1)

    for i in range(min(c),max(c)+1):
        m = c.count(i)
        if m>0:
            print('{} {}'.format(i,m))

这个效率比之前的高一点点，print 最耗时，print(a,b) 比 print('{} {}'.format(a,b)) 耗时

是同一个问题 但是没有解决
https://ask.csdn.net/questions/7588717?answer=53614856&spm=1001.2014.3001.5501

【有帮助请采纳】

n = int(input())#输入的个数
datalist = []#创建一个列表用于储存输入数据
for i in range(n):
    list = input().split()#将列表以空格为间隔拆成两部分
    for k in range(int(list[0]),int(list[1])+1):#对每个已拆开的列表所要表达的元素进行遍历
        datalist.append(k)#将遍历得到的数据存到datalist列表中
for x in range(1,max(datalist)+1):#这个必定遍历datalist列表中的所有元素
    if datalist.count(x) != 0:#判断该数是否为0个（如果是就不要）
        print('%d %d'%(x,datalist.count(x)))#输出结果

【有帮助请采纳】

原题

C++解法
可以参考

#include <iostream>
#include<vector>
using namespace std;
const int MAX = 100000;
int index = 0;

struct TreeNode
{
    int flag = 0;
    int geshu = 0;
    int left = 0;
    int right = 0;
    int value = 0;
};
void Pushup(int k,int l,int r, vector<TreeNode*>& t) {        //更新函数，这里是实现最大值 ，同理可以变成，最小值，区间和等
    TreeNode* father = new TreeNode;
    father->left = l;
    father->right = r;
    t[k] = father;
    return;
}
void build(int k, int l, int r, vector<TreeNode*>& t, vector<TreeNode*>& res) {
    if (l == r) { 
        TreeNode* temp = new TreeNode;
        temp->value = l;
        //todo开辟数组保存底端值

        temp->left = l;
        temp->right = r;
        t[k] = temp;
        res[index++] = temp;

    }
    else {
        int m = l + ((r - l) >> 1);    //m则为中间点，左儿子的结点区间为[l,m],右儿子的结点区间为[m+1,r]
        build(k << 1, l, m,  t,res);    //递归构造左儿子结点
        build(k << 1 | 1, m + 1, r,  t,res);    //递归构造右儿子结点
        Pushup(k, l, r,t);    //更新父节点

    }

}
void Pushdown(int k, vector<TreeNode*>& t) {
    if (t[k]->flag > 0) {
        if (t[k << 1]->left == t[k << 1]->right) {
            t[k << 1]->geshu = t[k << 1]->geshu + t[k]->flag;
        }
        else
        {
            t[k<<1]->flag= t[k << 1]->flag+ t[k]->flag;
        }
        if (t[k << 1|1]->left == t[k << 1|1]->right) {
            t[k << 1|1]->geshu = t[k << 1|1]->geshu + t[k]->flag;
        }
        else
        {
            t[k << 1|1]->flag = t[k << 1|1]->flag + t[k]->flag;
        }
        t[k]->flag = 0;

    }

}
//递归更新区间 updata(L,R,v,1,n,1);
void updata(int k,int L, int R, int l, int r, vector<TreeNode*>& t) {    //[L,R]即为要更新的区间，l，r为结点区间，k为结点下标
    if (L <= l && r <= R) {    //如果当前结点的区间真包含于要更新的区间内
        if (l == r) {
            t[k]->geshu++;
        }
        else {
            t[k]->flag++;
        }
    }
    else {
        Pushdown(k, t);    //重难点，查询lazy标记，更新子树
        int m = l + ((r - l) >> 1);
        if (L <= m)    //如果左子树和需要更新的区间交集非空
            updata(k << 1,L, R, l, m, t);
        if (m < R)    //如果右子树和需要更新的区间交集非空
    }
}
void qury(int k, int L, int R, int l, int r, vector<TreeNode*>& t) {
    if (l == r)return;

    if (L <= l && r <= R) {    //如果当前结点的区间真包含于要更新的区间内
        if (t[k]->flag>0) {
            Pushdown(k, t); 
        }
        int m = l + ((r - l) >> 1);
        if (L <= m)    //如果左子树和需要更新的区间交集非空
            qury(k << 1, L, R, l, m, t);
        if (m < R)    //如果右子树和需要更新的区间交集非空
            qury(k << 1 | 1, L, R, m + 1, r, t);
     
    }
   


}
int main() {
    {
        int number,left,right;
        cin >> number;
        vector<TreeNode*>vec1(4 * MAX);
        vector< TreeNode*>res(MAX);

        build(1, 1, MAX,vec1,res);
        for (int i = 0; i < number; i++) {
            cin >> left >> right;
            updata(1, left, right, 1, MAX, vec1);
        }
        qury(1, 1, MAX, 1, MAX, vec1);
        for (int i = 0; i < MAX; i++) {
            if (res[i]->geshu != 0) {
                cout << res[i]->value << " " << res[i]->geshu << endl;
            }
        }

    }
}