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

· · 题解

update on 2020.3.8

时空开小后使用了O(n)空间的分块

juruo第一次给Ynoi写题解啊

这里提供一个nsqrt(n)的做法

我们定义f[i]表示i后面第一个与i颜色相同的位置的下标

（如果没有，我们认为f[i] = n+1）

这个我们可以开一个set维护每一段里同一种颜色的，另外再对于每种颜色分别开个set维护,然后f的修改次数是O(n+m)的。

这个我就不详细说了，别的题解也有。

这里主要讲下分块怎么维护

（我看其他dalao有写树套树的，我这个蒟蒻树套树还不太熟练，于是写了个分块）

每次询问我们的答案，就是[l,r]里f值>=r的数的个数

我们对于整个序列分块，块里维护f值。对于块里，我们现在要求这么一个东西：

单点修改

查询整体 >= r 的个数

因为f 的值域是[1,n]，所以说我们可以维护块内前缀和，就是 块内f值在[1,i]内的数的个数

这个如果我们用树状数组维护，再调整块大小，可以

（没写过不知道能不能过 当然，也有更好的方法 我们在块里再来一个分块 要求达到一个基本操作 > O(1)前缀和 > O(sqrt(n)) 修改 这个很简单，我们维护每个数在块中的前缀和，和每个块结尾的前缀和即可 这个还是放下代码吧 ``` inline void add(int x,int y) { for(int i = c[x]; i <= mm; i ++) s[i] += y; for(int i = x; c[i] == c[x]; i ++) ss[i] += y; } inline int sum(int x) { return ss[x] + s[c[x]-1]; } ``` 这样我们就达到了$n\sqrt{n}

这个做法应该还是比树套树写着方便很多的

好了，下面是完整代码


#include<bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define se set<aa>
#define it iterator
#define lb lowber_bound

int n,m,nn,mm,sb;
map<int,int>p;
int a[MAXN],f[MAXN],u[MAXN],tt[MAXN];
int c[MAXN],d[MAXN]; 
struct aa
{
    int l,r,v;
};
set<aa>s[MAXN];

bool operator <(aa a,aa b) {
    return a.r < b.r;
}

set<aa>odt;

void fenkuai() 
{
    sb = sqrt(n);
    for(int i = 1; i <= n+1; i ++) {
        if(i%sb == 1) {
            c[i] = c[i-1]+1;
            d[i] = 1;
        } else {
            c[i] = c[i-1];
            d[i] = d[i-1]+1;
        }
    }
    mm = c[n];
}

struct kuai
{
    int s[MAXN],ss[MAXN];

    inline void jia(int x,int y)
    {
        for(int i = c[x]; i <= mm; i ++)
            s[i] += y;
        for(int i = x; c[i] == c[x]; i ++)
            ss[i] += y; 
    }

    inline int sum(int x) {
        return ss[x] + s[c[x]-1];
    }
}b[355];

void rd()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++)
        scanf("%d",&a[i]);
    for(int i = 1; i <= n; i ++)
    {
        if(!p.count(a[i])) {
            nn ++;
            p[a[i]] = nn;
            tt[nn] = a[i];
        }
        s[ p[a[i]] ].insert((aa){i,i,p[a[i]]});
    }
    fenkuai();
    for(int i = n; i >= 1; i --) {
        int t = u[ p[a[i]] ];
        if(t) f[i] = t;
        else f[i] = n+1;
        b[c[i]].jia(f[i],1);
        u[p[a[i]]] = i;
    }
    for(int i = 1; i <= n; i ++) {
        odt.insert((aa){i,i,p[a[i]]});
    } 

    for(int i = 1; i <= n*2; i ++) {
        s[i].insert((aa){n+1,n+1,i}); 
        s[i].insert((aa){0,0,i}); 

    }
} 

void split(se::it x,int i)
{
    int v = x->v,l = x->l,r = x->r;
    if(i < l || i >= r) return; 

    s[v].erase((aa){l,r,v});
    s[v].insert((aa){l,i,v});
    s[v].insert((aa){i+1,r,v});

    odt.erase(x);
    odt.insert((aa){l,i,v});
    odt.insert((aa){i+1,r,v});
}

aa qls(int v,int x) {
    se::it i = s[v].upper_bound((aa){0,x,0});
    i --;
    return (*i);
} 

void qf(int x,int y) {
    b[c[x]].jia(f[x],-1);
    f[x] = y; 
    b[c[x]].jia(f[x],1);
} 

void dlt(int l,int r,int v)
{
    s[v].erase((aa){l,r,v});
    aa ls = qls(v,l);
    aa rs = *s[v].lower_bound((aa){0,r,0});
    qf(r,r+1); 
    qf(ls.r,rs.l);
}

void jlt(int l,int r,int v)
{
    aa ls = qls(v,l);
    aa rs = *s[v].lower_bound((aa){0,r,0}); 
    s[v].insert((aa){l,r,v});
    qf(ls.r,l);
    qf(r,rs.l);
} 

void assign(int l,int r,int v)
{
    se::it x = odt.lower_bound((aa){0,l-1,0});
    split(x,l-1);

    se::it y = odt.lower_bound((aa){0,r,0});
    split(y,r);

    x = odt.lower_bound((aa){0,l,0});
    y = odt.lower_bound((aa){0,r+1,0});

    for(se::it i = x; i != y; ) {
        se::it j = i;
        i ++; 
        dlt(j->l,j->r,j->v);
        odt.erase(j);
    } 

    odt.insert((aa){l,r,v});
    jlt(l,r,v);
}

signed main()
{
    rd();
    for(int i = 1; i <= m; i ++)
    {
        int l,r,v,opt;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt == 1) {
            scanf("%d",&v);
            if(!p.count(v)) {
                nn ++;
                p[v] = nn;
                tt[nn] = v;
            }
            assign(l,r,p[v]);
        } else {
            int ans = r-l+1;
            if(c[l] != c[r])
            {
                for(int j = c[l]+1; j <= c[r]-1; j ++) 
                    ans -= b[j].sum(r);
                for(int j = l; c[l] == c[j]; j ++)
                    ans -= (f[j] <= r);
                for(int j = r; c[r] == c[j]; j --)
                    ans -= (f[j] <= r);

            } else {
                for(int j = l; j <= r; j ++)
                    ans -= (f[j] <= r);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
 }

Update 关于O(n)空间分块做法

还是当初Juan_Feng鸽鸽教我的qaq

考虑对询问分块，考虑每一个块的询问，我们会发现r只有\sqrt n种，那么我们就可以把按照r,把f[i]的值分成\sqrt n段，然后询问每个块完成后重构一下即可。

时间和与原来的做法差不多，但是空间小了很多

#include<bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define se set<aa>
#define it iterator
#define lb lowber_bound

int n,m,nn,mm,sb;
map<int,int>p;
int a[MAXN],f[MAXN],u[MAXN],tt[MAXN];
int c[MAXN],d[MAXN]; 
struct aa
{
    int l,r,v;
};
set<aa>s[MAXN];
struct op {
    int op,l,r,v;
}opt[MAXN]; 
int mr[MAXN],srz[MAXN],ak;

bool operator <(aa a,aa b) {
    return a.r < b.r;
}

set<aa>odt;

void fenkuai() 
{
    sb = sqrt(n);
    for(int i = 1; i <= n+1; i ++) {
        if(i%sb == 1) {
            c[i] = c[i-1]+1;
            d[i] = 1;
        } else {
            c[i] = c[i-1];
            d[i] = d[i-1]+1;
        }
    }
    mm = c[n];
}

struct kuai
{
    int s[355];

    inline void jia(int x,int y)//sqrt(n)
      {
        if(srz[x] == 0) return; 
        for(int i = srz[x]; i <= mm; i ++)
            s[i] += y;
      }

    inline int sum(int x) {//O(1)
        return s[x];
    }
}b[355];

inline int read()
{
    register int x = 0 , ch = getchar();
    while( !isdigit( ch ) ) ch = getchar();
    while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch = getchar();
    return x;
}

void chonggou(int x)
{
    for(int i = 1; i <= c[n]; i ++)
        memset(b[i].s,0,sizeof(b[i].s));
    memset(srz,0,sizeof(srz));
    ak = 0;
    for(int i = x; i <= m && i <= x+sb-1; i ++)  
    if(opt[i].op == 2){
        ak ++;
        mr[ak] = opt[i].r+1;
        srz[mr[ak]] ++;
    }
    sort(mr+1,mr+ak+1);
    srz[1] ++;
    for(int i = 1; i <= n; i ++)
        srz[i] += srz[i-1];
    srz[n+1] = 0;
    for(int i = 1; i <= n; i ++) 
        b[c[i]].s[srz[f[i]]] ++;

    for(int i = 1; i <= mm; i ++)
        for(int j = 2; j <= mm; j ++)
            b[i].s[j] += b[i].s[j-1];
} 

void rd()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++)
        scanf("%d",&a[i]);
    for(int i = 1; i <= m; i ++) {
        opt[i].op = read();
        opt[i].l = read();
        opt[i].r = read();

        if(opt[i].op == 1) {
            opt[i].v = read();
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!p.count(a[i])) {
            nn ++;
            p[a[i]] = nn;
            tt[nn] = a[i];
        }
        s[ p[a[i]] ].insert((aa){i,i,p[a[i]]});
    }
    fenkuai();
    for(int i = n; i >= 1; i --) {
        int t = u[ p[a[i]] ];
        if(t) f[i] = t;
        else f[i] = n+1;
        b[c[i]].jia(f[i],1);
        u[p[a[i]]] = i;
    }
    chonggou(1);
    for(int i = 1; i <= n; i ++) {
        odt.insert((aa){i,i,p[a[i]]});
    } 
    for(int i = 1; i <= n*2; i ++) {
        s[i].insert((aa){n+1,n+1,i}); 
        s[i].insert((aa){0,0,i}); 
    }
} 

void split(se::it x,int i)
{
    int v = x->v,l = x->l,r = x->r;
    if(i < l || i >= r) return; 

    s[v].erase((aa){l,r,v});
    s[v].insert((aa){l,i,v});
    s[v].insert((aa){i+1,r,v});

    odt.erase(x);
    odt.insert((aa){l,i,v});
    odt.insert((aa){i+1,r,v});
}

aa qls(int v,int x) {
    se::it i = s[v].upper_bound((aa){0,x,0});
    i --;
    return (*i);
} 

inline void qf(int x,int y)
{
    if(x == 0) return;
    b[c[x]].jia(f[x],-1);
    f[x] = y; 
    b[c[x]].jia(f[x],1);
} 

void dlt(int l,int r,int v)
{
    s[v].erase((aa){l,r,v});
    aa ls = qls(v,l);
    aa rs = *s[v].lower_bound((aa){0,r,0});
    qf(r,r+1); 
    qf(ls.r,rs.l);
}

void jlt(int l,int r,int v)
{
    aa ls = qls(v,l);
    aa rs = *s[v].lower_bound((aa){0,r,0}); 
    s[v].insert((aa){l,r,v});
    qf(ls.r,l);
    qf(r,rs.l);
} 

void assign(int l,int r,int v)
{
    se::it x = odt.lower_bound((aa){0,l-1,0});
    split(x,l-1);
    se::it y = odt.lower_bound((aa){0,r,0});
    split(y,r);

    x = odt.lower_bound((aa){0,l,0});
    y = odt.lower_bound((aa){0,r+1,0});

    for(se::it i = x; i != y; ) {
        se::it j = i;
        i ++;
        dlt(j->l,j->r,j->v);
        odt.erase(j);
    } 

    odt.insert((aa){l,r,v});
    jlt(l,r,v);
}

signed main()
{
    rd();
    for(int i = 1; i <= m; i ++)
    {
        int l = opt[i].l,r = opt[i].r,v = opt[i].v,op = opt[i].op;
        if(op == 1) {
            if(!p.count(v)) {
                nn ++;
                p[v] = nn;
                tt[nn] = v;
            }
            assign(l,r,p[v]);
        } else {
            int ans = r-l+1;
            if(c[l] != c[r])
            {
                int t = srz[r];
                for(int j = c[l]+1; j <= c[r]-1; j ++) 
                    ans -= b[j].sum(t);
                for(int j = l; c[l] == c[j]; j ++)
                    ans -= (f[j] <= r);
                for(int j = r; c[r] == c[j]; j --)
                    ans -= (f[j] <= r);
            } else {
                for(int j = l; j <= r; j ++)
                    ans -= (f[j] <= r);
            }
            printf("%d\n",ans);
        }

        if((i%sb) == 0) {
            chonggou(i+1);
        }
    }
    return 0;
 }