题目传送门
题面
题目描述
蓝桥智慧城市在一条主干道上沿路安装了 \(N\) 个智能交通信号灯，这些信号灯按位置从 \(1\) 到 \(N\) 编号。每个信号灯都有着一种控制模式，对于第 \(i\) 个信号灯，其控制模式用 \(A_i\) 表示，\(A_i\) 是一个大于等于 \(1\) 的整数。
为了评估信号灯配置的 “多样性”，交通管理专家提出了一种度量方式：对于任意两个不同位置 \(x\) 和 \(y\)，它们的多样性分数被定义为大于等于 \(1\) 的整数中，第一个既不是 \(A_x\) 也不是 \(A_y\) 的数值，记作 \(\text{mex}(A_x, A_y)\)。例如，当 \(A_x = 1\) 且 \(A_y = 2\) 时，\(\text{mex}(1, 2) = 3\)；当 \(A_x = 1\) 且 \(A_y = 3\) 时，\(\text{mex}(1, 3) = 2\)；当 \(A_x = 2\) 且 \(A_y = 2\) 时，\(\text{mex}(2, 2) = 1\)。
政府希望通过分析和调整信号灯配置，提升道路通行效率。为此，他们计划执行 \(M\) 条操作指令，每条指令为以下两类之一：
- \(1\ l\ r\)：查询操作。计算所有满足 \(l \leq i < j \leq r\) 的信号灯对 \((A_i, A_j)\)，其多样性分数 \(\text{mex}(A_i, A_j)\) 的总和。
- \(2\ k\ x\)：调整操作。将第 \(k\) 个信号灯的控制模式 \(A_k\) 修改为新的值 \(x\)。
现在，请你协助政府依次处理这 \(M\) 次操作，并输出每个查询操作的结果。
输入格式
第一行包含两个整数 \(N\) 和 \(M\)，分别表示信号灯的数量和操作指令的数量。
第二行包含 \(N\) 个整数 \(A_1, A_2, \ldots, A_N\)，表示初始的信号灯控制模式。
接下来 \(M\) 行，每行描述一条操作指令，格式如上所述。
输出格式
对于每个查询操作，输出一行包含一个整数，表示多样性分数的总和。
输入输出样例 #1
输入 #1
5 3
1 2 3 4 5
1 1 5
2 1 2
1 1 5
输出 #1
15
10
说明/提示
【样例说明】
初始时信号灯的控制模式依次为：\(1, 2, 3, 4, 5\)。第一次查询区间 \([1, 5]\)，\(\text{mex}\) 值分别为 \(3, 2, 2, 2, 1, 1, 1, 1, 1, 1\)，总和为 \(15\)。
第二次操作后，信号灯的控制模式依次为：\(2, 2, 3, 4, 5\)。第二次查询区间 \([1, 5]\)，\(\text{mex}\) 值均为 \(1\)，总和为 \(10\)。
【评测用例规模与约定】
对于 \(10\%\) 的评测用例，\(2 \leq N, M \leq 100\)，\(1 \leq l < r \leq N\)，\(1 \leq k \leq N\)，\(1 \leq A_i, x \leq 10^3\)。
对于 \(40\%\) 的评测用例，\(2 \leq N, M \leq 10^3\)，\(1 \leq l < r \leq N\)，\(1 \leq k \leq N\)，\(1 \leq A_i, x \leq 10^5\)。
对于 \(100\%\) 的评测用例，\(2 \leq N, M \leq 10^5\)，\(1 \leq l < r \leq N\)，\(1 \leq k \leq N\)，\(1 \leq A_i, x \leq 10^9\)。
题目大意
给你一个长度为 \(N\) 的序列，编号 \(1\) 至 \(N\)，编号为 \(i\) 的序列值为 \(A_i\)。
执行 \(M\) 次操作，其中一种操作是修改序列值，另一种操作是查询区间 \(l\) 至 \(r\) 的序列值两两组合，每组的大于等于 \(1\) 且不等于两序列值的最小整数的和。
思路
首先，咱们来分析一下 \(mex\) 运算。
不难发现，\(mex\) 的取值只能是 \(1\) 或 \(2\) 或 \(3\)。
求证一下，设选中的两序列值为 \(A_i\) 与 \(A_j\)，且 \(A_i \le A_j\)。
当 \(1 < A_i \le A_j\) 时，\(mex\) 值为 \(1\)；
当 \(A_i = 1\) 且 \(2 < A_j\) 或 \(A_j = 1\) 时，\(mex\) 值为 \(2\)；
当 \(A_i = 1\) 且 \(A_j = 2\) 时，\(mex\) 值为 \(3\)。
我们也可以看出序列值划分为三类，等于 \(1\)、等于 \(2\)、大于 \(2\)。
于是可以想到，将所有大于 \(2\) 的数设为 \(3\)，这样既不影响查询结果，也方便了我们进行处理。
再仔细看看题目，呦，序列单点修改区间查询！
是不是想到了某个熟悉的数据结构？
当然是 —— 线段树了虽然似乎树状数组更有性价比！
我们可以使用线段树，每个节点分别存储其表示的区间内值为 \(1\) 与 \(2\) 与 \(3\) 的数的数量。
那现在又有一个问题了：怎么统计 \(mex\) 数之和呢？
假设我们已经分别求出了区间 \(l\) 至 \(r\) 之间的数值为 \(1\)、\(2\)、\(3\) 的数的个数，分别设为 \(x\)、\(y\)、\(z\)。
我们可以对执行 \(mex\) 的两数进行分类讨论，一共六种情况。
分别可能为为 \((1,2)\)、\((2,3)\)、\((1,3)\)、\((1,1)\)、\((2,2)\)、\((3,3)\)。
然后我们运用已知每种情况的贡献值，就可以用排列组合的知识进行求解了。
具体求法可参考以下代码片段。
long long cal(node x)
{//sum[1]表示值为1的数的个数//sum[2]表示值为2的数的个数//sum[3]表示值为3的数的个数long long ans=0;ans+=(long long)(x.sum[1]*x.sum[2])*3;ans+=(long long)(x.sum[2]*x.sum[3]);ans+=(long long)(x.sum[1]*x.sum[3])*2;ans+=(long long)(x.sum[1]*(x.sum[1]-1));ans+=(long long)(x.sum[2]*(x.sum[2]-1))/2;ans+=(long long)(x.sum[3]*(x.sum[3]-1))/2;return ans;
}
然后我们就可以快乐地开始打恶心的线段树了。
代码实现
废话不多说，上代码。
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long a[maxn];
int n,m;
struct node
{long long sum[4];
}tree[maxn<<2];
int ls(int x){return (x<<1);}
int rs(int x){return ((x<<1)|1);}
void push_up(int d)
{tree[d].sum[1]=tree[ls(d)].sum[1]+tree[rs(d)].sum[1];tree[d].sum[2]=tree[ls(d)].sum[2]+tree[rs(d)].sum[2];tree[d].sum[3]=tree[ls(d)].sum[3]+tree[rs(d)].sum[3];return ;
}
void build(int d,int l,int r)
{if(l==r){tree[d].sum[a[l]]++;return ;}int mid=(l+r)>>1;build(ls(d),l,mid);build(rs(d),mid+1,r);push_up(d);return ;
}
node query(int ql,int qr,int d,int l,int r)
{if(ql<=l&&r<=qr){return tree[d];}int mid=(l+r)>>1;node ans1,ans2;bool f1=0,f2=0;if(ql<=mid){ans1=query(ql,qr,ls(d),l,mid);f1=1;}if(qr>mid){ans2=query(ql,qr,rs(d),mid+1,r);f2=1;}if(f1==1&&f2==1){ans1.sum[1]+=ans2.sum[1],ans1.sum[2]+=ans2.sum[2],ans1.sum[3]+=ans2.sum[3];return ans1;}else{return (f1==1?ans1:ans2);}
}
void change(int k,int x,int d,int l,int r)
{if(l==r){tree[d].sum[a[l]]=0;a[l]=x;tree[d].sum[a[l]]++;return ;}int mid=(l+r)>>1;if(k<=mid)change(k,x,ls(d),l,mid);else change(k,x,rs(d),mid+1,r);push_up(d);return ;
}
long long cal(node x)
{long long ans=0;ans+=(long long)(x.sum[1]*x.sum[2])*3;ans+=(long long)(x.sum[2]*x.sum[3]);ans+=(long long)(x.sum[1]*x.sum[3])*2;ans+=(long long)(x.sum[1]*(x.sum[1]-1));ans+=(long long)(x.sum[2]*(x.sum[2]-1))/2;ans+=(long long)(x.sum[3]*(x.sum[3]-1))/2;return ans;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;++i){cin>>a[i];if(a[i]>2)a[i]=3;}build(1,1,n);int op,l,r;while(m--){cin>>op>>l>>r;if(op==1){node t=query(l,r,1,1,n);cout<<cal(t)<<"\n";}else{if(r>2)r=3;change(l,r,1,1,n);}}return 0;
}
如有问题请直接提出，我会改进该篇题解。
最后感谢您的留步与观看，希望本篇题解能够帮到您。