题解 P4690 【[Ynoi2016]镜中的昆虫】

BFqwq · 2020-02-04 22:25:41 · 题解

Ynoi2016 镜中的昆虫

由于本题空间范围修改，该题解目前无法通过，但做法为正解的二维数点，仅供参考。

（其实这道在Ynoi中还算简单）

首先，区间染色，想到珂朵莉树。但显然这题数据不可能随机。

接着我们来思考：在无修改的情况下（也就是HH的项链）我们是使用一个线段树或树状数组维护前驱的。

那么这道题的解法就是综合这两种思想：

我们考虑一个颜色，显然，我们只需要将这种颜色记录一次。

在静态中，我们是通过维护前驱完成的，那么在动态中，我们同样维护前驱。

记一个点左侧最靠右且与之颜色相同的点为 pre，若无则为 0，

那么我们只需要统计 i\in[l,r] 且 pre_i\in[0,l) 的点，因为这些点是这个区间中这个颜色的点中最靠左的那一个。

(这是个很显然的事实，因为如果这个点的 pre_i\le l 那么 pre_i 这一个点也属于 [l,r] 且与之同色，并且更靠左)

将点在序列中的位置作为一维，前驱作为另一维，用树状数组套权值树维护。

在修改的时候，我们用珂朵莉树的思想，用 set 将同色的点结合成一个段，显然，一个段内的点出了最左侧的之外前驱均为 i-1。

每次修改的时候，我们将左右个端点所在的段拆分，然后暴力取出中间的段修改并将之合并为一个段。

采用摊还法，set 内初始有 n 个段，修改时产生的段个数可以看成 \operatorname{O}(m) （左右端点断开后新增的段），

那么修改次数的复杂度可以看成均摊的 \operatorname{O}(n+m)=\operatorname{O}(n) （n,m 同阶），单次修改复杂度 \operatorname{O}(\log^2 n)，总复杂度 \operatorname{O}(n\log^2 n)。

在具体实现的时候有几个小细节。第一个是权值线段树的下标要从 0 开始，

第二个是我们在维护全局 set 的同时也对每个颜色各开一个 set 一起操作，这样会更方便。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>=10) write(x/10);
    putchar('0'+x%10);
}
const int maxn=400005;
int len=0;
const int inf=2147483647;
struct node{
    int l,r,x;
    //node():l(0),r(0),x(0){}
    friend bool operator <(node a,node b){
        return a.l<b.l;
    }
}tp;
struct seg{
    int v,ls,rs;
}t[maxn*50];
int rt[maxn],n,m,tot,tem[maxn],tmp[maxn],cnt,num;
int lsh[maxn<<1],a[maxn],pre[maxn];
struct cz{
    int a,b,c,d;
}q[maxn];
set<node> s[maxn],al;
set<int> now;
set<node>:: iterator it;
set<int>:: iterator _it;
int lb(int x){
    return x&(-x);
}
void pushup(int o){
    t[o].v=t[t[o].ls].v+t[t[o].rs].v;
}
void change(int &o,int l,int r,int k,int v){
    if(!o) o=++tot;
    if(l==r){
        t[o].v+=v;
        return ;
    }
    int mid=l+r>>1;
    if(k<=mid) change(t[o].ls,l,mid,k,v);
    else change(t[o].rs,mid+1,r,k,v);
    pushup(o);
}
void add(int o,int v){
    for(int i=o;i<=n;i+=lb(i)) change(rt[i],0,n,pre[o],v);
}
int query(int l,int r,int k){
    if(l==r) {
        return 0;
    }
    int mid=l+r>>1,sum=0;
    if(k<=mid){
        for(int i=1;i<=cnt;i++) tem[i]=t[tem[i]].ls;
        for(int i=1;i<=num;i++) tmp[i]=t[tmp[i]].ls;
        return query(l,mid,k);
    }
    else{
        for(int i=1;i<=cnt;i++) sum+=t[t[tem[i]].ls].v,tem[i]=t[tem[i]].rs;
        for(int i=1;i<=num;i++) sum-=t[t[tmp[i]].ls].v,tmp[i]=t[tmp[i]].rs;
        return sum+query(mid+1,r,k);
    }
}
int find(int l,int r,int k){
    cnt=num=0;
    for(int i=r;i;i-=lb(i)){
        tem[++cnt]=rt[i];
    }
    for(int i=l-1;i;i-=lb(i)){
        tmp[++num]=rt[i];
    }
    return query(0,n,k);
}
void split(int x){
    tp=(node){x,0,0};
    it=al.upper_bound(tp);--it;
    if(it->l==x) return;
    tp=*it;
    al.erase(tp);s[tp.x].erase(tp);
    node tp1=(node){tp.l,x-1,tp.x};
    node tp2=(node){x,tp.r,tp.x};
    al.insert(tp1);al.insert(tp2);
    s[tp.x].insert(tp1);
    s[tp.x].insert(tp2);
}
void update(int l,int r,int x){
    if(l!=1) split(l);
    if(r+1<=n) split(r+1);
    now.insert(x);
    tp=(node){l,0,0};
    it=al.lower_bound(tp);
    while(it->l!=r+1){
        tp=*it;now.insert(tp.x);
        if(tp.l>l&&pre[tp.l]!=tp.l-1){
            add(tp.l,-1);
            pre[tp.l]=tp.l-1;
            add(tp.l,1);
        }
        al.erase(tp);s[tp.x].erase(tp);
        tp=(node){l,0,0};
        it=al.lower_bound(tp);
        if(it==al.end()) break;
    }
    tp=(node){l,0,0};
    it=s[x].lower_bound(tp);--it;
    add(l,-1);pre[l]=it->r;add(l,1);
    tp=(node){l,r,x};
    al.insert(tp);s[x].insert(tp);
    for(_it=now.begin();_it!=now.end();++_it){
        tp=(node){r,0,0};
        it=s[*_it].upper_bound(tp);
        if(it!=s[*_it].end()){
            l=it->l;
            tp=(node){l,0,0};
            it=s[*_it].lower_bound(tp);--it;
            add(l,-1);pre[l]=it->r;add(l,1);
        }
    }
    now.clear();
}
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();lsh[++len]=a[i];
    }
    for(int i=1;i<=m;i++){
        q[i].a=read();q[i].b=read();q[i].c=read();
        if(q[i].a==1){
            q[i].d=read();
            lsh[++len]=q[i].d;
        }
    }
    sort(lsh+1,lsh+len+1);
    len=unique(lsh+1,lsh+len+1)-lsh-1;
    tp=(node){0,0,0};
    for(int i=1;i<=len;i++)s[i].insert(tp);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh;
        it=s[a[i]].end();it--;pre[i]=it->l;
        add(i,1);
        tp=(node){i,i,a[i]};
        al.insert(tp);s[a[i]].insert(tp);
    }
    for(int i=1;i<=m;i++){
        if(q[i].a==1){
            q[i].d=lower_bound(lsh+1,lsh+len+1,q[i].d)-lsh;
            update(q[i].b,q[i].c,q[i].d);
        }
        else{
            write(find(q[i].b,q[i].c,q[i].b));
            puts("");
        }
    }
    return 0;
}