区间映射，区间离散化，大范围映射到小范围

喜欢ヅ旅行 2022-08-29 15:50 163阅读 0赞

区间离散化

当然`int x = find (targe);`

等价于

`int x = low_bound(0,alls.size()-1, targe) - alls + 1;`

#include <bits/stdc++.h>
    using namespace std;
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define fep(i,a,b) for(int i=a;i>=b;--i)
    #define ff first
    #define ss second
    #define ll long long
    #define mk make_pair
    #define all(a) (a).begin(),(a).end()
    #define pb push_back
    typedef pair <int,int> PII;
    const int inf = 0x3f3f3f3f;
    const int N = 100010;
    
    
    int n, m;
    int a[N], s[N];
    
    std::vector<int> alls;
    std::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()
    { 
    	ios;
    	cin >> n >> m;
    	rep(i, 0 , n-1)
    	{ 
    		int x, c;
    		cin >> x >> c;
    		add.pb({ x, c});
    		alls.pb(x);
    	}
    	rep(i,0,m-1)
    	{ 
    		int l, r;
    		cin >> l >> r;
    		query.pb({ l,r});
            alls.pb(l);
            alls.pb(r);
    	}
    	// 
    	sort(all(alls));
    	alls.erase(unique(all(alls)), alls.end());
    	for (auto item : add)
    	{ 
    		int x = find(item.ff);
    		a[x] += item.ss;
    	}
    	for (int i=1;i<=alls.size();i++) s[i] = s[i-1] + a[i];
    	for (auto item : query)
    	{ 
    		int l = find(item.ff), r = find(item.ss);
    		cout << s[r] - s[l-1] << endl;
    	}
    	return 0;
    }