带修改的莫队

发布于 2018-05-29  127 次阅读


带修改的莫队只支持单点修改

操作方法
普通的不带修改的莫队算法要把每个询问带上两个关键字排序,现在待修改的莫队算法要带上三个关键字排序。
这也是主要思想,和普通的莫队一样很简单的思想。
原本的莫队是[l,r]向连边推,现在带修改那么就设设三元(l,r,x),x为已经操作了x次修改,可以向(l±1,r,x),(l,r±1,x),(l,r,x±1)推,原理一样。

例题:bzoj数颜色

Description
墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?

Input
第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。

Output
对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

Sample Input
6 5

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

Sample Output
4

4

3

4

HINT
对于100%的数据,N≤10000,M≤10000,修改操作不多于1000次,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

思路:带修改的莫队裸题

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <deque>
#include <queue>
#define ri(n) scanf("%d",&n)
#define oi(n) printf("%d\n",n)
#define rl(n) scanf("%lld",&n)
#define ol(n) printf("%lld\n",n)
#define rep(i,l,r) for(i=l;i<=r;i++)
#define rep1(i,l,r) for(i=l;i<r;i++)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int epg=10-8;
const int maxn=1e6+20;
int len,cnt,num,ans;
int a[maxn],c[maxn],co[maxn];
int b[maxn];
int n,m;
int vis[maxn],last[maxn],ok[maxn];
map<int,int>mp;
//void ok(int x)
//{
//    for(int i=l[x];i<=r[x];i++)
//        mp[i].insert(a[i]);
//}
struct node
{
    int l,r,id,time;
    bool operator<(const node &q)const
    {
        return b[l]<b[q.l]||(b[l]==b[q.l]&&r<q.r);
    }
}p[maxn];
struct node2
{
    int x,y,pre;
}w[maxn];
void cal(int x)
{
    if(vis[x])
    {
        co[a[x]]--;
        if(co[a[x]]==0)
            ans--;
    }
    else
    {
        co[a[x]]++;
        if(co[a[x]]==1)
            ans++;
    }
    vis[x]^=1;
}
void change(int pos,int ad)
{
    if(vis[pos])
    {
        cal(pos);
        a[pos]=ad;
        cal(pos);
    }
    else
        a[pos]=ad;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        last[i]=a[i];
    }
    len=sqrt(n);
    for(int i=1;i<=n;i++)
        b[i]=(i-1)/len+1;
    int l,r;
    char c[2];
    //memset(vis,0,sizeof(vis));
    cnt=num=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%s%d%d",c,&l,&r);
        if(c[0]=='Q')
        {
           p[++cnt].l=l;p[cnt].r=r;p[cnt].id=cnt;p[cnt].time=num;
        }
        else
        {
            w[++num].x=l;w[num].y=r;w[num].pre=last[l];
            last[l]=r;
        }
    }
    sort(p+1,p+1+cnt);
    ans=0;
    l=r=1;cal(1);
    for(int i=1;i<=m;i++)
    {
        for(int j=p[i-1].time+1;j<=p[i].time;j++)
            change(w[j].x,w[j].y);
        for(int j=p[i-1].time;j>p[i].time;j--)
            change(w[j].x,w[j].pre);
        while (l<p[i].l)  cal(l++);
        while (l>p[i].l)  cal(--l);
        while (r<p[i].r)  cal(++r);
        while (r>p[i].r)  cal(r--);
        ok[p[i].id]=ans;
    }
    for(int i=1;i<=cnt;i++)
        printf("%d\n",ok[i]);
    return 0;
}

Comments


愿我如星君如月,夜夜流光相皎洁。