算法1
(y总算法,保序哈希)
将所有下标(n个点,m个查询)存入alls数组,之后进行排序和去重操作。
把alls数组所有元素找到离散化后的值,之后把对应的值加到前缀和数组s[]。
求s数组前缀和,然后根据查询的结果输出。
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,idx;
struct node{
int id;
int w=0;
}num[N];
struct que{
int l,r;
}ry[N];
vector<int> alls;
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; //从1开始方便进行前缀和操作
}
int s[3*N];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>num[i].id>>num[i].w;
alls.push_back(num[i].id);
}
for(int i=0;i<m;i++)
{
cin>>ry[i].l>>ry[i].r;
alls.push_back(ry[i].l);
alls.push_back(ry[i].r);
}
sort(alls.begin(),alls.end()); //排序操作
alls.erase(unique(alls.begin(),alls.end()),alls.end()); //去重操作
for(int i=0;i<n;i++)
{
int t=find(num[i].id);
s[t]+=num[i].w;
}
for(int i=1;i<=alls.size();i++) s[i]+=s[i-1];
for(int i=0;i<m;i++)
{
int l=find(ry[i].l),r=find(ry[i].r);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
算法2
(双哈希表操作)
不需要使用二分法进行操作,可以用两个哈希表解决。
一个哈希表mp将所有下标存进来,之后把这些下标存入到num数组中,排序后进行前缀和。
把对应的下标和前缀和映射到mp2,之后输出前缀和操作的结果。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
unordered_map<int,int> mp;
unordered_map<int,int> mp2;
int n,m,idx;
struct node{
int id;
int w=0;
bool operator<(const node& p)
{
return id<p.id;
}
}num[3*N];
struct que{
int l,r;
}ry[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
int x,y;
for(int i=0;i<n;i++)
{
cin>>x>>y;
if(!mp.count(x)) mp[x]=idx++;
num[mp[x]].id=x;
num[mp[x]].w+=y;
}
int l,r;
for(int i=0;i<m;i++)
{
cin>>l>>r;
ry[i].l=l-1,ry[i].r=r;
if(!mp.count(l-1))
{
mp[l-1]=idx++;
num[mp[l-1]].id=l-1;
num[mp[l-1]].w=0;
}
if(!mp.count(r))
{
mp[r]=idx++;
num[mp[r]].id=r;
num[mp[r]].w=0;
}
}
sort(num,num+idx);
for(int i=1;i<idx;i++)
num[i].w+=num[i-1].w;
for(int i=0;i<idx;i++)
{
mp2[num[i].id]=num[i].w;
}
for(int i=0;i<m;i++)
{
cout<<mp2[ry[i].r]-mp2[ry[i].l]<<endl;
}
return 0;
}