题解 P4690 【[Ynoi2016]镜中的昆虫】
2014吕泽龙
·
·
题解
分析
区间修改数颜色。
单点修改的操作是把相同颜色往前链，等价于问区间内前驱相同颜色不在当前区间的数的个数，这个东西用cdq分治或者树套树可以解决。修改的话用set搞定。
区间修改的话有一个结论是修改次数不超过O(n+m)次。
证明的话采用摊还分析。
考虑把所有相同颜色缩成一个点。
显然要修改的只有相同颜色区间的头和尾。
每一次区间操作把这个区间给单独抓出来，然后把这个区间内的点全部删掉，再插入修改后的代表这个区间的节点。
每次区间头，区间尾，以及新的区间各产生一个节点，总共新产生不超过3m个节点。
一个点之多再删除和插入的时候修改一次，所以至多进行2次修改。所以总共修改次数不超过O(n+m)
上述证明就提供了方法。采用set维护区间即可。
### **代码**
采用树套树
常数巨大。
```cpp
#include<bits/stdc++.h>
#define ins insert
#define era erase
#define Ub(x) upper_bound(Data(x))
#define Lb(x) lower_bound(Data(x))
const int N = 4e5 + 10;
int ri() {
char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f;
}
int n, Mx, cnt, pre[N], a[N];
struct Data {
int l, r, col;
Data(int _l = 0, int _r = 0, int _col = 0) : l(_l), r(_r), col(_col) {}
bool operator < (const Data &a) const {return l < a.l;}
};
std::set<Data>st[N], all;
std::set<Data>::iterator it;
std::set<int>nw;
std::set<int>::iterator it2;
std::map<int, int>M;
struct Val_Segment{
int s[N * 50], ls[N * 50], rs[N * 50], sz;
void Modify(int &p, int L, int R, int x, int v) {
s[p ? p : p = ++sz] += v;
if(L == R) return ; int m = L + R >> 1;
x <= m ? Modify(ls[p], L, m, x, v) : Modify(rs[p], m + 1, R, x, v);
}
int Query(int p, int L, int R, int ed) {
if(!p || ed == R) return s[p]; int m = L + R >> 1;
return ed <= m ? Query(ls[p], L, m, ed) : s[ls[p]] + Query(rs[p], m + 1, R, ed);
}
}seg;
struct Pos_Segment {
int rt[N];
void Modify(int x, int l, int v) {
for(;x <= n; x += x&-x)
seg.Modify(rt[x], 0, Mx, l, v);
}
int Query(int x, int k) {
int r = 0;
for(;x; x -= x&-x)
r += seg.Query(rt[x], 0, Mx, k);
return r;
}
int Query(int l, int r, int k) {return Query(r, k) - Query(l - 1, k);}
}Rt;
void Up(int x, int v) {
Rt.Modify(x, pre[x], -1);
pre[x] = v;
Rt.Modify(x, pre[x], 1);
}
void Ins(int l, int r, int col) {
st[col].ins(Data(l, r)); all.ins(Data(l, r, col));
}
void Era(Data x) {
st[x.col].era(x); all.era(x);
}
void Split(int x) {
it = all.Ub(x); --it;
if(it->l == x) return ;
Data tmp = *it;
Era(tmp);
Ins(tmp.l, x - 1, tmp.col);
Ins(x, tmp.r, tmp.col);
}
void Modify(int l, int r, int col) {
Split(l);
if(r < n) Split(r + 1);
nw.clear(); nw.ins(col);
for(;1;) { //把所有介于l，r的区间全部抓出来。
it = all.Lb(l);
if(it == all.end() || it->l > r)
break;
Data tmp = *it; nw.ins(tmp.col);
if(tmp.l > l && pre[tmp.l] != tmp.l - 1)
Up(tmp.l, tmp.l - 1);
Era(tmp);
}
it = st[col].Lb(l); Up(l, (--it)->r);
Ins(l, r, col);
for(it2 = nw.begin();it2 != nw.end(); ++it2) { //所有右端点开头的都要修改。
it = st[*it2].Ub(r);
if(it == st[*it2].end())
continue;
int pos = it->l;
it = st[*it2].Lb(pos);
Up(pos, (--it)->r);
}
}
int main() {
n = ri(); int q = ri(); Mx = n + q;
for(int i = 1;i <= n; ++i) {
a[i] = ri();
if(!M[a[i]])
st[M[a[i]] = ++cnt].insert(Data());
a[i] = M[a[i]];
}
for(int i = 1;i <= n; ++i) {
it = st[a[i]].end(); --it; pre[i] = it->l;
Rt.Modify(i, pre[i], 1);
Ins(i, i, a[i]);
}
for(;q--;) {
int op = ri(), l = ri(), r = ri();
if(op == 1) {
int x = ri();
if(!M[x])
st[M[x] = ++cnt].insert(Data());
x = M[x]; Modify(l, r, x);
}
else if(op == 2)
printf("%d\n", Rt.Query(l, r, l - 1));
}
return 0;
}
```