NC15706. 前缀查询
描述
输入描述
第一行为两个整数 0 ≤ N ≤ 105，表示接下来有 N 个操作；
接下来 N 行，每行输入一个操作，行首为一个整数 1 ≤ oi ≤ 4，表示这一行的操作的种类，那么这一行的操作和格式为：1. 插入人名，这一行的格式为 1 si ai，其中 |ai| ≤ 103
2. 前缀修改声望，这一行的格式为 2 pi di，其中 |di| ≤ 103
3. 查询名字的声望和，这一行的格式为 3 sj
4. 查询前缀的声望和，这一行的格式为 4 pj输入保证插入人名的字符串的长度和小于或等于 105，总的字符串的长度和小于或等于 106。
输出描述
对于每一次询问操作，在一行里面输出答案。
示例1
输入:
20 1 a -10 1 abcba -9 1 abcbacd 5 4 a 2 a 9 3 aadaa 3 abcbacd 4 a 3 a 2 a 10 3 a 2 a -2 2 d -8 1 ab -2 2 ab -7 1 aadaa -3 4 a 3 abcba 4 a 4 c
输出:
-14 0 14 13 -1 9 11 1 11 0
C++(clang++ 11.0.1) 解法, 执行用时: 162ms, 内存消耗: 4360K, 提交时间: 2022-10-19 21:50:19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll s[1000005];
char t[1000005];
int q,n,root,i,j,c[1000005][26],x[1000005],a[1000005];
void fix(int &r,char *t,int d)
{
if(!r)r=++n;
a[r]++;
s[r]+=d;
if(!*t)return;
fix(c[r][*t-'a'],t+1,d-x[r]);
}
int fix1(int r,char *t,int d)
{
if(!r)return 0;
if(!*t)
{
x[r]+=d;
s[r]+=(ll)a[r]*d;
return a[r];
}
int f=fix1(c[r][*t-'a'],t+1,d);
s[r]+=(ll)d*f;
return f;
}
ll ask(int r,char *t,bool b,int f)
{
if(!r)return 0;
if(!*t)
{
ll ans=s[r]+(ll)f*a[r];
if(b)for(int i=0;i<26;i++)ans-=ask(c[r][i],t,0,f+x[r]);
return ans;
}
return ask(c[r][*t-'a'],t+1,b,f+x[r]);
}
int main()
{
scanf("%d",&q);
while(q--)
{
scanf("%d%s",&i,t);
if(i==1)
{
scanf("%d",&i);
fix(root,t,i);
}
else if(i==2)
{
scanf("%d",&i);
fix1(root,t,i);
}
else cout<<ask(root,t,i&1,0)<<endl;
}
return 0;
}