【算法】根号系列

带修莫队

这个东西其实说起来挺简单的,除了带一个修改原理和莫队没啥区别,复杂度……应该是n^{\frac{5}{3}}级别的……搞得和kdtree差不多。实现的时候,我们往查询操作里记录目前这个查询操作时已经算到哪个修改操作了,然后剩下的地方就是普通莫队了。原理挺简单的……只要你会莫队,记得把块开成n^\frac{2}{3},开到根号可能你会被卡到生不如死。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 2e6 + 10; 

struct ask
{
    int l, r, pre, pos;
}q[ms];

struct cha
{
    int pos, v;
}c[ms];

int col[ms], su[ms], n, m, lx, ly, taq, tac, bas[ms], sz, ans, pri[ms];

char opt[10];

inline bool cmp(ask a, ask b)//左侧块是第一关键字,右侧块是第二关键字,上一次修改是第三关键字 
{ 
    return bas[a.l] == bas[b.l] ? (bas[a.r] == bas[b.r] ? a.pre < b.pre : a.r < b.r) : a.l < b.l;
}

inline void add(int x)
{
    su[x] ++;
    if(su[x] == 1)
        ans ++;
}

inline void del(int x)
{
    su[x] --;
    if(su[x] == 0)
        ans --;
}

inline void work(int no, int p)
{
    if(c[no].pos >= q[p].l && c[no].pos <= q[p].r)
    {
        su[col[c[no].pos]] --;
        if(su[col[c[no].pos]] == 0)
            ans --;
        su[c[no].v] ++;
        if(su[c[no].v] == 1)
            ans ++;
    }
    swap(col[c[no].pos], c[no].v);//这里将目前序列中的颜色和修改操作做交换的原因是,我们可能需要撤销操作,这个时候我们默认将序列的值改成修改操作存的颜色,减少代码量 
}

inline void solve()
{
    int l = 1, r = 0, no = 0;
    for(ri i = 1; i <= taq; i ++)
    {
        while(l < q[i].l) 
            del(col[l]), l ++;
        while(l > q[i].l) 
            l --, add(col[l]);
        while(r < q[i].r) 
            r ++, add(col[r]);
        while(r > q[i].r) 
            del(col[r]), r --;
        while(no < q[i].pre) 
            no ++, work(no, i);
        while(no > q[i].pre) 
            work(no, i), no --;
        pri[q[i].pos] = ans;
    }
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        re(col[i]);
    for(ri i = 1; i <= m; i ++)
    {
        scanf("%s", opt);
        if(opt[0] == 'Q')
            re(lx), re(ly), taq ++, q[taq] = (ask){lx, ly, tac, taq};
        else
            re(lx), re(ly), tac ++, c[tac] = (cha){lx, ly};
    }
    sz = pow(n, 0.666666666);
    for(ri i = 1; i <= n; i ++)
        bas[i] = i / sz + 1;
    sort(q + 1, q + 1 + taq, cmp);
    solve();
    for(ri i = 1; i <= taq; i ++)
        printf("%d\n", pri[i]);
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注