SS241113C. 数据结构 (struct)
题意
有 \(n\) 个数，\(m\) 个操作，\(n,m,a_i\le 10^6\)，每次操作给区间 \([l,r]\) 的所有数字加 \(1\)，然后输出全局颜色数量，操作独立。
思路
感觉不好想，对我来讲有点难，需要更聪明的脑袋和丰富的想象力。
首先 \(O(n \sqrt{n})\) 的莫队做法是显然的，假设 \(n,m\) 同阶。
考虑从操作出发，操作比较特别，是区间 \(+1\)。
那么对于区间每个颜色 \(c\)，都会变成 \(c+1\)。此时需要分 \(c\) 是否消失，\(c+1\) 是否新出现讨论。
- \(c\) 消失了。
说明所有 \(c\) 都在 \([l,r]\) 内，设 \(mn_c,mx_c\) 分别为 \(c\) 最小、最大出现的位置，即 \(l \le mn_c \le mx_c \le r\)。
这个可以扫描线二维数点做，扫描 \(mx_c,r\)，数 \(l,mn_c\)。
- \(c+1\) 新出现了。
计算这个贡献的前提是 \([l,r]\) 中存在 \(c\)。
注意因为我们会讨论 \(c+1\) 消失了的情况，并且会计入贡献，因此这里其实是计算在 \([l,r]\) 之外没有 \(c+1\)。如果存在颜色 \(c+1\)，则要求 \(l \le mn_{c+1} \le mx_{c+1} \le r\)，这个和刚刚一样。另一种情况是本来就不存在颜色 \(c+1\)。
简化一下。发现如果操作区间存在 \(c\)，且满足 \(c+1\) 全部在操作区间里面，那么原来的 \(c+1\) 就会消失，然后又会有新的 \(c+1\) 出现，因此无需考虑这种情况。而如果本来不存在 \(c+1\)，那么也不会有 \(c+1\) 消失的情况。
因此我们要考虑的是：
- 操作区间里面没有 \(c\)，而 \(c+1\) 全部在操作区间里面，答案减一。
- 操作区间里面有 \(c\)，而本来不存在 \(c+1\)，答案加一。
\([l,r]\) 中不存在 \(c\)。也就是 \([l,r] \subseteq\) 某两个相邻的颜色 \(c\) 之间。
即 \(pos_l < l \le mn_{c+1} \le mx_{c+1} \le r < pos_r\)。其中 \(pos_l,pos_r\) 表示相邻的两个 \(c\) 的位置。
下面是难点。
扫描 \(r\)，扫到 \(mx_{c+1}\) 的时候，在树状数组的 \((pos_l,mn_{c+1}]\) 的位置减 \(1\)（注意区间可能为空集）。扫到 \(pos_r\) 的时候，如果 \(mx_{c+1} \le pos_r\)（注意可以取等，因为等于的时候你之间是减过贡献的，需要加回去），在树状数组的 \((pos_l,mn_{c+1}]\) 的位置加回 \(1\)（注意此时不一定存在 \(c+1\)）。
然后你发现操作 \(2\)，其实就是当不存在 \(c+1\) 的时候，此时你刚好扫到 \(pos_r\)，直接给 \((pos_l,pos_r]\) 加一！
时间复杂度 \(O((n+m) \log n)\)。感觉理解难度比较大。
code
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace poetry {
#define isdigit(x) (x>='0'&&x<='9')
#define gc getchar_unlocked
#define pc putchar_unlocked
template <typename T>
void read(T &x) {
x=0;
char ch=gc();
for(;!isdigit(ch);ch=gc());
for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+(ch^48);
}
template <typename T>
void write(T x,char ch) {
static int st[40];
int top=0;
do {
st[top++]=x%10;
x/=10;
}while(x);
while(top) pc(st[--top]^48);
pc(ch);
}
constexpr int N=1e6+7;
int n,m;
int a[N];
int tr[N];
int ans[N];
void add(int x,int val) { for(;x<=n;x+=x&-x) tr[x]+=val; }
int query(int x) {
int s=0;
for(;x;x-=x&-x) s+=tr[x];
return s;
}
struct que {
int id,l,r;
}q[N];
bool cmp (que a,que b) { return a.r < b.r; }
int mx[N],mn[N],mx_pos[N],my_pos[N];
int sum;
void main() {
read(n),read(m);
rep(i,1,n) read(a[i]);
rep(i,1,m) read(q[i].l),read(q[i].r),q[i].id=i;
rep(i,1,n+1) mn[i]=n+1;
per(i,n,1) mn[a[i]]=i;
rep(i,1,n) my_pos[i]=mx[a[i]], mx_pos[a[i]]=mx[a[i]-1], mx[a[i]]=i;
rep(i,1,n) if(mx[i]) sum++;
sort(q+1,q+m+1,cmp);
int it=0;
rep(i,1,m) {
int l=q[i].l,r=q[i].r;
while(it<r) {
++it;
if(it==mx[a[it]]) {
int L=mx_pos[a[it]], R=mn[a[it]];
if(L<R) add(L+1,-1), add(R+1,1);
}
if(it>=mx[a[it]+1]) {
int L=my_pos[it], R=min(it,mn[a[it]+1]);
if(L<R) add(L+1,1), add(R+1,-1);
}
}
ans[q[i].id]=query(l);
}
rep(i,1,m) write(sum+ans[i],'\n');
}
}
int main() {
#ifdef LOCAL
freopen("my.out","w",stdout);
#else
freopen("struct.in","r",stdin);
freopen("struct.out","w",stdout);
#endif
poetry :: main();
}