首页 > > 程序设计 > C/C++ >

带修改莫队算法

2018-06-17 22:14:10来源：未知阅读 ()

update in 2017.12.24：

以前写的≈shit，实在看不下去了，重写一遍

pre

很早之前就学习了莫队算法。

老师讲课的时候就提到过带修改莫队在线莫队树上莫队树上带修改莫队……但是一直都没有做到过有关的题，

今天有幸做了一道裸的带修改莫队的题，

那就来分享一下自己的经验

带修改的莫队

首先我们要知道，普通的莫队算法是不资瓷修改操作的，

不过后人对莫队算法加以改进

发明了资瓷修改的莫队算法

思路：

在进行修改操作的时候，修改操作是会对答案产生影响的(废话)

那么我们如何避免修改操作带来的影响呢？

首先我们需要把查询操作和修改操作分别记录下来。

在记录查询操作的时候，需要增加一个变量来记录离本次查询最近的修改的位置

然后套上莫队的板子，与普通莫队不一样的是，你需要用一个变量记录当前已经进行了几次修改

对于查询操作，如果当前改的比本次查询需要改的少，就改过去

反之如果改多了就改回来

说的听绕口的

比如，我们现在已经进行了3次修改，本次查询是在第5次修改之后，那我们就执行第4,5次修改

这样就可以避免修改操作对答案产生的影响了

code

题目链接

update in 2018.5.4

洛谷数据被加强了，块的大小开$sqrt(N)$会T飞，开$n^{\frac{2}{3}}$可无压力过，带修改莫队真是玄学

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cmath>
#include<algorithm>
#define swap(x, y) x ^= y, y ^= x, x^= y
using namespace std;
const int MAXN= 2*1e6+10;
inline int read() {
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
    return x*f;
}
char obuf[1<<24], *O=obuf;
void print(int x) {
    if(x > 9) print(x / 10);
    *O++ = x % 10 + '0';
}
int N, M;
int a[MAXN], where[MAXN];
struct Query {
    int x, y, pre, id;
}Q[MAXN];
int Qnum = 0;
struct Change {
    int pos,val;
}C[MAXN];
int Cnum = 0;
int color[MAXN], ans=0, base, out[MAXN];
int comp(const Query &a,const Query &b) {
    return where[a.x] == where[b.x] ? ( where[a.y] == where[b.y] ? a.pre < b.pre : a.y < b.y ): a.x < b.x ;
}
void Add(int val){if(++color[val]==1) ans++; } 
void Delet(int val){ if(--color[val]==0) ans--; }
void Work(int now, int i) {
    if(C[now].pos >= Q[i].x && C[now].pos <= Q[i].y) {
        if( --color[a[C[now].pos]] == 0 ) ans--;
        if( ++color[C[now].val] == 1)     ans++; 
    }
    swap(C[now].val, a[C[now].pos]);
}
void MoQueue()
{
    int l = 1, r = 0, now = 0; 
    for(int i = 1;i <= Qnum;i++)
    {
        while(l < Q[i].x) Delet(a[l++]);
        while(l > Q[i].x) Add(a[--l]);
        while(r < Q[i].y) Add(a[++r]);
        while(r > Q[i].y) Delet(a[r--]); 
        while(now < Q[i].pre) Work(++now, i);
        while(now > Q[i].pre) Work(now--, i);
        out[Q[i].id] = ans;
    }
    for(int i = 1;i <= Qnum; i++)
        print(out[i]), *O++ = '\n';
}
int main()
{
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    freopen("a.out","w",stdout); 
    #endif
    N = read();M = read();
    for(int i = 1;i <= N; i++) a[i] = read();
    while(M--)
    {
        char opt[5];
        scanf("%s",opt);
        if(opt[0] == 'Q') {
            Q[++Qnum].x = read();
            Q[Qnum].y = read();
            Q[Qnum].pre = Cnum;//???????????? 
            Q[Qnum].id = Qnum;        
        }
        else if(opt[0] == 'R') {
            C[++Cnum].pos = read();
            C[Cnum].val = read();
        }
    }
    base = pow(N, 0.6666666666);
    for(int i = 1; i <= N; i++) where[i] = i / base + 1;
    sort(Q+1, Q+Qnum+1, comp);
    MoQueue();
    fwrite(obuf, O-obuf, 1, stdout);
    return 0;
}

新代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=2*1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
    return x*f;
}
int N,M;
int a[MAXN],where[MAXN];
struct Query
{
    int x,y,pre,id;
}Q[MAXN];
int Qnum=0;
struct Change
{
    int pos,val;
}C[MAXN];
int Cnum=0;
int color[MAXN],ans=0,base,out[MAXN];
int comp(const Query &a,const Query &b)
{
    if(a.x!=b.x) return where[a.x]<where[b.x];
    if(a.y!=b.y) return where[a.y]<where[b.y];
    return a.pre<b.pre;
}
void Add(int val)
{    
    if(++color[val]==1) ans++;
} 
void Delet(int val)
{
    if(--color[val]==0) ans--;
}
void Work(int now,int i)
{
    if(C[now].pos>=Q[i].x&&C[now].pos<=Q[i].y)//注意：只有修改在查询的区间内才会对查询的结果产生影响 
    {
        if( --color[a[C[now].pos]] == 0 ) ans--;
        if( ++color[C[now].val] == 1)      ans++; 
    }
    swap(C[now].val,a[C[now].pos]);
    //这里有个很巧妙的操作
    //对于一个操作，下一次需要为的颜色是本次被改变的颜色
    //比如，我把颜色3改为了7，那么再进行这次修改的时候就是把7改为3
    //所以直接交换两种颜色就好 
}
void MoQueue()
{
    int l=1,r=0,now=0; 
    for(int i=1;i<=Qnum;i++)
    {
        while(l<Q[i].x)    Delet(a[l++]);
        while(l>Q[i].x) Add(a[--l]);
        while(r<Q[i].y) Add(a[++r]);
        while(r>Q[i].y) Delet(a[r--]);//以上四句为莫队模板 
        while(now<Q[i].pre) Work(++now,i);//改少了，改过去 
        while(now>Q[i].pre) Work(now--,i);//改多了，改回来 
        out[Q[i].id]=ans;//统计答案 
    }
    for(int i=1;i<=Qnum;i++)
        printf("%d\n",out[i]);
}
int main()
{
    N=read();M=read();
    base=sqrt(N);
    for(int i=1;i<=N;i++) a[i]=read(),where[i]=(i-1)/base+1;
    while(M--)
    {
        char opt[5];
        scanf("%s",opt);
        if(opt[0]=='Q')
        {
            Q[++Qnum].x=read();
            Q[Qnum].y=read();
            Q[Qnum].pre=Cnum;//别忘了记录最近的修改位置 
            Q[Qnum].id=Qnum;        
        }
        else if(opt[0]=='R')
        {
            C[++Cnum].pos=read();
            C[Cnum].val=read();
        }
    }
    sort(Q+1,Q+Qnum+1,comp);//玄学排序 
    MoQueue();
    return 0;
}