企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：E - Multiple Bonus

【题目描述】

Takahashi is a department manager who managesN NNemployees. Each employee is assigned an employee number from1 11toN NN, and the initial evaluation points of employeei iiareS i S_iSi​.
高桥是一位部门经理，管理着N NN名员工。每位员工被分配了一个从1 11到N NN的员工编号，员工i ii的初始评分为S i S_iSi​。

LetT i T_iTi​denote the current evaluation points of employeei ii. Initially,T i = S i T_i = S_iTi​=Si​(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N).
设T i T_iTi​表示员工i ii当前的评分。初始时，T i = S i T_i = S_iTi​=Si​（1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N）。

This company has a unique evaluation system. When a certain employeek kk(1 ≤ k ≤ N 1 \leq k \leq N1≤k≤N) achieves results as a team leader, bonus points corresponding to the achievement are added to the evaluation points of all employees whose employee numbers are multiples ofk kk(k , 2 k , 3 k , … k, 2k, 3k, \ldotsk,2k,3k,…) and are at mostN NN. Sincek kkitself is a multiple ofk kk, it is included in the targets.
这家公司有一套独特的评分系统。当某位员工k kk（1 ≤ k ≤ N 1 \leq k \leq N1≤k≤N）作为团队领导取得成果时，与成就对应的奖励分数会被加到所有员工编号是k kk的倍数（k , 2 k , 3 k , … k, 2k, 3k, \ldotsk,2k,3k,…）且不超过N NN的员工的评分上。由于k kk本身是k kk的倍数，因此也包含在目标中。

Takahashi performsQ QQoperations on this evaluation system. Each operation is one of the following two types:
高桥对该评分系统执行Q QQ次操作。每次操作是以下两种类型之一：

• Operation1 11: Given a positive integerk kk(1 ≤ k ≤ N 1 \leq k \leq N1≤k≤N) and a positive integerv vv. Addv vvto the evaluation pointsT j T_jTj​of all employeesj jjwhose employee numbers are multiples ofk kkand are at mostN NN(i.e.,j = k , 2 k , 3 k , … j = k, 2k, 3k, \ldotsj=k,2k,3k,…andj ≤ N j \leq Nj≤N).
  操作1 11：给定一个正整数k kk（1 ≤ k ≤ N 1 \leq k \leq N1≤k≤N）和一个正整数v vv。将所有员工编号是k kk的倍数且不超过N NN的员工j jj（即j = k , 2 k , 3 k , … j = k, 2k, 3k, \ldotsj=k,2k,3k,…且j ≤ N j \leq Nj≤N）的评分T j T_jTj​增加v vv。
• Operation2 22: Given a positive integerx xx(1 ≤ x ≤ N 1 \leq x \leq N1≤x≤N). Output the sum of the current evaluation points from employee1 11to employeex xx:∑ i = 1 x T i \displaystyle\sum_{i=1}^{x} T_ii=1∑x​Ti​.
  操作2 22：给定一个正整数x xx（1 ≤ x ≤ N 1 \leq x \leq N1≤x≤N）。输出从员工1 11到员工x xx的当前评分之和：∑ i = 1 x T i \displaystyle\sum_{i=1}^{x} T_ii=1∑x​Ti​。

For all operations of type2 22, output the correct answer.
对于所有类型2 22的操作，输出正确答案。

【输入】

N NNQ QQ
S 1 S_1S1​S 2 S_2S2​… \ldots…S N S_NSN​
q u e r y 1 \mathrm{query}_1query1​
q u e r y 2 \mathrm{query}_2query2​
⋮ \vdots⋮
q u e r y Q \mathrm{query}_QqueryQ​

• The first line contains the number of employeesN NNand the number of operationsQ QQ, separated by a space.
• The second line contains the initial evaluation pointsS 1 , S 2 , … , S N S_1, S_2, \ldots, S_NS1​,S2​,…,SN​of each employee, separated by spaces.
• The followingQ QQlines each contain one operation.
• For operation1 11: given in the format1 k v.
• For operation2 22: given in the format2 x.

【输出】

Each time operation2 22is given, output the sum of evaluation points from employee1 11to employeex xxon one line.

【输入样例】

5 6 1 2 3 4 5 2 3 1 2 10 2 5 1 1 1 2 1 2 4

【输出样例】

6 35 2 34

【解题思路】

【算法标签】

#树状数组#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn,q,s[N],sa[N],tr[N],tag[N];// s: 原始数组, sa: 前缀和, tr: 树状数组, tag: 分块标记intlowbit(intx)// 提出x的低位2次幂数{returnx&-x;}voidadd(intx,intc)// 向后修：树状数组单点增加{for(inti=x;i<=n;i+=lowbit(i)){tr[i]+=c;}}intquery(intx)// 向前查：树状数组前缀和查询{intres=0;for(inti=x;i;i-=lowbit(i)){res+=tr[i];}returnres;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q;// 输入数组长度和操作次数for(inti=1;i<=n;i++){cin>>s[i];// 输入原始数组sa[i]=sa[i-1]+s[i];// 计算前缀和}intB=sqrt(n);// 分块阈值while(q--){intop;cin>>op;// 操作类型if(op==1)// 修改操作{intk,v;cin>>k>>v;// 对k的倍数位置增加vif(k<=B)// 小k，使用分块标记{tag[k]+=v;}else// 大k，直接修改树状数组{for(inti=k;i<=n;i+=k){add(i,v);}}}else// 查询操作{intx;cin>>x;// 查询前缀和intans=sa[x]+query(x);// 基础前缀和+树状数组修改for(intk=1;k<=B;k++)// 加上分块标记的贡献{ans+=tag[k]*(x/k);}cout<<ans<<endl;}}return0;}

【运行结果】

5 6 1 2 3 4 5 2 3 6 1 2 10 2 5 35 1 1 1 2 1 2 2 4 34