离散化模板

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

题目描述：

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109 ,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

8
0
5

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
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n,m;
int a[N],s[N];

vector<int> alls;
vector<PII> add,query;

int find(int x){
    
    int l = 0, r = alls.size() - 1;
    while(l < r){
        int mid = l + r>> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int x,c;
        cin >> x >>c;
        add.push_back({x,c});
        
        alls.push_back(x);
    }
    
    for(int i = 0; i < m; i++){
        int l,r;
        cin >> l >> r;
        query.push_back({l,r});
        
        alls.push_back(l);
        alls.push_back(r);
    }
    
    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()),alls.end());
    
    //处理插入
    for(auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    
    //预处理前缀和
    for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
    
    //处理询问
    for(auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s [l - 1] << endl;
    }
    
    return 0;
}



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
76
77
78
79
80
81
82
83
#include <stdio.h>

int findleftk(int a[],int lo,int hi,int k){//二分查找 重复元素最左侧的一个
    if(hi-lo<=2){
        if(a[lo]>=k) return lo;
        else if(a[lo+1]>=k) return lo+1;
        else return lo+2;
    }
    else{
        int mid=(lo+hi)/2;
        if(a[mid]<k) return findleftk(a,mid+1,hi,k);
        else return findleftk(a,lo,mid+1,k);
    }
}

int findrightk(int a[],int lo,int hi,int k){     
    if(hi-lo<=2){
        if(a[lo+1]<=k) return lo+1;
        else if(a[lo]<=k) return lo;
        else return lo-1;
    }
    else{
        int mid=(lo+hi)/2;
        if(a[mid]>k) return findrightk(a,lo,mid,k);
        else return findrightk(a,mid,hi,k);
    }
}

void quicksort(int a[],int b[],int lo,int hi){
    int n=hi-lo,i=lo,j=hi-1;
    if(n<=1) return;
    else{
        int t=a[lo],p=b[lo];
        while(i<j){
            while(i<j && a[j]>t) j--;
            if(i<j){
                a[i]=a[j];
                b[i++]=b[j];
            }
            while(i<j && a[i]<t) i++;
            if(i<j){
                a[j]=a[i];
                b[j--]=b[i];
            }
        }
        a[i]=t;
        b[i]=p;
        quicksort(a,b,lo,i);
        quicksort(a,b,i+1,hi);
    }
}

int main(){
    int n,m,i,j,k,p,q;
    scanf("%d %d",&n,&m);

    int a[n],b[n],sum[n];	//a[]存下标 b[]存数值
    for(i=0;i<n;i++) scanf("%d %d",&a[i],&b[i]);
    quicksort(a,b,0,n);

    sum[0]=b[0];

    for(i=1;i<n;i++) sum[i]=sum[i-1]+b[i]; //前缀和

    for(i=0;i<m;i++){
        scanf("%d %d",&p,&q);
        j=findleftk(a,0,n,p);   //先二分查找
        k=findrightk(a,0,n,q);
    
    if(j<=k) printf("%d\n",sum[k]-sum[j]+b[j]);
    else printf("0\n");
    
    //暴力求和会超时 用前缀和来求
    // sum=0;
    // for(j=0;j<n;j++){
    //     if(a[j]>=p && a[j]<=q) sum+=b[j];
    // }
    // printf("%d\n",sum);
    }
    
    return 0;
}