HH项链

基础莫队算法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
struct node{                             //离线记录查询操作
  int L, R, k;                           //k：查询操作的原始顺序
}q[N];
int pos[N];
int ans[N];
int cnt[N];                             //cnt[i]: 统计数字i出现了多少次
int a[N];
bool cmp(node a, node b){               //按块排序，就是莫队算法：           
  if(pos[a.L] != pos[b.L])              //按L所在的块排序，如果块相等，再按R排序
    return pos[a.L] < pos[b.L];
  if(pos[a.L] & 1) return a.R > b.R;    //奇偶性优化，如果删除这一句，性能差一点
    return a.R < b.R;
  /*如果不按块排序，而是直接L、R排序，就是普通暴力法：
  if(a.L==b.L) return a.R < b.R;
  return a.L < b.L; */
}
int ANS = 0;
void add(int x){                       //扩大区间时（L左移或R右移），增加数x出现的次数
  cnt[a[x]]++;
  if(cnt[a[x]]==1) ANS++;              //这个元素第1次出现
}
void del(int x){                       //缩小区间时（L右移或R左移），减少数x出现的次数
  cnt[a[x]]--;
  if(cnt[a[x]]==0) ANS--;             //这个元素消失了
}
int main(){
  int n; scanf("%d",&n);              //序列长度
  int block = sqrt(n);                //每块的大小
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);                //读第i个元素
    pos[i]=(i-1)/block + 1;           //第i个元素所在的块
  }
  int m; scanf("%d",&m);              //操作次数
  for(int i=1;i<=m;i++){              //读取所有m个查询，离线处理
    scanf("%d%d",&q[i].L, &q[i].R);
    q[i].k = i;                       //记录查询的原始顺序
  }
  sort(q+1, q+1+m, cmp);              //对所有查询排序
  int L=1, R=0;                       //左右指针的初始值：当左右指针重合就包含了一个元素
  for(int i=1;i<=m;i++){
    while(L<q[i].L) del(L++); //{del(L); L++;}     //缩小区间：L右移
    while(R>q[i].R) del(R--); //{del(R); R--;}     //缩小区间：R左移
    while(L>q[i].L) add(--L); //{L--; add(L);}     //扩大区间：L左移
    while(R<q[i].R) add(++R); //{R++; add(R);}     //扩大区间：R右移
    ans[q[i].k] = ANS;
  }
  for(int i=1;i<=m;i++) printf("%d\n",ans[i]);     //按原顺序打印结果
  return 0;
}

笔记：莫队算法 = 离线 + 暴力 +分块。离线就是先记录所有步数，找到效率更高的查询方法。用双指针单向扫描统计是暴力法，在扫描时排序的方法是莫队算法重点，分块排序扫描，相同块内再用右区间决定前后顺序。再用奇偶排序优化块与块之间的相邻节点

树状数组

#include <iostream>
#include <algorithm>
#define lowbit(x) (x & -x)
using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], res[N], f[N];
struct Query {
  int id, l, r;
} q[N];
int tr[N];

inline void add(int k, int x) {
  for (; k <= n; k += lowbit(k)) tr[k] += x;          //更新树状数组
}

inline int sum(int k) {
  int res = 0;
  for (; k; k -= lowbit(k)) res += tr[k];            //0-k：累计区间数值
  return res;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }

  sort(q, q + m, [&](Query &q1, Query &q2) {      //匿名函数：右区间正序
    return q1.r < q2.r;
  });

  for (int i = 1, k = 0; k < m; k++) {
    int r = q[k].r, l = q[k].l, id = q[k].id;
    for (; i <= n && i <= r; i++) {
      if (f[a[i]]) add(f[a[i]], -1);
      f[a[i]] = i;
      add(i, 1);
    }
    res[id] = sum(r) - sum(l - 1);
  }

  for (int i = 0; i < m; i++) printf("%d\n", res[i]);
}

笔记：单独使用莫队的成绩不太理想，使用树状数组能轻松的完成满分。右区间排序f[]去重，用树状数组更新数次，最后用右区间减去左区间的差储存在res[]

版权声明：

本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_46105170/article/details/125930102