基础莫队

将待查询区间排序

排序：先按左端点分块的编号递增排序块内按照右端点的下标递增排序

最坏时间复杂度 O ( n n ) O(n\sqrt{n}) O(nn

)

HH的项链

题意

HH 有一串由各种漂亮的贝壳组成的项链。

HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。

HH 不断地收集新的贝壳，因此他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？

这个问题很难回答，因为项链实在是太长了。

于是，他只好求助睿智的你，来解决这个问题。

思路

莫队模板题

数据范围

1 ≤ N ≤ 50000 1≤N≤50000 1≤N≤50000

1 ≤ M ≤ 2 × 1 0 5 1≤M≤2×10^5 1≤M≤2×105

1 ≤ L ≤ R ≤ N 1≤L≤R≤N 1≤L≤R≤N

代码

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }

const int N = 50010, M = 200010, S = 1000010;

int n, m;
int a[N], cnt[S], ans[M];
int block;

struct Node {
    int id, l, r;
}node[M];

bool cmp(const Node& a, const Node& b) {
    // 按照分块编号递增排序，块内按照右端点递增排序
    if (a.l / block == b.l / block)return a.r < b.r;
    return a.l / block < b.l / block;
}

void add(int x, int& res) {
    cnt[x]++;
    if (cnt[x] == 1)res++;
}

void del(int x, int& res) {
    cnt[x]--;
    if (!cnt[x])res--;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
    cin >> m;

    for (int i = 1; i <= m; ++i) { // 将查询离线
        int l, r; scanf("%d%d", &l, &r);
        node[i] = { i,l,r };
    }

    block = n / sqrt(n); // 块的大小
    sort(node + 1, node + 1 + m, cmp); // 对查询排序

    int i = 0, j = 1;
    int res = 0;
    for (int k = 1; k <= m; ++k) {// 对排序后的查询进行计算
        int l = node[k].l;
        int r = node[k].r;

        while (i < r)add(a[++i], res);
        while (i > r)del(a[i--], res);
        while (j < l)del(a[j++], res);
        while (j > l)add(a[--j], res);

        ans[node[k].id] = res;
    }


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

signed main() {

    // int _; cin >> _;
    // while (_--)
        solve();

    return 0;
}

卡常优化代码

亲测从 1600+ms 优化到 1100+ms

基础莫队算法基础莫队

#include<bits/stdc++.h>
#include<unordered_map>
#pragma GCC optimize(2)
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
//template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }

const int N = 50010, M = 200010, S = 1000010;

int n, m;
int a[N], cnt[S], ans[M];
int block;

struct Node {
    int id, l, r;
}node[M];

bool cmp(const Node& a, const Node& b) {
    // 如果当前两个区间左端点在同一个奇数块，那么按右端点递减排序，否则按右端点递增排序
    int l = a.l / block, r = b.l / block;
    return l ^ r ? l < r : (l & 1 ? a.r < b.r : a.r > b.r);
}

void add(int x, int& res) {
    cnt[x]++;
    if (cnt[x] == 1)res++;
}

void del(int x, int& res) {
    cnt[x]--;
    if (!cnt[x])res--;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
    cin >> m;

    for (int i = 1; i <= m; ++i) {
        int l, r; scanf("%d%d", &l, &r);
        node[i] = { i,l,r };
    }

    block = n / sqrt(n);
    sort(node + 1, node + 1 + m, cmp);

    int i = 0, j = 1;
    int res = 0;
    for (int k = 1; k <= m; ++k) {// 对排序后的查询进行计算
        int l = node[k].l;
        int r = node[k].r;
		
        // 将add del函数 通过运算优先级优化成常数
        while (i < r)res += !cnt[a[++i]]++; 
        while (i > r)res -= !--cnt[a[i--]];
        while (j < l)res -= !--cnt[a[j++]];
        while (j > l)res += !cnt[a[--j]]++;

        ans[node[k].id] = res;
    }


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

signed main() {

    // int _; cin >> _;
    // while (_--)
    solve();

    return 0;
}

Different Intergers

来源：牛客2018多校

题意

给定一个长度为 n 的数组 a，和 m 个询问，每次询问给定一个 [l,r] 求出 a 1 , a 2 , … a i , a j , a j + 1 , … , a n a_1,a_2,\dots a_i,a_j,a_{j + 1},\dots,a_n a1,a2,…ai,aj,aj+1,…,an 中不同的数的数量

数据范围

1 ≤ n , q ≤ 1 0 5 1 ≤ n, q ≤ 10^5 1≤n,q≤105

1 ≤ a i ≤ n 1 ≤ a_i ≤ n 1≤ai≤n

1 ≤ l i , r i ≤ n 1 ≤ l_i, r_i ≤ n 1≤li,ri≤n

思路

与求某区间内不同数的思路相同，先用莫队思想把查询区间排序，与上题（HH的项链）不同的是，将 l 初始为 0，r初始为 n + 1，最初包括整个区间。这样每次用 l，r与当前查询的 lr比较。

例如，如果 e [ i ] . r < r e[i].r < r e[i].r<r 那么 r递减到 e [ i ] . r e[i].r e[i].r 就会把 $r 到到到 e[i].r$ 中所有的数加进去，因为 r 是从 n + 1 即整个区间的右端点开始的，那么当前加进去的数就是 e [ i ] . r e[i].r e[i].r 到 n 的所有数，满足了题目的要求。

l l l 从0 开始类似。

相应的

add

del

操作也要进行更改，因为 r 变大或者 l 变小时，区间里的数是减少的。r 变小或者 l 变大时，区间里的数是增加的。

代码

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }

const int N = 1e5 + 10;

int n, m;
int a[N], ans[N], cnt[N];
int block;

struct Node {
    int id, l, r;
}node[N];

bool cmp(const Node& a, const Node& b) {
    if (a.l / block == b.l / block)return a.r < b.r;
    return a.l / block < b.l / block;
}
void add(int x, int& res) {
    cnt[x] ++;
    if (cnt[x] == 1)res++;
}

void del(int x, int& res) {
    cnt[x]--;
    if (!cnt[x])res--;
}

void solve() {
    while (~scanf("%d%d", &n, &m)) {
        memset(cnt, 0, sizeof cnt);
        for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);

        block = sqrt(n);

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

        sort(node + 1, node + 1 + m, cmp);
        int l = 0, r = n + 1;
        int res = 0;
        for (int i = 1; i <= m; ++i) {
            int id = node[i].id;

            while (r < node[i].r)del(a[r++], res);
            while (r > node[i].r)add(a[--r], res);
            while (l < node[i].l)add(a[++l], res);
            while (l > node[i].l)del(a[l--], res);

            ans[id] = res;
        }

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

signed main() {

    // int _; cin >> _;
    // while (_--)
    solve();

    return 0;
}

基础莫队算法基础莫队

基础莫队

HH的项链

题意

思路

数据范围

代码

卡常优化代码

Different Intergers

题意

数据范围

思路

代码

继续阅读

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

【数据结构】医院选址

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

[转]ISUP信令的IAM消息详细内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希