力扣 LeetCode 2916. 子数组不同元素数目的平方和 II - 力扣（LeetCode） 2916. 子数组不同元素数目的平方和 II - 给你一个下标从 0 开始的整数数组 nums 。 定义 nums 一个子数组的 不同计数 值如下： 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。 请你返回 nums 中所有子数组的 不同计数 的... 思路 1. 转化贡献 假设一个子数组中出现的元素集合为 \{a,b,c,d...\} ，那么这个集合产生的贡献在数值上相当于集合中所有的元素二元组个数，即 (a,a),(a,b),\dots,(d,c),(d,d) 在这个集合中各产生 1 贡献。 也就是说统计「所有子数组的不同元素个数平方和」在数值上相当于统计「每个子数组包含多少个元素二元组 (x,y) 」，即统计「 每个元素二元组 (x,y) 被多少个子数组 a_{l...r} 包含 」。 2. 计算每个右端点的贡献 假设我们固定了右端点 r ，其中包含元素二元组 (a,b) ，两者最后一次出现的位置分别为 p_a,p_b ，那么包含这个二元组的左端点 l 需要在位置 \min(p_a,p_b) 及之前，即这个二元组产生了 \min(p_a,p_b) 的贡献。 即对于一个固定的右端点 r ，假设其中所有元素最后一次出现的位置集合为 \{p_a,p_b,\dots,p_d\} ，那么这个右端点的总贡献为 \min(p_a,p_a)+\min(p_a,p_b)+\dots+\min(p_d,p_c)+\min(p_d,p_d) 。 3.计算移动右端点后的贡献变化 现在我们把右端点从 r 移动到 r+1 ，看看位置集合有什么变化。假设 a[r+1]=e ，且原先的有序位置集合为 \{p_a,p_b,\textcolor{red}{p_e},p_c,p_d\} ，那么移动前和 e 关联的贡献一共有两种情况： 在 e 左侧的元素，如 p_a,p_b ，产生自己位置的贡献； 在 e 右侧的元素，如 p_c,p_d ，产生 p_e 的贡献。 经过这次右端点移动， e 所在的位置被更新为 r+1 ，即现在的有序集合为 \{p_a,p_b,p_c,p_d,\textcolor{red}{p_e=r+1\}} 。此时 e 被移动到最右侧，因此贡献为其他位置之和。 因为只有和 e 关联的二元组发生了变化，所以我们用端点 r 的贡献减去移动前 e 产生的贡献（没出现过则为 0 ），再加上移动后 e 产生的贡献，就是端点 r+1 产生的贡献。 因此我们只需要动态维护右端点移动过程中元素的位置和与个数和，这两者都可以用树状数组维护，时间复杂度 O(n \log n) 。 注意对形如 (x,y) 和 (x,x) 的二元组分别处理，前者会因为 (x,y),(y,x) 产生两次贡献，后者只产生一次贡献。 代码 class Solution { public: using ll=long long; static constexpr int M=1000000007; static constexpr int N=100000; //lst：每个元素最后出现的位置 int i,j,k,n,lst[N+5]; //f：f[0]代表位置和，f[1]代表个数和，cf与cg为移动后位置和与个数和，pre为右端点(x,y)类贡献 ll f[N+5][2],cf,cg,pre,res; //树状数组增删 void add(int x,int y,int z){ //cf与cg为全局和，直接修改 cf+=y; cg+=z; for(;x<=n;x+=(-x&x)){ f[x][0]+=y; f[x][1]+=z; } } //树状数组查询 pair<ll,ll> get(int x,ll y=0,ll z=0){ for(;x;x-=(-x&x)){ y+=f[x][0]; z+=f[x][1]; } return {y,z}; } int sumCounts(vector<int>& nums) { //初始化，只清空使用的部分 n=nums.size(); for(int i=0;i<=n;i++)f[i][0]=f[i][1]=0; for(auto &i:nums)lst[i]=0; cf=cg=pre=res=0; for(int i=1;i<=n;i++){ auto &pos=lst[nums[i-1]]; //删除移除前的a[i-1]，不存在则不删 if(pos)add(pos,-pos,-1); //查询nums[i-1]修改前的贡献，lf为位置和，lg为个数和 auto [lf,lg]=get(pos); //贡献为左侧位置和+右侧个数和pos pre-=lf+(cg-lg)pos; //新贡献，为所有位置和 pre+=cf; //移动nums[i-1]至位置i add(i,i,1); pos=i; //加上右端点r的贡献，注意(x,y),(y,x)被枚举两次，但(x,x)只枚举一次 res+=pre2+cf; res%=M; } return res; } }; 2 个帖子 - 2 位参与者 阅读完整话题

  • 情报分类：综合情报
  • 分类依据：内容未命中明确的垂直分类规则，归入综合情报
  • 信息来源：服务器 / LINUX DO - 最新话题
  • 发布时间：2026/10/16 14:32:14