自动搬运

查看原文

来自洛谷，原作者为

	SunsetVoice **

搬运于2025-08-24 23:07:07，当前版本为作者最后更新于2024-12-18 18:32:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

背景故事

提供一个能将此题降上位橙的解法。

先按 $d$ 从小到大排序对每一个可能的前缀建桶，记录所有能对这个字符串产生贡献的 $d,v$ 数值，最后对 $v$ 做前缀和。

由于我们已经按 $d$ 排好了序，所以 $d$ 在数组中一定是从小到大排序的，查询时二分即可。

复杂度（使用 map 情况下） $O(n\log n+nS_i\log nS_i+m\log nS_i)$。

考虑在常数上优化，首先尽量少开 long long，后对每个桶记录是否已计算好前缀和以保证计算时只计算一次，再优化输入输出即可。

#include<bits/stdc++.h>
using namespace std;
struct memory{
	bool isvb;
	vector<long long>d,v,vb;
	void cl(){
		long long sum = 0;
		for(long long hjx:v){
			sum+=hjx;
			vb.push_back(sum);
		}
		isvb = 1;
	}
};
map<string,memory>mp;
long long n,m;
struct node{
	int d,v;
	string str;
}a[200001];
bool cmp(node x,node y){
	return x.d<y.d;
}
inline string read()
{
	string str="";
	char ch=getchar();
	while(ch==' ' || ch=='\n' || ch=='\r')
	{
		ch=getchar(); 
	}
	while(ch!=' ' && ch!='\n' && ch!='\r')
	{
		str+=ch;
		ch=getchar();
	} 
	return str;
}
signed main(){
	scanf("%lld %lld",&n,&m);
	for(register int i = 1;i<=n;i++){
		scanf("%d %d",&a[i].d,&a[i].v);
		a[i].str = read();
	}
	sort(a+1,a+1+n,cmp);
	for(register int i = 1;i<=n;i++){
		string nstr = "";
		int gl = a[i].str.length();
		for(register int j = 0;j<gl;j++){
			nstr+=a[i].str[j];
			mp[nstr].d.push_back(a[i].d);
			mp[nstr].v.push_back(a[i].v);
			mp[nstr].isvb = 0;
		}
	}
	for(int i = 1;i<=n;i++){
		string nstr = "";
		int gl = a[i].str.length();
		for(int j = 0;j<gl;j++){
			nstr+=a[i].str[j];
			if(mp[nstr].isvb==0){
				mp[nstr].cl();
			}
		}
	}
	while(m--){
		int fd;
		string fq;
		scanf("%d",&fd);
		cin>>fq;
		if(!mp.count(fq)){
			printf("0\n");
			continue;
		}
		int pos = upper_bound(mp[fq].d.begin(),mp[fq].d.end(),fd)-mp[fq].d.begin()-1;
		if(pos<0){
			printf("0\n");
			continue;
		}
		printf("%lld\n",mp[fq].vb[pos]);
	}
	return 0;
}