题解

待修改的莫队，一开始以为很难，结果好像还比较简单。就多记录一个当前询问是在第几个修改之后，莫队过程中也多记录一个当前在第几个修改后，改多了就改回去，改少了就修改就好了。

cmp函数也要再加一维时间，不过第二个判断也变成了右端点的块，而不只是两点相不相等（没看清楚一直T）。

还有只有修改在询问区间采取统计答案！！！！！

至于搞修改有两种：

1.记录这个前x位置的数，然后就分修改和撤销修改稿

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;

const int maxn=150000;
const int maxm=1000005;
int n,m,cnt,num;
int nowl=1,nowr=0,nownum=0,ret;
int a[maxn],b[maxn];
int size,pos[maxn];
int ans[maxn],vis[maxm];
struct query{
  int l,r,id,num;
}q[maxn];
struct modify{
  int x,y,pre,num;
}mo[maxn];

template<class T>inline void read(T &x){
    x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}

bool cmp(query a,query b){
  if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
  if(pos[a.r]!=pos[b.r])  return pos[a.r]<pos[b.r];
  return a.num<b.num;
}

inline void add(int x){
  if(++vis[a[x]]==1) ret++;
}

inline void del(int x){
  if(!--vis[a[x]]) ret--;
}

inline void go(int i){
  if(nowl<=mo[i].x&&mo[i].x<=nowr){
    if(!--vis[a[mo[i].x]]) ret--;
    if(++vis[mo[i].y]==1) ret++;
  }
  a[mo[i].x]=mo[i].y;
}

inline void back(int i){
  if(nowl<=mo[i].x&&mo[i].x<=nowr){
    if(!--vis[a[mo[i].x]]) ret--;
    if(++vis[mo[i].pre]==1) ret++;
  }
  a[mo[i].x]=mo[i].pre;
}

int main(){
  read(n);read(m);
  size=pow(n,2.0/3);
  for(int i=1;i<=n;i++){
    read(a[i]);b[i]=a[i];
    pos[i]=(i-1)/size+1;
  }
  for(int i=1;i<=m;i++){
    char op[2];
    scanf("%s",op);
    if(op[0]=='Q'){
      int l,r;
      read(l);read(r);
      ++cnt;
      q[cnt]=(query){l,r,cnt,num};
    }
    else {
      int x,y;
      read(x);read(y);
      ++num;
      mo[num]=(modify){x,y,b[x],num};
      b[x]=y;
    }
  }
  sort(q+1,q+cnt+1,cmp);
  for(int i=1;i<=cnt;i++){
    while(nowl>q[i].l) add(--nowl);
    while(nowr<q[i].r) add(++nowr);
    while(nowl<q[i].l) del(nowl++);
    while(nowr>q[i].r) del(nowr--);
    while(nownum<q[i].num) go(++nownum);
    while(nownum>q[i].num) back(nownum--);
    ans[q[i].id]=ret;
  }
  for(int i=1;i<=cnt;i++) printf("%d
",ans[i]);
}

莫队1

2.然后就是可以发现经过一次该修改后，下一次经过一定是改回去，所以交换修改的值和原序列的值即可。

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

const int maxn=150000;
const int maxm=1000005;
int n,m,cnt,num;
int nowl=1,nowr=0,nownum=0,ret;
int a[maxn];
int size,pos[maxn];
int ans[maxn],vis[maxm];
struct query{
  int l,r,id,num;
}q[maxn];
struct modify{
  int x,y,pre,num;
}mo[maxn];

template<class T>inline void read(T &x){
    x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}

bool cmp(query a,query b){
  if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
  if(pos[a.r]!=pos[b.r])  return pos[a.r]<pos[b.r];
  return a.num<b.num;
}

inline void add(int x){
  if(++vis[a[x]]==1) ret++;
}

inline void del(int x){
  if(!--vis[a[x]]) ret--;
}

inline void change(int i){
  if(nowl<=mo[i].x&&mo[i].x<=nowr){
    if(!--vis[a[mo[i].x]]) ret--;
    if(++vis[mo[i].y]==1) ret++;
  }
  swap(a[mo[i].x],mo[i].y);
}

int main(){
  read(n);read(m);
  size=pow(n,2.0/3);
  for(int i=1;i<=n;i++){
    read(a[i]);
    pos[i]=(i-1)/size+1;
  }
  for(int i=1;i<=m;i++){
    char op[2];
    scanf("%s",op);
    if(op[0]=='Q'){
      int l,r;
      read(l);read(r);
      ++cnt;
      q[cnt]=(query){l,r,cnt,num};
    }
    else {
      int x,y;
      read(x);read(y);
      ++num;
      mo[num]=(modify){x,y,num};
    }
  }
  sort(q+1,q+cnt+1,cmp);
  for(int i=1;i<=cnt;i++){
    while(nowl>q[i].l) add(--nowl);
    while(nowr<q[i].r) add(++nowr);
    while(nowl<q[i].l) del(nowl++);
    while(nowr>q[i].r) del(nowr--);
    while(nownum<q[i].num) change(++nownum);
    while(nownum>q[i].num) change(nownum--);
    ans[q[i].id]=ret;
  }
  for(int i=1;i<=cnt;i++) printf("%d
",ans[i]);
}

莫队2

然后这道题也可以用树套树做（我没写），由HH的项链可以得到答案就是$sum_{i=l}^{r}pre[i]<l$，pre是上一个与a[i]值相同的位置，用树状数组记录原序列，每个节点开一颗值域线段树记录区间上pre。

修改就随便yy，知道哪些的pre会改就好了。不过维护pre和next很麻烦，所以用set或者splay维护（这就是为什么我不想写的原因）。

反正纯属xbb，随便看看就行。

[国家集训队]数颜色 / 维护队列 题目描述 题解

题解

相关推荐

[国家集训队]数颜色 / 维护队列题目描述题解