C++算法——离散化
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef pair< int , int > PII;
const int N = 300010;
int n , m; //输入n个整数，对m个区间进行求和
//a[N]下标表示映射后数组的下标，值表示该下标的值
//s[N]表示前缀和
int a[N] , s[N];
vector<int> alls; //把原数组中每个数的下标以及查询的下标（单凡出现过的下标）
vector<PII> add , query; //add存储原数组的下标和值，query存储的是要查的左右端点{l,r}
int find( int x )
{
int l = 0 , r = alls.size() - 1 ;
//利用二分找到原数组x下标对应的
while(l < r)
{
int mid = l + r >> 1;
if( alls[mid] >= x ) r = mid;
else l = mid + 1;
}
return r + 1;
}
vector<int>::iterator unique(vector<int> &a)
{
int j = 0;
for (int i = 0; i < a.size(); i ++ )
if ( !i || a[i] != a[i - 1] )
a[j ++ ] = a[i];
// a[0] ~ a[j - 1] 所有a中不重复的数
return a.begin() + j;
}
int main()
{
cin >> n >> m;
//输入n个数到add中 ,其中x表示下表，c表示值
for(int i = 0 ; i < n ; i++ )
{
int x , c;
cin >> x >> c;
add.push_back( {x , c} );
alls.push_back(x);
}
//输入m个数到alls中，其中l表示左端点 ， r表示右端点
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中的每个数的下标进行排序
//利用unique函数除去重复项
alls.erase( unique( alls ) , alls.end() );
//处理插入
for( auto item : add ) //遍历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;
}