提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  大数据

当前栏目

P1903 [国家集训队]数颜色 / 维护队列 带修改莫队

队列队列 修改 颜色 维护 莫队
2023-09-27 14:26:02 时间

题目描述

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入格式

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。

第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式

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

输入输出样例

输入 #1 
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
输出 #1 
4
4
3
4

说明/提示

对于30%的数据，n,m \leq 10000n,m≤10000

对于60%的数据，n,m \leq 50000n,m≤50000

对于所有数据，n,m \leq 133333n,m≤133333

所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

本题可能轻微卡常数

 

题解：

最基础莫队：SP3267 DQUERY - D-query 莫队板子题

莫队算法是离线算法，不支持修改，强制在线需要另寻他法。的确，遇到强制在线的题目莫队基本上萎了，但是对于某些允许离线的带修改区间查询来说，莫队还是能大展拳脚的。做法就是把莫队直接加上一维，变为带修莫队。

那么加上一维什么呢？具体怎么实现？我们的做法是把修改操作编号，称为"时间戳"，而查询操作的时间戳沿用之前最近的修改操作的时间戳。跑主算法时定义当前时间戳为 t ，对于每个查询操作，如果当前时间戳相对太大了，说明已进行的修改操作比要求的多，就把之前改的改回来，反之往后改。只有当当前区间和查询区间左右端点、时间戳均重合时，才认定区间完全重合，此时的答案才是本次查询的最终答案。

通俗地讲，就是再弄一指针，在修改操作上跳来跳去，如果当前修改多了就改回来，改少了就改过去，直到次数恰当为止。

int l=1,r=0,now=0,time=0;  //time代表当前时间
    for(int i=1; i<=cnt_node; ++i)
    {
        int start=node[i].l,last=node[i].r,temp=node[i].time;
        while(l<start) now-=!--cnt[arr[l++]];
        while(l>start) now+=!cnt[arr[--l]]++;
        while(r<last) now+=!cnt[arr[++r]]++;
        while(r>last) now-=!--cnt[arr[r--]];
        while(time<temp)  //判断这个区间是不是在某个修改之后的
        {
            ++time;
            if(start<=modi[time].pos && last>=modi[time].pos)
                now -= !--cnt[arr[modi[time].pos]] - !cnt[modi[time].val]++;
            swap(arr[modi[time].pos],modi[time].val);  //修改原序列
        }
        while(time>temp)
        {
            if(start <= modi[time].pos && modi[time].pos <= last)
                now -= !--cnt[arr[modi[time].pos]] - !cnt[modi[time].val]++;
            swap(arr[modi[time].pos], modi[time].val);
            --time;
        }
        ans[node[i].id]=now;
    }

 

 

而且还需要修改一下排序函数：

int cmp(Node a, Node b)  //注意排序函数也需要改变
{
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.time < b.time);
}

 

除此之外，最重要的就是我们分块按照sqrt(n)不是最优的，当块的大小为pow(n, 2.0 / 3.0)时（也就是n的2/3次方）理论复杂度达到最优

块大小取pow(n, 2.0 / 3.0)，总体复杂度O(pow(n, 5.0 / 3.0))。而块大小取√n时会退化成O(n2)

 

代码：

//复杂度n*sqrt(n)
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926;
const long long N = 1000006;
const double eps = 1e-10;
typedef long long ll;
#define mem(A, B) memset(A, B, sizeof(A))
#define lson rt<<1 , L, mid
#define rson rt<<1|1 , mid + 1, R
#define ls rt<<1
#define rs rt<<1|1
#define SIS std::ios::sync_with_stdiget_mod_new(z-x)o(false), cin.tie(0), cout.tie(0)
#define pll pair<long long, long long>
#define lowbit(abcd) (abcd & (-abcd))
#define max(a, b) ((a > b) ? (a) : (b))
#define min(a, b) ((a < b) ? (a) : (b))
int arr[maxn],cnt[maxn],belong[maxn];
int n,m,sizes,new_size,cnt_node,cnt_modi,ans[maxn];
struct Node
{
    int l,r,id,time;
} node[maxn];
struct Modify
{
    int pos,val,last;
} modi[maxn];
int cmp(Node a, Node b)  //注意排序函数也需要改变
{
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.time < b.time);
}
int main()
{
    scanf("%d%d",&n,&m);
    sizes = pow(n, 2.0 / 3.0);
    new_size=ceil((double)n/sizes);
    for(int i=1; i<=new_size; ++i)
    {
        for(int j=(i-1)*sizes+1; j<=i*sizes; ++j)
        {
            belong[j]=i;
        }
    }
    for(int i=1; i<=n; ++i)
        scanf("%d",&arr[i]);
    for(int i=1; i<=m; ++i)
    {
        char s[5];
        scanf("%s",s);
        if(s[0]=='Q')
        {
            ++cnt_node;
            scanf("%d%d",&node[cnt_node].l,&node[cnt_node].r);
            //不能把上面两句改成：
            //scanf("%d%d",&node[++cnt_node].l,&node[cnt_node].r);
            node[cnt_node].time=cnt_modi;
            node[cnt_node].id=cnt_node;
        }
        else
        {
            ++cnt_modi;
            scanf("%d%d",&modi[cnt_modi].pos,&modi[++cnt_modi].val);

        }
    }
    sort(node+1,node+1+cnt_node,cmp);
    int l=1,r=0,now=0,time=0;
    for(int i=1; i<=cnt_node; ++i)
    {
        int start=node[i].l,last=node[i].r,temp=node[i].time;
        while(l<start) now-=!--cnt[arr[l++]];
        while(l>start) now+=!cnt[arr[--l]]++;
        while(r<last) now+=!cnt[arr[++r]]++;
        while(r>last) now-=!--cnt[arr[r--]];
        while(time<temp)  //判断这个区间是不是在某个修改之后的
        {
            ++time;
            if(start<=modi[time].pos && last>=modi[time].pos)
                now -= !--cnt[arr[modi[time].pos]] - !cnt[modi[time].val]++;
            swap(arr[modi[time].pos],modi[time].val);  //修改原序列
        }
        while(time>temp)
        {
            if(start <= modi[time].pos && modi[time].pos <= last)
                now -= !--cnt[arr[modi[time].pos]] - !cnt[modi[time].val]++;
            swap(arr[modi[time].pos], modi[time].val);
            --time;
        }
        ans[node[i].id]=now;
    }
    for(int i=1; i<=cnt_node; ++i)
        printf("%d\n",ans[i]);
    return 0;
}


/*
6 2
1 2 3 4 5 5
Q 1 4
Q 2 6
*/

 

相关文章