本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AtCoder：E - Count the Types of Flowers
【题目描述】
Takahashi works as a caretaker at a botanical garden. The garden hasN NNflower beds arranged in a straight line, numbered1 , 2 , … , N 1, 2, \ldots, N1,2,…,Nfrom left to right. Each flower bedi ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)contains a flower of species numberP i P_iPi. Species numbers are integers between1 11andN NNinclusive, and different flower beds may contain flowers of the same species number.
高桥在一座植物园担任管理员。花园里有N NN个花坛排成一条直线，从左到右编号为1 , 2 , … , N 1, 2, …, N1,2,…,N。每个花坛i ii（1 ≤ i ≤ N 1 ≤ i ≤ N1≤i≤N）包含一种编号为P i P_iPi的花卉。物种编号是介于1 11和N NN之间的整数，不同的花坛可能包含相同物种编号的花卉。
The botanical garden hasQ QQtour visits scheduled. Thei ii-th tour( 1 ≤ i ≤ Q ) (1 \leq i \leq Q)(1≤i≤Q)visits the range from flower bedL i L_iLito flower bedR i R_iRi(inclusive).
植物园安排了Q QQ次参观游览。第i ii次参观（1 ≤ i ≤ Q 1 ≤ i ≤ Q1≤i≤Q）将访问从花坛L i L_iLi到花坛R i R_iRi（包含两端）的范围。
Takahashi wants to know in advance how many distinct types of flowers are in each tour’s visiting range, in order to prepare the guide for each tour.
高桥希望提前了解每次参观的访问范围内有多少种不同的花卉类型，以便为每次参观准备导览。
For each tour, determine the number of distinct species numbers contained in the range from flower bedL i L_iLito flower bedR i R_iRi.
对于每次参观，确定从花坛L i L_iLi到花坛R i R_iRi的范围内包含的不同物种编号的数量。
【输入】
N NNQ QQ
P 1 P_1P1P 2 P_2P2… \ldots…P N P_NPN
L 1 L_1L1R 1 R_1R1
L 2 L_2L2R 2 R_2R2
⋮ \vdots⋮
L Q L_QLQR Q R_QRQ
- The first line contains an integerN NNrepresenting the number of flower beds and an integerQ QQrepresenting the number of tours, separated by a space.
- The second line contains integersP 1 , P 2 , … , P N P_1, P_2, \ldots, P_NP1,P2,…,PNrepresenting the species numbers of the flowers planted in each flower bed, separated by spaces.
- The followingQ QQlines give the visiting range for each tour.
- Thei ii-th of these lines( 1 ≤ i ≤ Q ) (1 \leq i \leq Q)(1≤i≤Q)contains the left endpointL i L_iLiand right endpointR i R_iRiof the visiting range for thei ii-th tour, separated by a space.
【输出】
OutputQ QQlines. Thei ii-th line( 1 ≤ i ≤ Q ) (1 \leq i \leq Q)(1≤i≤Q)should contain the number of distinct species numbers in the range from flower bedL i L_iLito flower bedR i R_iRifor thei ii-th tour.
【输入样例】
5 3 1 2 1 3 2 1 3 2 5 1 5【输出样例】
2 3 3【解题思路】
【算法标签】
#树状数组#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intn,q;// n: 数组长度，q: 查询次数intp[N],last[N];// p: 原数组，last: 记录每个物种上次出现的位置inttr[N],ans[N];// tr: 树状数组，ans: 存储查询结果structNode{intid,l,r;// 查询的编号、左边界、右边界}Q[N];// 计算lowbit：返回x的二进制表示中最低位的1所对应的值intlowbit(intx){returnx&-x;}// 树状数组更新操作：在位置x增加cvoidadd(intx,intc){for(inti=x;i<=n;i+=lowbit(i)){tr[i]+=c;}}// 树状数组查询操作：查询前缀和[1, x]intquery(intx){intres=0;for(inti=x;i;i-=lowbit(i)){res+=tr[i];}returnres;}// 查询按右端点排序的比较函数boolcmp(Node x,Node y){returnx.r<y.r;// 按右端点升序排序}intmain(){cin>>n>>q;// 读入数组长度和查询次数for(inti=1;i<=n;i++){cin>>p[i];// 读入原数组}for(inti=1;i<=q;i++)// 读入查询{intl,r;cin>>l>>r;Q[i]={i,l,r};// 存储查询编号、左右边界}sort(Q+1,Q+q+1,cmp);// 将查询按右端点排序intcur=1;// 当前处理的数组位置for(inti=1;i<=q;i++)// 处理每个查询{intl=Q[i].l,r=Q[i].r,id=Q[i].id;// 处理数组位置，直到达到当前查询的右端点while(cur<=r){intspecies=p[cur];// 当前位置的物种if(last[species]!=0)// 如果这个物种之前出现过{add(last[species],-1);// 在之前出现的位置-1}add(cur,1);// 在当前位置+1last[species]=cur;// 更新这个物种最后出现的位置cur++;}// 查询区间[l, r]的不同物种数量ans[id]=query(r)-query(l-1);}for(inti=1;i<=q;i++){cout<<ans[i]<<endl;// 输出所有查询结果}return0;}【运行结果】
5 3 1 2 1 3 2 1 3 2 2 5 3 1 5 3
